March 24, 2020 Single Round Match 772 Editorials
PlusCastle
Used as: Division Two – Level One:
| Value | 250 |
| Submission Rate | 100 / 146 (68.49%) |
| Success Rate | 42 / 100 (42.00%) |
| High Score | gravito12345 for 238.62 points (6 mins 15 secs) |
| Average Score | 172.98 (for 42 correct submissions) |
The first fact is spaces are not useful. Deleting a space doesn’t reduce the number of closed figures.
Now consider count is a complete square number, i. e. count = x * x. We create a full square with a side of length x. So the answer is (x – 1)^2. It also works for non-complete square counts.
Code by agw02010:
def maximiseClosedFigures(self, k):
ret = int((k ** 0.5 - 1) ** 2)
return ret
PermutationAndMultiplication
Used as: Division Two – Level Two:
| Value | 500 |
| Submission Rate | 70 / 146 (47.95%) |
| Success Rate | 25 / 70 (35.71%) |
| High Score | BKM009 for 464.92 points (7 mins 55 secs) |
| Average Score | 299.49 (for 25 correct submissions) |
We can remove additional trailing zeros from A it will not affect the answer. Now, A = 2^ones-1 and B = 2^(ones+zeros-1) + 2 ^ (ones – 1) – 1⇒ A * B = 2^(ones+ones+zeros-1) + 2^(ones+ones-1) – 2^ones – (2^(ones+zeros-1) + 2 ^ (ones – 1) – 1).
Adding (and subtracting) two numbers can be done in O(n).
Code by BKM009:
public static int multiplyAndCount(int m, int n)
{
if (m == 1)
{
return 1;
}
if (m <= n)
{
return 2 * m;
}
if (m == 2 && n == 1)
{
return 4;
}
if (n == 1)
{
return m + 1;
}
return m;
}
AntiprimeNumbers
Used as: Division Two – Level Three:
| Value | 1000 |
| Submission Rate | 9 / 146 (6.16%) |
| Success Rate | 3 / 9 (33.33%) |
| High Score | moririn2528 for 590.15 points (28 mins 11 secs) |
| Average Score | 545.22 (for 3 correct submissions) |
We solve the problem for D = 8. We can create 3^N numbers with digits 4, 6, 8. Let’s involve digit “1”. “1” could be never placed after “1”, “4”, or “6”. Also, “1” could be never placed after two “8”s. We have 3^(n-1) options with placing 1 at the start of the string and fill the remaining with 4, 6, 8. Also, we have 3^(n-2) options to start with “81” and fill the remaining with 4, 6, 8.Code by Tomii9273:
def countAntiPrimes(self, N, D):
s = int(N)
d = D
mod = 10**9+7
def pow(x, y):
if y==0:
return 1
ans = 1
while y > 0:
if y % 2 == 1:
ans = (ans * x) % mod
x = (x * x) % mod
y //= 2
return ans
if d < 4:
if s == 1:
ans = 1
else:
ans = 0
elif d < 6:
ans = 2
elif d < 8:
if s == 1:
ans = 3
else:
ans = (pow(2, s-1) * 3) % mod
else:
if s == 1:
ans = 4
elif s == 2:
ans = 13
else:
ans = (4*pow(3, s-1) + pow(3, s-2)) % mod
return ans
SmoothPermutations
Used as: Division One – Level One:
| Value | 250 |
| Submission Rate | 91 / 126 (72.22%) |
| Success Rate | 64 / 91 (70.33%) |
| High Score | square1001 for 233.16 points (7 mins 44 secs) |
| Average Score | 146.01 (for 64 correct submissions) |
Let f(n, k, x) be the number of permutations of numbers 1 to n such that the largest element among the first k elements is at most equal to x.
f(n, k, x) = (n – k) * (n – 1 – k) * (n – 2 – k) * … * (x + 1 – k) * x * (x – 1) * (x – 2) * … * 1.
But there are a lot of queries. We need to calculate it faster. It’s possible with a segment tree or a sparse table. Let sp(i, j) be i * (i + 1) * (i + 2) * … * (i + 2 ^ j – 1) and precompute this function. Now calculating of every L * (L + 1) * (L + 2) * … * R is possible using this values in O(log).
Total complexity is O(T * log(MX)).Code by square1001:
int sz, mod;
vector<int> seg;
int query(int a, int b, int k, int l, int r) {
if (a <= l && r <= b) return seg[k];
if (r <= a || b <= l) return 1;
int lc = query(a, b, k * 2, l, (l + r) >> 1);
int rc = query(a, b, k * 2 + 1, (l + r) >> 1, r);
return 1LL * lc * rc % mod;
}
int query(int a, int b) {
if (a <= 0) return 0;
return query(a, b, 1, 0, sz);
}
long long countPermutations(int T, int M, int MX, int seed, vector<int> prefN, vector<int> prefK, vector<int> prefX) {
mod = M;
vector<int> A(3 * T);
A[0] = seed;
for (int i = 1; i < 3 * T; ++i) {
A[i] = (A[i - 1] * 1103515245LL + 12345) % 2147483648LL;
}
vector<int> N(T), K(T), X(T);
int LEN = prefN.size();
for (int i = 0; i < LEN; ++i) {
N[i] = prefN[i];
K[i] = prefK[i];
X[i] = prefX[i];
}
for (int i = LEN; i < T; ++i) {
N[i] = (A[i] % MX) + 1;
K[i] = (A[T + i] % N[i]) + 1;
X[i] = (A[2 * T + i] % N[i]) + 1;
}
sz = 1;
while (sz <= MX) sz *= 2;
seg.resize(sz * 2);
for (int i = 0; i < sz; ++i) {
seg[i + sz] = i;
}
for (int i = sz - 1; i >= 1; --i) {
seg[i] = 1LL * seg[2 * i] * seg[2 * i + 1] % mod;
}
long long ans = 0;
for (int i = 0; i < T; ++i) {
int lc = query(X[i] - K[i] + 1, X[i] + 1);
int rc = query(1, N[i] - K[i] + 1);
int sub = 1LL * lc * rc % M;
ans += sub;
}
return ans;
}
MaxPoints
Used as: Division One – Level Two:
| Value | 500 |
| Submission Rate | 25 / 126 (19.84%) |
| Success Rate | 23 / 25 (92.00%) |
| High Score | tourist for 432.96 points (11 mins 33 secs) |
| Average Score | 308.40 (for 23 correct submissions) |
Let’s reform the validation formula. Let s be the total sum between every two points. Let overall(S) be the sum of all pairwise distances between any point in S and any other point (in S or not in S).
Now, inside(S) – outside(S) = overall(S) – s. Why? Let divide pair of points to three parts:
- One from S, another from S: in overall(S), this distance counted twice. In s, it subtracted once.
- One from S, another from outside of S: counted once in overall(S), subtracted once in s.
- One from outside of S, another from outside of S: never counted in overall(S), once counted in s.
Let’s calculate sum[i], the sum of distances from i to every point. Sort points. sweep from left to right and for each point calculate its x difference to all other points. Same for y.
Now, sort points by their sum. Add them one by one while overall(S) – s <= k.
Code by tourist:
int MaxPoints::findMaxPoints(int N, vector <int> XG, vector <int> YG, long long K, int seedX, int seedY) {
vector<long long> A(N);
A[0] = seedX;
for (int i = 1; i < N; i++) {
A[i] = (A[i - 1] * 1103515245 + 12345) % 2147483648LL;
}
vector<int> X(N);
for (int i = 0; i < (int) XG.size(); i++) {
X[i] = XG[i];
}
for (int i = (int) XG.size(); i < N; i++) {
X[i] = (A[i] % 2000001) - 1000000;
}
vector<long long> B(N);
B[0] = seedY;
for (int i = 1; i < N; i++) {
B[i] = (B[i - 1] * 1103515245 + 12345) % 2147483648LL;
}
vector<int> Y(N);
for (int i = 0; i < (int) YG.size(); i++) {
Y[i] = YG[i];
}
for (int i = (int) YG.size(); i < N; i++) {
Y[i] = (B[i] % 2000001) - 1000000;
}
vector<long long> sum(N);
for (int rot = 0; rot < 2; rot++) {
vector<pair<int, int>> xs(N);
for (int i = 0; i < N; i++) {
xs[i] = make_pair(rot == 0 ? X[i] : Y[i], i);
}
sort(xs.begin(), xs.end());
long long s = 0;
for (int i = 1; i < N; i++) {
s += xs[i].first - xs[0].first;
}
for (int i = 0; i < N; i++) {
sum[xs[i].second] += s;
if (i < N - 1) {
s += (xs[i + 1].first - xs[i].first) * 1LL * (i + 1 - (N - i - 1));
}
}
}
sort(sum.begin(), sum.end());
long long cur = -accumulate(sum.begin(), sum.end(), 0LL) / 2;
if (cur > K) {
return -1;
}
int ans = 0;
for (long long s : sum) {
if (cur + s <= K) {
cur += s;
++ans;
}
}
return ans;
}
Guest Blogger
