Video editorials for B, C, and D are available on ak2006's channel.
1844A - Subtraction Game
There exists a small $$$n$$$ where the second player can win.
If $$$a \ge 2$$$, then $$$n = 1$$$ works.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t,a,b;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
}
return 0;
}
1844B - Permutations & Primes
In order for $$$(l,r)$$$ to contribute to the primality, we must have $$$\operatorname{MEX}(a_l,\dots,a_r) \ge 2$$$, so there is some value $$$1$$$ between indices $$$l$$$ and $$$r$$$.
To maximize the number of pairs $$$(l,r)$$$ that contain the value $$$1$$$, we should put $$$1$$$ near the middle of the array.
To minimize the number of pairs $$$(l,r)$$$ where $$$\operatorname{MEX}(a_l,\dots,a_r) \ge 2$$$ but is not prime, we should put $$$2$$$ and $$$3$$$ at the ends of the array.
#include <bits/stdc++.h>
using namespace std;
int a[200000];
int main() {
int i;
int t,n;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
if (n == 1) printf("1\n");
else if (n == 2) printf("1 2\n");
else {
int c = 4;
fill(a,a+n,0);
a[0] = 2,a[n/2] = 1,a[n-1] = 3;
for (i = 0; i < n; i++) {
if (a[i] == 0) a[i] = c++;
}
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
}
}
return 0;
}
1844C - Particles
The answer is the sum of some subset of $$$c_1,\dots,c_n$$$. Think about which subsets are obtainable.
Consider the set of even-indexed particles and the set of odd-indexed particles.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
int c[200000];
int main() {
int i;
int t,n;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
for (i = 0; i < n; i++) scanf("%d",&c[i]);
int allneg = 1;
for (i = 0; i < n; i++) allneg &= (c[i] < 0);
if (allneg) printf("%d\n",*max_element(c,c+n));
else {
LLI ans1 = 0,ans2 = 0;
for (i = 0; i < n; i++) {
if (i & 1) ans1 += max(c[i],0);
else ans2 += max(c[i],0);
}
printf("%lld\n",max(ans1,ans2));
}
}
return 0;
}
1844D - Row Major
Describe, using a graph, all the pairs of characters in $$$s$$$ that need to be different.
Consider the smallest positive integer that does not divide $$$n$$$.
#include <bits/stdc++.h>
using namespace std;
char s[1000001];
int main() {
int i;
int t,n;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
int c = 1;
while ((n % c) == 0) c++;
for (i = 0; i < n; i++) s[i] = 'a'+(i % c);
s[n] = '\0';
printf("%s\n",s);
}
return 0;
}
1844E - Great Grids
Try to find a characterization of all great grids.
There are two approaches that lead to the same conclusion. Approach 1 is more clever and leads more easily to the conclusion, while approach 2 is perhaps more natural to consider. Feel free to read the hint towards the approach that sounds better.
Think of the letters as numbers modulo $$$3$$$ and look at differences of adjacent cells.
Draw a / or \ for each $$$2 \times 2$$$ subgrid connecting the equal letters, and look for patterns.
In either approach, we can associate a type to each row and column, which has one of two possibilities. The constraints correspond to a row and a column needing to have the same or different types.
The problem reduces to checking the $$$2$$$-colourability of a graph.
#include <bits/stdc++.h>
using namespace std;
typedef vector<pair<int,int> > vpii;
#define mp make_pair
#define pb push_back
vpii adjList[4000];
int colour[4000],bad = 0;
int doDFS(int u,int c) {
if (colour[u] != -1) {
if (colour[u] != c) bad = 1;
return 0;
}
colour[u] = c;
for (auto [v,e]: adjList[u]) doDFS(v,c^e);
return 0;
}
int main() {
int i;
int t,n,m,k;
int x1,y1,x2,y2;
scanf("%d",&t);
while (t--) {
scanf("%d %d %d",&n,&m,&k);
for (i = 0; i < k; i++) {
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1--,y1--,x2--,y2--;
adjList[min(x1,x2)].pb(mp(n+min(y1,y2),(x1+y1 != x2+y2)));
adjList[n+min(y1,y2)].pb(mp(min(x1,x2),(x1+y1 != x2+y2)));
}
fill(colour,colour+n+m,-1),bad = 0;
for (i = 0; i < n+m; i++) {
if (colour[i] == -1) doDFS(i,0);
}
printf(bad ? "NO\n":"YES\n");
for (i = 0; i < n+m; i++) adjList[i].clear();
}
return 0;
}
1844F1 - Min Cost Permutation (Easy Version)
Solve the case $$$c \ge 0$$$ first. There is a very simple description of the answer.
What is the answer when $$$c = 0$$$?
When $$$c \ge 0$$$, the answer is the array sorted in nondecreasing order.
When $$$c < 0$$$, the minimum cost is achieved by sorting the array in nonincreasing order, but this is not the lexicographically smallest. Try to greedily form the lexicographically smallest array one element at a time.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
int a[200000];
int main() {
int i,j;
int t,n,c;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&n,&c);
for (i = 0; i < n; i++) scanf("%d",&a[i]);
if (c >= 0) {
sort(a,a+n);
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
continue;
}
sort(a,a+n,greater<int>());
for (i = 0; i < n; i++) {
for (j = n-1; j > i; j--) {
LLI diff = -abs(a[j]-a[j-1]-c);
if (j < n-1) {
diff -= abs(a[j+1]-a[j]-c);
diff += abs(a[j+1]-a[j-1]-c);
}
if (i == 0) diff += abs(a[i]-a[j]-c);
else {
diff -= abs(a[i]-a[i-1]-c);
diff += abs(a[i]-a[j]-c);
diff += abs(a[j]-a[i-1]-c);
}
if (diff == 0) {
for (; j > i; j--) swap(a[j],a[j-1]);
}
}
}
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
}
return 0;
}
1844F2 - Min Cost Permutation (Hard Version)
These hints and solution continue from the solution for the easy version, so please read the solution for the easy version first.
We need to optimize the $$$\mathcal{O}(n^2)$$$ greedy with some data structures. There exist solutions with varying levels of data structure implementation depending on how much effort is put into characterizing the answer array. For a short solution, start by simplifying the formula $$$(*)$$$ (in the solution for the easy version) to get a cleaner description.
The condition is actually equivalent to ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$) and ($$$b_{k-1}-a_i \le |c|$$$).
Maintain a linked list of the unused entries of $$$a$$$ and a set of unused entries that satisfy ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$).
1844F2 - Min Cost Permutation (Hard Version)
Let $$$c < 0$$$.
We now simplify condition $$$(*)$$$, which involves considering a few cases depending on the sign of the terms. It turns out that the condition is equivalent to ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$) and ($$$b_{k-1}-a_i \le |c|$$$) (for full details, see the overall proof below).
Sort $$$a$$$ in nonincreasing order so that $$$a_1 \ge a_2 \ge \dots \ge a_n$$$. We can simulate the greedy algorithm from the easy version with the help of a linked list of the unused elements of $$$a$$$ and a set of $$$a_i$$$ which satisfy the first part of the condition, ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$). Here, $$$a_{i-1}$$$ and $$$a_{i+1}$$$ actually refer to the closest unused elements of $$$a$$$, which are $$$a_i$$$'s left and right pointers in the linked list, respectively.
Each time, we query the set for its smallest element $$$a_i$$$ that satisfies $$$a_i \ge b_{k-1}-|c|$$$. If this element does not exist, then we take $$$a_i$$$ to be the largest element in the linked list. Then, we set $$$b_k := a_i$$$, delete $$$a_i$$$ from the linked list, and update the set with the left and right elements of $$$a_i$$$ if they now satisfy the condition.
One small observation is that in the answer $$$b$$$, $$$b_1 = a_1$$$ and $$$b_n = a_n$$$. This may simplify the implementation since it means that some edge cases of $$$(*)$$$ actually don't need to be checked. It is also actually not necessary to check the $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$ condition.
The time complexity is $$$\mathcal{O}(n \log n)$$$.
The case $$$n \le 2$$$ is trivial. In the following, we only consider the case $$$c < 0$$$ and $$$n \ge 3$$$. The case $$$c \ge 0$$$ follows by symmetry (reverse the array).
Let $$$c' := -c$$$ to reduce confusion with negative signs, and WLOG let $$$a_1 \ge a_2 \ge \dots \ge a_n$$$.
Instead of considering $$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$, consider a permutation $$$b$$$ that minimizes the augmented cost $$$|b_1-b_n-c|+\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$. By circular symmetry, WLOG rotate $$$b$$$ so that $$$b_n = a_n$$$.
We will perform a sequence of steps to sort $$$b$$$ in nonincreasing order without ever increasing the augmented cost. Consider looking at $$$b_{n-1},b_{n-2},\dots,b_1$$$ in order, such that when we look at $$$b_k$$$, we have the invariant that $$$b_{k+1} \ge b_{k+2} \ge \dots \ge b_n = a_n$$$. If $$$b_k \ge b_{k+1}$$$, do not do anything. Otherwise, since $$$b_k \ge a_n = b_n$$$, there exists an index $$$k+1 \le i < n$$$ such that $$$b_i \ge b_k \ge b_{i+1}$$$. Consider deleting $$$b_k$$$ from the array and reinserting it between index $$$i$$$ and $$$i+1$$$. We have the following results:
Claim 1: Deleting $$$b_k$$$ decreases the augmented cost by at least $$$c'$$$.
Proof: Let $$$x := b_{k-1}-b_k$$$ (or $$$b_n-b_1$$$ if $$$k = 1$$$) and $$$y := b_{k+1}-b_k \ge 0$$$. We need to check that $$$|x-y-c'|+c' \le |x-c'|+|-y-c'|$$$, which follows from $$$|x-c'|+|-y-c'| = |x-c'|+y+c' \ge |x-y-c'|+c'$$$ (we use the triangle inequality in the last step).
Note that equality holds if and only if $$$x-c' \le 0$$$, i.e. $$$b_{k-1}-b_k \le c'$$$.
Claim 2: Reinserting $$$b_k$$$ increases the augmented cost by at most $$$c'$$$.
Proof: Let $$$x := b_i-b_k \ge 0$$$ and $$$y := b_k-b_{i+1} \ge 0$$$. We need to check that $$$|x-c'|+|y-c'| \le |x+y-c'|+c'$$$. Consider four cases:
- If $$$x,y \ge c'$$$, then $$$|x-c'|+|y-c'| = x+y-2c' < (x+y-c')+c' = |x+y-c'|+c'$$$.
- If $$$x \ge c', y \le c'$$$, then $$$|x-c'|+|y-c'| = x-y \le (x+y-c')+c' = |x+y-c'|+c'$$$.
- If $$$x \le c', y \ge c'$$$, then $$$|x-c'|+|y-c'| = y-x \le (x+y-c')+c' = |x+y-c'|+c'$$$.
- If $$$x,y \le c'$$$, then $$$|x-c'|+|y-c'| = 2c'-x-y = (c'-x-y)+c' \le |x+y-c'|+c'$$$.
Note that equality holds if and only if $$$x = 0$$$ or $$$y = 0$$$ or $$$c'-x-y \ge 0$$$, i.e. $$$b_i-b_{i+1} \le c'$$$ or $$$b_i = b_k$$$ or $$$b_k = b_{i+1}$$$.
Therefore, each step does not increase the augmented cost. After all the steps, $$$b$$$ will be sorted in nonincreasing order. Therefore, the smallest possible augmented cost is $$$|a_1-a_n-c|+\sum_{i=1}^{n-1} |a_{i+1}-a_i-c|$$$.
Now note that $$$|a_1-a_n-c| = (a_1-a_n)+c'$$$ is the maximum possible value of $$$|b_1-b_n-c|$$$! This means that the minimum cost cannot be less than the minimum augmented cost minus $$$(a_1-a_n)+c'$$$. It follows that the minimum cost is obtained by sorting $$$a$$$ in nonincreasing order, and furthermore, any optimal permutation $$$b$$$ satisfies $$$b_1 = a_1$$$ and $$$b_n = a_n$$$.
Furthermore, suppose we have fixed $$$b_1,\dots,b_k$$$ and also $$$b_n = a_n$$$. By a similar argument (looking at $$$b_{n-1},\dots,b_{k+1}$$$ and reinserting them to the right), one optimal permutation $$$b_{k+1},\dots,b_n$$$ of the remaining elements is to sort them in nonincreasing order. Our greedy algorithm can only reach states where the optimal remaining permutation satisfies $$$b_n = a_n$$$, so it is correct.
Note that condition $$$(*)$$$ is similar to equality being achieved in both claim 1 and claim 2. It follows that $$$(*)$$$ is equivalent to ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$) and ($$$b_{k-1}-a_i \le |c|$$$) as claimed.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define mp make_pair
int a[200000],b[200000],l[200000],r[200000];
set<pii> S;
int main() {
int i;
int t,n,c;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&n,&c);
for (i = 0; i < n; i++) scanf("%d",&a[i]);
if (c >= 0) {
sort(a,a+n);
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
continue;
}
sort(a,a+n,greater<int>());
b[0] = a[0];
for (i = 0; i < n; i++) l[i] = (i+n-1) % n,r[i] = (i+1) % n;
for (i = 2; i < n-1; i++) {
if (a[l[i]]-a[r[i]] <= -c) S.insert(mp(a[i],i));
}
for (i = 1; i < n; i++) {
int u;
auto it = S.lower_bound(mp(b[i-1]+c,0));
if (it == S.end()) u = r[0];
else u = it->second,S.erase(it);
b[i] = a[u];
int x = l[u],y = r[u];
r[x] = y,l[y] = x;
S.erase(mp(a[x],x)),S.erase(mp(a[y],y));
if ((x != 0) && (l[x] != 0) && (r[x] != 0) && (a[l[x]]-a[r[x]] <= -c)) S.insert(mp(a[x],x));
if ((y != 0) && (l[y] != 0) && (r[y] != 0) && (a[l[y]]-a[r[y]] <= -c)) S.insert(mp(a[y],y));
}
for (i = 0; i < n; i++) printf("%d%c",b[i],(i == n-1) ? '\n':' ');
}
return 0;
}
1844G - Tree Weights
Model the problem as a system of linear equations.
Let $$$x_u$$$ be the sum of the weights of the edges on the path from node $$$1$$$ to node $$$u$$$. The equations are of the form $$$x_i + x_{i+1} - 2x_{\text{lca}(i,i+1)} = d_i$$$.
The intended solution does not do anything like attempt to maintain paths/virtual trees of known weight. One easily overlooked detail that is essential to the solution is that $$$x_i$$$ are integers.
Solve the equations modulo $$$2$$$ first, so that the $$$2x_{\text{lca}(i,i+1)}$$$ term disappears.
After solving the equations modulo $$$2$$$, we can similarly solve modulo $$$4$$$, $$$8$$$, etc.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
typedef vector<pair<int,int> > vpii;
#define mp make_pair
#define pb push_back
vpii adjList[100000];
LLI d[100000];
int parent[100000][17],parenti[100000],depth[100000];
int doDFS(int u,int p,int d) {
parent[u][0] = p,depth[u] = d;
for (auto [v,i]: adjList[u]) {
if (v != p) parenti[v] = i,doDFS(v,u,d+1);
}
return 0;
}
int logn;
int lca(int u,int v) {
int i;
if (depth[u] < depth[v]) swap(u,v);
for (i = logn-1; i >= 0; i--) {
if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
}
if (u == v) return u;
for (i = logn-1; i >= 0; i--) {
if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
}
return parent[u][0];
}
int lcas[100000],bit[100000];
LLI ans[100000],w[100000];
int main() {
int i;
int n,u,v;
scanf("%d",&n);
for (i = 0; i < n-1; i++) {
scanf("%d %d",&u,&v);
u--,v--;
adjList[u].pb(mp(v,i));
adjList[v].pb(mp(u,i));
}
for (i = 0; i < n-1; i++) scanf("%lld",&d[i]);
int j;
doDFS(0,-1,0);
for (i = 1; (1 << i) < n; i++) {
for (j = 0; j < n; j++) {
if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
else parent[j][i] = -1;
}
}
logn = i;
for (i = 0; i < n-1; i++) lcas[i] = lca(i,i+1);
for (i = 0; i < 57; i++) {
bit[0] = 0;
for (j = 0; j < n-1; j++) bit[j+1] = bit[j]^(d[j] & 1);
for (j = 0; j < n-1; j++) d[j] = (d[j]-bit[j]-bit[j+1]+2*bit[lcas[j]])/2;
for (j = 0; j < n; j++) ans[j] |= ((LLI) bit[j] << i);
}
for (i = 0; i < n-1; i++) {
if (d[i] != 0) {
printf("-1\n");
return 0;
}
}
for (i = 1; i < n; i++) {
w[parenti[i]] = ans[i]-ans[parent[i][0]];
if (w[parenti[i]] <= 0) {
printf("-1\n");
return 0;
}
}
for (i = 0; i < n-1; i++) printf("%lld\n",w[i]);
return 0;
}
1844H - Multiple of Three Cycles
The partially formed permutation is composed of several paths and cycles. Only the length of each path/cycle modulo $$$3$$$ matters.
The problem reduces to the following: Given $$$a$$$ $$$1$$$s, $$$b$$$ $$$2$$$s, and $$$c$$$ $$$0$$$s, how many ways are there to build a permutation on these objects so that each cycle sums to a multiple of $$$3$$$? Let $$$f(a,b,c)$$$ be the answer. Write some dynamic programming recurrences for $$$f(a,b,c)$$$.
Note that $$$f(a,b,c) = (a+b+c)f(a,b,c-1)$$$ (choose the next object of any $$$0$$$ and merge them).
This allows us to eliminate the $$$c$$$ parameter, multiplying the answer by a factorial and inverse factorial.
Let $$$f(a,b) = f(a,b,0)$$$. Write down not one, but two recurrence relations $$$f(a,b)$$$ satisfies.
We have $$$f(a,b) = b(a+b-1)f(a-1,b-1) + (a-1)f(a-2,b+1)$$$ when $$$a > 0$$$ (choose the next object of any $$$1$$$ and merge them) and also $$$f(a,b) = a(a+b-1)f(a-1,b-1) + (b-1)f(a+1,b-2)$$$ when $$$b > 0$$$ (choose the next object of any $$$2$$$ and merge them).
These recurrences mean that given any two of $$$f(a,b),f(a-1,b-1),f(a+2,b-1),f(a-1,b+2)$$$, we can solve for the other two.
Consider the pairs $$$(a,b)$$$ that arise from the $$$n$$$ queries. These pairs can be visualized as a walk in the plane, where each each pair does not differ from the previous pair by much. If we carefully use the recurrences to solve for values of $$$f(a,b)$$$ from values we already know, we can answer all queries on this walk while calculating only $$$\mathcal{O}(n)$$$ values of $$$f(a,b)$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
#define MOD 998244353
int parent[300000],siz[300000];
int find(int n) {
if (parent[n] != n) parent[n] = find(parent[n]);
return parent[n];
}
int queries[600000][3],ans[600000];
int fact[300000],invfact[300000],invn[300000];
int inv(int n) {
int e = MOD-2,r = 1;
while (e > 0) {
if (e & 1) r = ((LLI) r*n) % MOD;
e >>= 1;
n = ((LLI) n*n) % MOD;
}
return r;
}
int main() {
int i;
int n,x,y,bad = 1e9;
int num[3];
scanf("%d",&n);
for (i = 0; i < n; i++) parent[i] = i,siz[i] = 1;
num[0] = 0,num[1] = n,num[2] = 0;
for (i = 0; i < n; i++) {
scanf("%d %d",&x,&y);
x--,y--;
if (find(x) != find(y)) {
num[siz[find(x)] % 3]--;
num[siz[find(y)] % 3]--;
siz[find(y)] += siz[find(x)];
parent[find(x)] = find(y);
num[siz[find(y)] % 3]++;
}
else if ((siz[find(x)] % 3) == 0) num[0]--;
else if (bad == 1e9) bad = i;
copy(num,num+3,queries[i]);
}
fact[0] = 1;
for (i = 1; i < n; i++) fact[i] = ((LLI) i*fact[i-1]) % MOD;
invfact[n-1] = inv(fact[n-1]);
for (i = n-2; i >= 0; i--) invfact[i] = ((LLI) (i+1)*invfact[i+1]) % MOD;
for (i = 1; i < n; i++) invn[i] = ((LLI) invfact[i]*fact[i-1]) % MOD;
int m = n;
while (num[1]+num[2] > 0) {
int a = (num[1] > 0) ? 1:2;
num[a]--;
int b = (num[1] > 0) ? 1:2;
num[b]--;
num[(a+b) % 3]++;
copy(num,num+3,queries[m++]);
}
x = 1,y = 1;
int u = 1,v = 8;
auto f = [&]() {
assert(x > 0);
int nu = (((v-(((LLI) (y+1)*(x+y+1)) % MOD)*u) % MOD)*invn[x]) % MOD;
int nv = ((((LLI) x*(x+y+2)) % MOD)*nu+(LLI) (y+2)*v) % MOD;
x--,y += 2,u = nu,v = nv;
if (u < 0) u += MOD;
if (v < 0) v += MOD;
};
auto g = [&]() {
assert(y > 0);
int nu = (((v-(((LLI) (x+1)*(x+y+1)) % MOD)*u) % MOD)*invn[y]) % MOD;
int nv = ((((LLI) y*(x+y+2)) % MOD)*nu+(LLI) (x+2)*v) % MOD;
x += 2,y--,u = nu,v = nv;
if (u < 0) u += MOD;
if (v < 0) v += MOD;
};
for (i = m-1; i >= 0; i--) {
int a = queries[i][1],b = queries[i][2],c = queries[i][0];
if ((a == 0) && (b == 0)) ans[i] = 1;
else if ((a == x) && (b == y)) ans[i] = u;
else if ((a == x-1) && (b == y+2)) f(),ans[i] = u;
else if ((a == x+2) && (b == y-1)) g(),ans[i] = u;
else if ((a == x+1) && (b == y+1)) {
if (x > 0) f(),g(),ans[i] = u;
else g(),f(),ans[i] = u;
}
else assert(0);
ans[i] = ((LLI) ans[i]*fact[a+b+c]) % MOD;
ans[i] = ((LLI) ans[i]*invfact[a+b]) % MOD;
}
for (i = 0; i < n; i++) printf("%d\n",(i >= bad) ? 0:ans[i]);
return 0;
}
Siyuan Cheng's last minute submmision..DAMN!!!
Nice contest and a very fast tutorial. Really amazing.
So fast tutorial
don't get fooled tutorial is not available.
implementation is there at least which is better than last time
amazing E&&F
Problem A: a + b.
True
lol I did smthg else. 3 cases
did Same Thing :)
I was scared of submitting my answer because it was so weird for me.
best contest ever <3
Agree
Contest is too Speedforces that even editorial got posted on fast
so fast :O
fast editorial :)
nice pfp :)
I was quite frustrated because continuously got WA on C while using dp :(
However, that means im still too stupid, need to practice more.
agree
ya did the same :(, where you able to find out why the dp solution fails here?
well, i sadly couldnt generate my wrong case bro... xd.
Same. It took me a while to eventually land on the correct solution.
Here's my DP solution for C :
Consider DP[i] to be the largest bubble you can have to be fused, on the left of the (i + 1)th, (i + 2)th, ..., (n — 1)th bubbles
When you're facing a big bubble at spot i, and the next bubbles in line, you have three choices :
Eliminate the i-th bubble, which gives DP[i + 1] >= Bubble[i + 1], since you removed everything on the left of (i + 1)th bubble
Fuse the i-th bubble with the (i + 2)th, which gives DP[i + 2] >= DP[i] + Bubble[i + 2]
And the final tricky choice : Keep the i-th bubble to be fused later, and therefore eliminate bubbles (i + 1) and (i + 2) at some point in the process, which gives DP[i + 2] >= DP[i]
In the end you get a DP that simply calculates the magic sum of the editorial, but that's the way I found it anyway
Implementation is pretty straightforward : https://codeforces.com/contest/1844/submission/213325940
In the code statement
DP[i + 2] = max(DP[i], max(DP[i + 2], DP[i] + Val[i + 2]));
could you please explain, why are we checking the maximum DP[i] parameter?
Have a look
I had a hard time with implementation of E
Can you explain me the last sample test for E? why is it NO?
You can simply try it.. There is no possible answer grid for that condition
super fast editorial sheesh!
Thanks for the good problems and amazing fast editorial! Quite a high-quality round, many interesting problems. However, the problem diversity is not that high with most of the problems ad-hoc and constructive, while not including many algorithms in the first 5 or 6 problem. Anyway, great job and wish you can make the problem more diversed next time!
In first prb if a=1 b=2 how n must be 3, 2 also right answer I'm correct.bcz 1st player Play game n =1 second player play n = 0 so 3rd turn 1st player failed.
If player one choses 2 than n = 0 so player 2 would lose
If there are multiple solutions, you can output one of them. Because this problem use Special Judge.
How to come up with the solution of G? Or is there any similar problem?
Apparently, problem I from AIM Tech poorly prepared contest was very similar, at least in terms of solution
I don't know much about trees, but I know they love bit opeations (e.g., binary lifting). Probably the most common thing is the XOR an a path problem. So it stands to reason to solve the problem in $$$\mathbb{Z} / 2\mathbb{Z}$$$ first. After that, it's kinda straightforward.
Will tourist be the king again?
The saddest thing happened right now. An FST in prob C preventing me from reaching CM for the stupidest bug.
I initialized ma = -1e9 + 1 instead of -1e9-1. :cry:
UPD: The +70 delta is now -111
Feeling Bad For You :(
Can anyone explain how we are creating graph out of the coordinates in problem E? More specifically, how the following 2 lines are creating the graph with the property mentioned in the tutorial?
adjList[min(x1,x2)].pb(mp(n+min(y1,y2),(x1+y1 != x2+y2)));adjList[n+min(y1,y2)].pb(mp(min(x1,x2),(x1+y1 != x2+y2)));problem A...
Has anyone solved c using dp , out of curiosity
Here is my submission，hope it helps you: 213365683
could you please explain the dp logic
I did the same thing after the contest. It is pretty much calling a array dp and calculating the max sum subsequence with it aka the solution in the editorial.
Here the only submission that really uses dp, atlest the only one I have found:213325940
Ye sayad sayad dp ni h ,Khali tumne dp vector use Kiya h
can you explain the code also plxx
This is my submission of D during contest. As one can see it fails on test 15's case 16. However this test case is n = 2 which was also present on sample as well as some of the previous tests. Then why does it show wrong answer only on test 15 ? (It passed pretests during contest but now its showing FST).
Your solution is same as tourist. So you must look at his solution. Maybe then you will be able to find the error
Got it. Thanks. I initialized with n even before taking n as the input.
lmao
can you help me out in this 213442767 is mine getting WA on test 2 but the same code in c++ 213442685 getting accepted why, somebody please help me out.
well, there is a greedy solution for F in $$$O(n)$$$ (but after sorting).
the main idea is to keep checking "is choosing a smaller number able to remain the value unchanged?": if yes then go check the next one, otherwise construct a sequence using those larger numbers just checked.
here is the submission.
orz
But there's a $$$O(n\log n)$$$ sort in the beginning QwQ
Oh yeah, I just didn't notice that QAQ. Then it is $$$O(n)$$$ only when the list is given ordered. thx!
Tutorial with hints are BEST!!!
"the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow" Could anyone explain why it is so? Greatly appreciated
Here is the idea of the proof, but some parts are omitted.
The $$$2 \times 2$$$ submatrix must look like
where $$$x, y, z \in \{0, 1, 2\}$$$ (or the mirror image of that, but the two cases are identical and thus, it is enough to consider this one case).
Every submatrix must contain all three values $$$\Rightarrow x \neq y \neq z \neq x$$$
Now there are two cases
Case 1: Top row difference $$$x - y \equiv 1 \pmod 3$$$
$$$x \equiv y + 1 \pmod 3$$$
Now, since $$$y \equiv y$$$ and $$$x \equiv y + 1$$$, $$$z$$$ must have the remaining value, i.e. $$$z \equiv y + 2$$$.
This means that the difference on the bottom row is $$$y - z \equiv y - (y + 2) \equiv -2 \equiv 1 \pmod 3$$$, which is equal to the difference on the top row. We can see that the difference on the left column is equal to the difference on the top row and the difference on the right column is equal to the difference on the bottom row. Thus, the differences on the left column and the right column are equal.
Case 2: Top row difference $$$x - y \equiv 2 \pmod 3$$$ can be handled in the exact same way as above and we will end up with the same conclusion.
Congrats on Becoming GrandMaster vgtcross
The fact is that the difference in the tutorial is unidirectional instead of abs hah
How can one easily prove F?
Can someone give proof for this in problem F?
"When c≥0 , it can be proven that the minimum cost can be obtained by sorting a in nondecreasing order."
You can change the form of summation by first supposing all $$$b_{i+1}-b_i \leq c$$$ and then compensate those $$$b_{i+1}-b_i > c$$$ twice:
So we need (least $$$i$$$ with $$$b_{i+1} - b_i > c$$$) and ($$$\sum (b_{i+1} - b_i - c)$$$), and a sorted $$$b$$$ certainly satisfies.
This explanation is so good that it has to be in the editorial. Thanks a lot!
orz fast editorial!! I only was able to solve Problems A and D (had to leave after 2 hours of competition) but very fun round, almost had Problem C's solution!
my performance predictor showing infinite level performance by Global Rank 1....!!! Insane.
I belive it calculates the performance relative to the performance of the top place and thats why.
I thought D was going to be some awful construction or brute force but after looking at the proof I am amazed. Really pretty proof. I got the clique idea but couldn't construct a string with that number of characters
Simply factoring and then calculating mex of all characters that are $$$d$$$ positions before, where $$$d$$$ is a divisor of $$$n$$$. Doesn't feel as a D
will that not give a time complexity of Nroot(N), something to avoid when constraint is 1e6
It's not $$$Nsqrt(N)$$$, only $$$N$$$ times the number of divisors of $$$N$$$, which isn't more than $$$240$$$. With little optimisations it runs fast enough to pass the time limit. My code runs in 717ms
Hmm, thanks.
Also, this was helpful: link
can you explain this solution a bit more. I don't understand your code and it seems much simpler than the solution that I have in mind.
The solution I have in mind is find the divisors of N. Then iterate over n incrementing s[i+divisor] for each divisor by 1 if it is the same as s[i]. The problem I have with this solution is that it isn't clear to me why that finds the minimum number of distinct elements. To give a specific example that trouble me, if s[i] is 1, and s[i + divisorA] is 0, s[i+divisorA] will not be incremented. However, for an index j where i<j<i+divisorA, and a divisor divisorB such that j+divisorB = i+divisorA, couldn't index j increment j+divisorB which make s[i] equal to index s[i+divisorA].
I know that I didn't express my doubt very clearly but I hope you understand what I am worried about.
still newbie orz
Amazing contest! Learnt some stuffs. Problems were well-designed and of high quality. Kudos to duality!
Why no one is thinking DP for E ? I spent hours debugging my code but not sure why dp won't work.
dp[i][j][c] -> is it possible to color position (i,j) with color c ?
duality orz
I hate constructive algorithms :(
in F: When c≥0 , it can be proven that the minimum cost can be obtained by sorting a in nondecreasing order. As sorting a in nondecreasing order is also the lexicographically smallest array, this is the answer.
how?
Feedback on the problems:
A: Good easy problem. I liked that there were multiple meaningfully distinct paths to the solution.
B: Fine for its position.
C: Fine for its position. Despite the fact that the bulk of the problem was making the necessary observation (i.e. we can take any subset of the odds or any subset of the evens), the proof of the observation is fairly straightforward once you've made it, meaning it didn't feel like I was trying for a proof by AC.
D: Okay problem (although I'm embarrassed by the way I solved it...). I think it might have been good to use a somewhat harder task in this position to smooth the gap between C and E, and also to avoid having four one-trick problems at the beginning of the contest.
E: Excellent problem; one of my favorites at its difficulty level in recent memory. The process of solving the problem was satisfying in a similar way to a good challenging OI problem: I felt like I was gradually making observations that improved my understanding of the problem's setup, eventually leading to a solution. Most problems that are similarly satisfying are much harder than this one is, so it's impressive to write a task this interesting that's still suitable as problem E.
F: Great problem. Like E, I found the process of making conjectures to gradually understand the problem very satisfying. This was also a good use of a subtask, and the score distribution between the two subtasks seems reasonable.
G: Great problem. The idea to get rid of the $$$2 \cdot x_{lca}$$$ term by taking the equation mod $$$2$$$ is brilliant. I've heard some people have seen similar ideas before, but the solution was completely new to me (and I was not even close to solving the problem in-contest).
H: Didn't read during the round.
The statements were clear, and it looks like there were relatively few FSTs. Moreover, the editorial is well-written; I appreciate that most proofs are included and that hints are provided for all problems. The gap between D and E was a bit large, but it's very difficult to get the difficulty distribution just right, so this is far from a round-ruining issue. Thanks to the author and the coordinator!
thanks for the feedback, can I know what is your thought process solving E?
Here's an outline of my solution path. Note that this will likely be less comprehensible than the editorial.
I noticed that if you know three of the letters in a 2x2 grid, you can uniquely determine the fourth. This implies that if we fix the first row and the first column, these uniquely determine how to fill in the rest of the grid. From there, I started drawing out possible first rows and analyzing the possibilities for the second rows (based on the two choices of which letter appears first in the second row), and I found that each row must be equal to the last except with each letter shifted forward (i.e. A's turn into B's, B's turn into C's, C's turn into A's) or backward (i.e. A, B, and C turn into C, A, and B).
Then, I looked at which diagonal contains two equal elements in each 2x2 grid. I found that in one of the two cases, the diagonals in the next row have the same orientation as the diagonals in the last, while in the other case the diagonals in the next row have the opposite orientation of the corresponding diagonals in the last row. In other words, we can pick arbitrary orientations for all diagonals in the top two rows, and then for each subsequent row, we can either flip the orientation of all diagonals or keep them all the same.
From there, I realized this is equivalent to the graph coloring problem described in the editorial (largely because I've seen the same general idea many times in the past). Big picture, the idea is that if we have one boolean for each column representing whether the first 2x2 grid corresponding to that column has identical letters on the main diagonal or the off diagonal, and another boolean for each row representing whether the diagonals in that row are flipped or not, then saying that a given 2x2 grid needs to have equivalent elements on a specific diagonal tells us whether the boolean variables for the corresponding row and column must be the same or distinct.
Given a number of booleans and various requirements that they must be equivalent or distinct, we can detect whether a valid assignment of true/false values to the variables exists by creating a graph in which the variables are vertices and the constraints are edges. We can then repeatedly assign some variable an arbitrary value, use BFS or DFS to determine the value of all other variables in the same connected component, and check whether the resulting assignment is valid.
Geothermal Thank you for such a good explanation. Honestly speaking, I wasn't able to understand the editorial even after reading it multiple times, but your explanation was very clear and intuitive as well. I wish you start uploading on Youtube once again.
Draw some cases.
Notice that it looks like row[i+1] is row[i] but +1 or -1 mod 3.
Same thing for column.
Remember similar problems. It turns into a sort of xor 2sat with variables being the difference between consecutive rows and columns.
you said remember similar problems, can you suggest some please? it's new to me.
Problems about a binary matrix where c[i][j] = r[i] ^ c[j]. There are many problems like that but I won't go look for a link.
Thank you for the feedback!Can you explain the proof for n>=3 in problem B?
In general if we don't include 1 in the sub array then mex will be 1 which is not prime. so we want it to be in the center so that it will be in most of the sub arrays. Now 2 and 3 are primes so by including 1 we want them to be not included. so lets keep them at the ends so that less sub arrays include 2 and 3 . In general if we elements are at end then least sub array will be there including them. Finally , if 1 is there in the sub array then except for 1 case (that is including all elements) 2 or 3 will not be there in any of the sub array . Ans — 2 ---- 1 ---- 3 remaining elements can be anything.
Can you share your idea for F1 please? In particular I don't understand why we fix the maximum element as the 1st element for c<0 case.
In the editorial for E it says that "the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow" in each 2x2 subgrid. Am I understanding this wrong or should it be that the top/left arrows and the bottom/right arrows are the same?
I really like problem G. Its intended solution is nice and elegant. Special thanks for this one.
Could anyone suggest similar problems to problem E (easier preferably) ?
i feel bad because i'm newbie, for third question i have idea same the tutorial but i don't write it down...
problem E is really nice!
can you explain the solution? and suggest some similar problems on this method?
First, we draw a line between two cells sharing a unique corner, then there is a unique line in each 2 × 2 subgrid.
let $$$a_{i,j}$$$ be $$$0$$$ if there is a line connecting $$$(i,j),(i+1,j+1)$$$, and $$$1$$$ if there is a line connecting $$$(i,j+1),(i+1,j)$$$. Some $$$a_{i,j}$$$s are given, and we should fill the rest. a key observation is, if $$$a$$$ is valid, then $$$\forall i \in [1,n),j \in [1,m)$$$, the sum of $$$a_{i,j},a_{i,j+1},a_{i+1,j},a_{i+1,j+1}$$$ is even. That also means, there exists an array $$$f$$$ and an array $$$g$$$ consisting of $$$0$$$ and $$$1$$$, satisfying $$$f_i \oplus g_j = a_{i,j}$$$, here $$$\oplus$$$ means the bitwise xor.
if $$$a_{i,j}$$$ is given, then add an edge between $$$f_i$$$ and $$$g_j$$$. For each component, check if it's able to construct. The time complexity is $$$O(\sum n+m+k)$$$.
Such a bad contest. The difference in difficulty between D and E is absurd.
What is the reason for you to cheat to provide your fake rating "for cheaters"):
beg for a proof of F. :(
Can anyone explain the proof for n>=3 in problem B
You need max primality, so maximum no of subarrays with mex as prime. Which prime numbers are easiest to get in an mex? It's 2 and 3. But to get to 2 (or 3) as MEX you need 1 in the subarray as well. If you think about it, an element can affect the maximum subarrays if its in the middle of the array. At the ends of an array, you have n subarrays you can construct using the first (or last) element of an array. However, this number goes up as we go towards the middle and maximises at the centre. Hence, you take 1 as the middle element. Now you need to make sure 2 and 3 together are included in the least number of subarrays (since MEX will then come out as 4, which is not a prime). How do you do that? By taking them as the first and last element in the array.
Got it brother.Thank you for explaining it:)
I calculated max subarray sum for even indices and odd indices and printed max of them in problem C , it got Ac
Subsequence
oh yeah , that means I git ac undeservingly
In premise of problem B, if instead of 1, the natural numbers started from any given integer, and the mex calculation also starts from that number itself, would it guarantee the solution, where you need to append the least two primes after the given integer in the front and the back of the array, will always result in a permutation which has maximum no. of subarrays which have prime mex ?
no , it wouldn't guarantee I think
For Problem C, would taking the max of maximum Subarray Sum of odd-indexed arrays and even-indexed arrays work?
I am unable to think of a countercase.
EDIT: I am a dumdum, Maximum Subset Sum is what we need not Maximum Subarray Sum! :(
G is one of the greatest problems I have ever seen. I solved it but I am still shocked that any problem can be solved like that... It just doesn't feel right... Fascinating!
I have proved the case of c>=0 through complex inequalities about F1, is there any simple proof or understanding?
A+BForces
Hi, anyone would like to study (code) together with me?
Can anyone explain me please how to prove the fact that nondecreasing order in case of c >= 0 (F task) gives optimal result? It makes sense, but i can't prove it formally for a long time
Problem F is pretty similar to 1685D2 - Permutation Weight (Hard Version), and is essentially a particular instance of this generalization, with the extra bit of finding the lexicographically minimal Euler tour a little faster by using the structure of the problem.
Can you please elaborate here? I am not able to understand it. Thanks in advance
Can anyone tell me what is wrong in this solution and why in problem F1 we include i+1 , i-1 's differnece , that does not make sense to me. Please help
My code:- 213562733
void solve(){ int n,c; cin>>n>>c;
vi v(n); fov(n,v); if(c>=0){ sort(v.begin(),v.end()); printArr(v); return; } sort(v.rbegin(),v.rend()); for(int i=0;i<n;i++) { int preCost=0,newCost=0; for(int j=n-1;j>i;j--) { if(v[j]>=v[i]) continue; if(i>0){ preCost = abs(v[i]-v[i-1]-c) + abs(v[i+1]-v[i]-c); newCost = abs(v[j]-v[i-1]-c) + abs(v[i+1]-v[j]-c); } else{ preCost = abs(v[i+1]-v[i]-c); newCost = abs(v[i+1]-v[j]-c); } if(j<(n-1)){ preCost = preCost+ abs(v[j]-v[j-1]-c) + abs(v[j+1]-v[j]-c); newCost = newCost+ abs(v[i]-v[j-1]-c) + abs(v[j+1]-v[i]-c); } else { preCost = preCost+abs(v[j]-v[j-1]-c); newCost = newCost+abs(v[i]-v[j-1]-c); } if(preCost==newCost) { swap(v[i],v[j]); break; } } } printArr(v);}
B's an interesting problem, could someone help me understand why in the solution MEX values of other primes such as 5,7,11,13 are not relevant to this solution? Like I get this construction maximizes the number of subarrays with MEX values 2 and 3, but somehow I thought the solution would involve finding each prime and trying to build a subarray that would contain each prime value in MEX as many times as possible.
Also the final remark
(note that we don't even need to sieve for primes!)given whatever the heck I did with this problem in the contest might be the most inadvertently cheeky and emotional damage inducing line in an editorial I've ever had to read.So first of all, every subarray not containing 1 is bad so we want to maximize number of subarrays containing 1(which is quite easy you just place it in the middle and get quadratic number of arrays containing it).So now we are looking only at subarrays that contain middle point. Idea is, because 2 and 3 are only connected primes in natural numbers, to use that fact to get all the subarrays that have middle to also have prime MEX like this: if we place 2 on the end of the array that means that ALL subarrays including 1 and not end of array(the '2') have MEX = 2(now we are left with only subarrays containing 2 which are also the suffix subarrays). Similarly we can put 3 on the other end and then even subarrays including 2 have MEX = 3. So now there only remains 1 subarray that we haven't made a prime MEX, which is full array, but that one doesn't matter cuz its MEX is anyway n + 1 so we can't make it prime if it ain't. Hope this helped :)
I have another interesting solution for problem E, which is O(n + m + k^2). Idea is as stated in a solution version 2, that if you have '/' it means right up corner is same as down left corner and as for '' if we reverse logic it means that right up corner is different than down left corner. Also, as stated, transitions in each row are either completely the same as in previous or completely reversed(try for yourselves). So now connections in a graph will be : are 2 slashes in same row equal or different(there are k^2 pairs of slashes max). After we create such a graph we can do simple 2-color search :)
My submission: 213578347
for E, editorial says:
The conditions imply that all labels are 1 or 2, and in each contiguous 2×2 subgrid, the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow.but, for example, in the subgrid below:
the top arow is 1 and the bottom arow is 2, their not the same. and the right arow is 2 while the left arow is 1.
can somebody explain?
Bottom arrow has value -2 (we are looking at the value modulo 3, not on the value module), and 1 == -2 modulo 3
Edited: the same thing with left and right arrows. It's important that if you count the value of left arrow as "bottom value — top value", then you should calculate the value of right arrow the same way (ignoring the negativity of the result)
I get it now. thank you very mutch.
I think the idea of G is a bit similar to what's explained in this Veritasuim's video.
This submission should not work. It is O(N^2). Someone hack it: 213539286.
I remember some time ago I came across this problem from leetcode which reminds problem C from this contest. It turns out that the problem linked has a DP solution of O(N^3) (there is also the video explanation in the first problem of this video by Errichto). However, I cant understand why the problem C from this contest has a demonstrated DP solution of O(n) (see for example the solution explained by JeanBombeur in the comments) while the leetcode problem linked has O(n^3) as optimal DP solution, despite the two problems are almost the same. Please, can somebody help me understand why the two problems are not solvable in the same way?
God damn, finally, i got the proof for statement in f-task (that non-decreasing order gives optimal result in case of c >= 0). Don't know if where is anyone who still have interest in this proof, but if you are — you are welcome (i will write it as the answer to this message, sorry if you won't understand, i'll try my best to explain)
Note that the order of values in A doesn't matter, so let the A array be already sorted. In that case, we can simply write a difference between all adjacent alements, and every difference will be no less than zero. So, let's define array D:
D[i] = A[i+1] - A[i], and as i just said,D[i] >= 0for all i.There also is an important picture representation of array A and it's random permutation: imagine the values from A as points on an integer line, now D[i] is the length of section between points A[i] and A[i+1]. Random permutation is now a sequence of jumps on this line, every jump ends at a not visited yet point, and every jump (starting from second) starts in the end of previous jump, first jump just starts at some A[i].
Every jump is a transition from B[i] to B[i+1] (for some i). Also, every jump has it's difference (i mean B[i+1] — B[i], let's define it as DB[i]), and is equal to some union of "elementary jumps" (by elementary jump i mean D[j] for any j). Declaring B[i] = A[f[i]], |DB[i]| = sum from (min(f[i], f[i+1])) to (max(f[i], f[i+1]) — 1) {D[j]}, and sign(DB[i]) = -1^(f[i+1] < f[i]).
First idea: there is a bijection between DB and D, satisfying the condition: for every comparison DB[i] <-> D[j] expression (min(f[i], f[i+1]) <= j && j < max(f[i], f[i+1])) is true. Other words, d[j] lies in the union of elementary jumps, which is equal to DB[i]. (If there is a misunderstanding, read the previous paragraph again, also drawing on paper might help)
Proof: let's take a look at the following invariant: before every jump we have a set of points, from which we haven't started a jump yet, we are standing in one of these points and between every such adjacent points there is exactly one elementary jump, which has not yet been used by the bijection construction algorithm. The algorithm is to jump from the first member of permutation to the last, and for each jump, match it to the first (in the direction of the jump) elementary jump that has not yet been used to it. It is easy to make sure that the invariant is not violated during the execution of the algorithm. (use a picture with integer line, and alternating sequence of points and elementaary jumps), after every jump we have one less point to jump to and one less elementary jump we can use in matching, but these two were adjacent on the line, so we can simply throw this pair out from the line).
Now, let's proof that any permutation is not better that non-decreasing order of A (from the point of view of the minimality of the amount |B[i+1] — B[i] — c|)
Note that we have 4 types of jumps in a random permutation: left/right and "matching elementary jump is < c / >= c". Matching elementary jump — from paragraph about bijection. Elementary jump < c means D[i] < c. The main idea is to compare value of function |B[i+1] — B[i] — c| on jump of permutation and matching elementary jumps.
Case: right jump, matching D[i] >= c. In that case elementary jump gives d[i] — c, permutation jump gives D[i] — c + (D[v1] + D[v2] + ... ). I mean that DB[j] for right jumps is equal to D[v] + D[v+1] + ... + D[u], for some u <= i <= v. So, right jumps are definitely not better than matching elementary jumps.
Case: right jump, matching D[i] < c. In that case we can get better result than matching elementary jump, but we can't reduce the value of (|B[j+1] — B[j] — c|) by more than min(c, DB[j] — D[i]). We will need this fact later, to proof that "casualities" on left jumps are not less than "profits" on right jumps with d[i] < c.
Case: left jump, matching D[i] >= c. In that case, elementary jump gives D[i] — c, while the "original" jump gives DB[i] + c, so the difference is DB[i] — D[i] + 2c, I.e. we took DB[i] as a union of elementary jumps, removed D[i] and added two segments of length S.
Last case: left jump, D[i] < c. In that case difference is equal to DB[i] + D[i].
So, why we can't make better result than with non-decreasing order? Let's fix a random permutation B, fix random elementary jump D[i], and check every permutation jump, "covering" (containing, other words) this elementary jump. Define x as the number of right jumps, containing this elementary jump, and y as the number of left jumps, -//-. Note that |x — y| <= 1.
If permutation jump (matched to fixed elementary jump) is right, then contribution of fixed elem. jump in decreasing the value of some right jumps <= (x-1)*D[i] (it decrease the value of every right jump, containing this elem. jump (not as a matching), but every decrease is no more than d[i]). In the same time, D[i] contribution in increasing values of every left jump, containing D[i] is equal to y*D[i] (because no one of these left jumps contains D[i] as matching). Since |x-y| <= 1, we can be sure that y*D[i] >= (x-1)*D[i] (other words, we didn't get any profit from this elementary jump)/
Otherwise, if matching permutation jump is left, then contribution of fixed elem. jump in decreasing the value of some right jumps <= x*D[i] (and if D[i] >= c, we can restrict it even stronger, with value x*c). On the other hand, contribution in increasing values of left jumps is equal to (y-1)*D[i] + 2*D[i] (in case of D[i] < c) and (y-1)*D[i] + 2*c (in case D[i] >= c). It's not hard to notice, that in both cases (D[i] < c / D[i] >= c) maximum increment value is not less than maximum decrement value.
Other words — we proved that there is no permutation with sum |b[i+1] — b[i] — c| less than non-decreasing order sum.
Yeah, i really like it then "can be proven" facts proof is several time bigger than the solution. However, if anyone has shorter and simplier proof — it would be very nice to get acquainted.
P.s. proof for c < 0 is obvious, multiply by -1 all A[i] and c, every module has not change it's value, but now c is > 0, so (-a[i]) should be sorted in non-decreasing order <=> a[i] should be sorted in non-increasing order.
might be late but I think you missed the proofs section of the editorial of F2
Oh really...
Sorry then, I definitely have a problem with attention :(
So unique for G's solution.
I have received a mail and a message from the codeforces system that my solution of problems A, B and C of codeforces round #884 Codeforces Round 884 (Div. 1 + Div. 2) coincides with a person with codeforces user handle Yash_1308.I came to see now that he was using my template in the previous round, which I had been using for the last one year. It is the case of some code pasted before the contest, and nothing was done during the contest.
Problem A: My submission 213301983 Problem A: His submission 213308099 Problem B: My submission 213315128 Problem B: His submission 213332212 Problem C: My submission 213338146 Problem C: His submission 213352663 I regularly give contests and use this template from around 30 previous contests. So, this shows that I am not a cheater, and I have neither provided any solution nor copied during the contest, which proves that I am not a cheater.
I would request MikeMirzayanov and duality to please look into the matter and remove my plag as I have not done anything wrong.
Great contest!
In the proof section in problem F2, "furthermore, any optimal permutation b satisfies b1=a1 and bn=an". Why is that the case?
In The 1st question output written is wrong which mislead the question. In 3rd case when a=9 and b=26 output will be 35 but it is written 3.
i am not able to understand the proof for problem B , can any one help with that...
Problem: Subtraction Game
Solution: a+b(addition)
Did someone solve G with virtual trees? We can image that a edge is connecting i to i+1,then we merge the n-1 "edge"s in some order and we will keep knowing all the value of "edge" in the virtue tree.But I don't know how to update the virtue tree.
What does MEX refers to in the problem number B?
My thought process on D:
- noticed that it is enough to just output $$$abababa\ldots$$$ for an odd $$$n$$$.
- noticed that $$$abcabcabc...$$$ always works for any $$$n$$$ as long as none of its divisors pickup a "full $$$abc$$$ part". So, it won't work if $$$n$$$ has divisors $$$3/6/9/...$$$
- Why so, because of cyclicity. Led me to thinking that we must avoid any letter repeating at a distance = any of the divisors of $$$n$$$.
- To minimise the number of characters, we will still have to have cyclicity in the string. So, lets make a string that is cyclic in the length = smallest number that is not a divisor of $$$n$$$.