 ## March 24, 2020 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;
}


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


a.poorakhavan

Guest Blogger

categories & Tags

UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close