Single Round Match 772 Editorials

PlusCastle 

Used as: Division Two - Level One:

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:

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:

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:

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:

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;
}