There are many people cheating (including me :(). Why don’t cheaters get banned?

div2 D was so amazing problem!

div1D can be reduced to a well-known problem: finding MEX in a path. I wonder why only 2 participants solved this problem.

unrated?

Great problem 2174D LeoPro and proof for 2-swap is cool.

I solved it as follows

• Check if cheapest $$$N-1$$$ edges are disconnected.
• Standard 1-swap(brute-force)
• Top $$$K$$$ 2-swap(brute-force with $$$k=20$$$)

I changed one letter and my code was accepted in question C.

As the author of d1B, here's another solution:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int T,n,k,a[N];
void los(){
    cin >> n >> k;
    vector<vector<int>> dp(k + 1,vector<int>(k + 1,-1e9));
    vector<int> pos(k + 1);
    for(int i = 1;i <= n;i ++) cin >> a[i];
    dp[0][0] = 0; int j = 1;
    for(int i = 1;i <= k;i ++) for(;j <= n;j ++) 
        if(a[j] >= i){ pos[i] = j; break;}
    for(int i = 1;i <= k;i ++) for(int j = 1;j <= i;j ++) if(pos[j])
        for(int l = 0;l <= i - j;l ++)
            dp[i][j] = max(dp[i][j],dp[i-j][l] + (j - l) * (n - pos[j] + 1));
    int ans = 0;
    for(int i = 0;i <= k;i ++) for(int j = 0;j <= k;j ++)
        ans = max(ans,dp[i][j]);
    cout << ans << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1505,M = 1e5+5;
int T,n,k,a[M];
struct LCT{
    int mx[N],k[N],b[N],tot,cnt,ls[N],rs[N],rt;
    void clr(){
        for(int i = 0;i <= cnt;i ++) ls[i] = rs[i] = mx[i] = 0;
        tot = 0,cnt = 1,rt = 1,b[0]= -1e9;
    }int get(int x,int id){return k[id] * x + b[id];}
    void upd(int &s,int l,int r,int x){
        if(!s) s = ++cnt;
        int mid = (l + r) / 2;
        if(get(mid,x) > get(mid,mx[s])) swap(x,mx[s]);
        if(l == r) return ;
        if(get(l,x) > get(l,mx[s])) upd(ls[s],l,mid,x);
        if(get(r,x) > get(r,mx[s])) upd(rs[s],mid+1,r,x);
    }void add(int _k,int _b){k[++tot] = _k,b[tot] = _b,upd(rt,1,n,tot);}
    int qry(int s,int l,int r,int x){
        if(!s) return -1e9;
        if(l == r) return get(x,mx[s]);
        int mid = (l + r) / 2;
        return max(get(x,mx[s]),(x <= mid ? qry(ls[s],l,mid,x) : qry(rs[s],mid+1,r,x)));
    }
}t[N];
void los(){
    cin >> n >> k;
    vector<vector<int>> dp(k + 1,vector<int>(k + 1,-1e9));
    vector<int> pos(k + 1);
    for(int i = 1;i <= n;i ++) cin >> a[i];
    dp[0][0] = 0; int j = 1;
    for(int i = 1;i <= k;i ++) for(;j <= n;j ++) 
        if(a[j] >= i){ pos[i] = n - j + 1; break;}
    t[0].clr(),t[0].add(0,0);
    for(int i = 1;i <= k;i ++){
        t[i].clr();
        for(int j = 1;j <= i;j ++) if(pos[j])
            dp[i][j] = max(dp[i][j],t[i-j].qry(1,1,n,pos[j]) + j * pos[j]);
        for(int j = 1;j <= i;j ++) t[i].add(-j,dp[i][j]);
    }int ans = 0;
    for(int i = 0;i <= k;i ++) for(int j = 0;j <= k;j ++)
        ans = max(ans,dp[i][j]);
    cout << ans << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

Div 2 Problem B can be solved using random values by making sure that we don't have any duplicate element in the prefix except for the range l to r where we want it to be 0.

https://codeforces.me/contest/2175/submission/352263703

The time limit is somewhat tight, but problem F can also be solved using FFT 352263995. The idea is you consider the colors in the Prufer sequence. You can figure out with what parity each color has to appear, and you get an EGF for the number of ways to choose which nodes appear for each # of times the color appears. Naively, you could have to do up to n convolutions of size n, which is too slow. However, you can batch these together by (#of nodes of a given color, mask) and do binary exponentiation, and since there can only be O(sqrt(n)) of these, we get an O(n^(1.5)log^2(n)) algorithm.

I am interested to see if this is hackable.

Why "tutorial" not "editorial" and why russian bugaboo names?

For the Div2 D editorial.. isn't the time complexity for the naive solution supposed to be O(n*k*k) instead of O(n*k*k*k) ?

Why only me is refusing about what's "$$$\mathbb{E}$$$" stands for?

Is there any simpler solution for div1C?

I don't think the proof in div1.c is rigorous enough. Actually that's what confused me. $$$(s_2+1)/2 \lt len$$$ might happen, right? If the intersecting part passes through the center, it is different.

Thanks to div.1 C for making me IM again. It's too hard to me.

F:

• Given a degree sequence $$$g_{1...N}$$$ with $$$g_i \gt 0$$$ and $$$\sum g_i = 2(N-1)$$$, the number of trees is $$$(N-2)! / \prod (g_i-1)!$$$. This is sometimes known as the generalised Cayley's formula. We can split it into independent products for each colour.
• If some colour corresponds to $$$K$$$ vertices and the sum of their degrees is $$$S$$$, the number of ways to assign their degrees is $$$\left(\sum_{g \gt 0} x^g / (g-1)!\right)^K [x^S] = x^K e^{Kx} [x^S]$$$.
• Without parity constraints, the answer would simply be $$$(N-2)!$$$ times the coefficient of $$$x^{2N-2}$$$ of the product of $$$x^{K_i} e^{K_i x}$$$ over all groups. Note that $$$\sum K_i = N$$$ so we can throw away their product $$$x^N$$$ and update parity constraints to $$$mask_i \oplus (K_i\%2)$$$.
• Now we just want to find the product of formal power series $$$\sum_{S: 2 | (S-mask_i)} e^{K_i x} [x^S] x^S$$$ over all groups $$$i$$$. It's well-known that each such series is $$$(e^{K_i x} + e^{-K_i x})/2$$$ if $$$mask_i$$$ is even and $$$(e^{K_i x} - e^{-K_i x})/2$$$ if $$$mask_i$$$ is odd.
• We apply dynamic programming to express the product as $$$\sum_{j=-N}^N c_j e^{jx}$$$ in $$$O(N^2)$$$. The coefficient at $$$x^{2N-2-N}$$$ is $$$\sum_{j=-N}^N c_j j^{N-2} / (N-2)!$$$, calculated in $$$O(N \log N)$$$.

Don't like to wait long for the editorials

Was it just me or was B too hard for a Div 2 B? Also C < B

Another take on problem F. There is a well-known bijection between these two objects:

• Functions $$$f: [n] \to [n]$$$ ("endofunctions")
• Permutations of labeled rooted trees

From formula perspective, we know that there are $$$n^n$$$ endofunctions, as we can pick $$$f(k)$$$ for each of $$$n$$$ values of $$$k$$$ in one of $$$n$$$ ways. Another way to count them, is to split $$$[n]$$$ into $$$n$$$ sets that represent predecessors of each $$$k$$$, i.e. values $$$i$$$ s.t. $$$f(i) = k$$$.

In generating functions, the number of such splits is $$$\left[\frac{x^n}{n!}\right] e^{nx}$$$, where the left $$$n$$$ means that the total size of the sets is $$$n$$$, and the right $$$n$$$ means that there are $$$n$$$ sets.

If we wanted to ensure total size is even, we would count them as $$$\left[\frac{x^n}{n!}\right] \cosh nx$$$, and for odd size as $$$\left[\frac{x^n}{n!}\right] \sinh nx$$$, as $$$\cosh x$$$ and $$$\sinh x$$$ are the even/odd parts of $$$e^x$$$ correspondingly.

Then, from endofunctions perspective, the degree of each $$$k$$$ is the size of the $$$k$$$-th set plus $$$1$$$. To map it back to regular trees, if $$$n \gt 1$$$, we can pick any two vertices $$$u \neq v$$$ and demand that $$$u$$$ and $$$v$$$ do not appear anywhere in predecessor lists, which would also mean that they have no successors. Doing it this way, we can think of the objects we count as a triple:

• A tree rooted in $$$u$$$
• A permutation $$$P$$$ of rooted trees with two "dangling" edges in each root
• A tree rooted in $$$v$$$

There is a one-to-one correspondence between such triples and labeled trees on $$$n$$$ vertices, as we can arrange $$$u \to P \to v$$$ as the unique path from $$$u$$$ to $$$v$$$ in the tree. Now, accounting for $$$+1$$$ in the degree, for each vertex color we know how many vertices we need and what the total parity of their "predecessor sets" should be.

Let's say that there are $$$k$$$ colors that need even sum of predecessor set sizes, with vertex counts $$$a_1, \dots, a_k$$$, and $$$l$$$ colors that need odd sum, with vertex counts $$$b_1, \dots, b_l$$$. We can then arrange the bijection above into the following formula:

To compute it quickly, we may note that $$$\log P(kx) = \sum\limits_{i=1}^\infty k^i b_i x^i$$$, where $$$b_i$$$ are the coefficients of $$$\log P(x)$$$. As such, we can find $$$\log \cosh x$$$ and $$$\log \frac{\sinh x}{x}$$$ in $$$O(n \log n)$$$, and then the problem reduces to finding $$$A_t = \sum\limits_{i=1}^k a_i^t$$$ and $$$B_t = \sum\limits_{j=1}^l b_j^t$$$.

The latter can be done in $$$O(n \log^2 n)$$$ by computing $$$\log \prod\limits_{i=1}^k \frac{1}{1-a_i x}$$$, but also constraints allow to find it in $$$O(nm)$$$.

Apparently, you can also use $$$\cosh x = \frac{t+t^{-1}}{2}$$$ and $$$\sinh x = \frac{t-t^{-1}}{2}$$$ for $$$t = e^x$$$, and find the product as a polynomial in $$$t$$$ in $$$O(n \log n)$$$, as suggested by one of the comments above.

I came up with an alternative solution for Div1D: 352286058.

The first observation is that any graph on $$$n$$$ vertices and $$$n-1$$$ edges must have a connected component which is a tree. Proof sketch: There must exist a connected component with more vertices than edges, and any connected graph with more vertices than edges is a tree. (Note that this tree might be an isolated vertex.)

For the following arguments, let me assume for simplicity that all weights are distinct, and that the edges are sorted by weight.

So let $$$T$$$ be a tree in the optimal solution. Since we can replace the edges of $$$T$$$ with any spanning tree of $$$G[V(T)]$$$, $$$T$$$ must be the MST of $$$V(T)$$$. Furthermore, all edges between $$$V(T)$$$ and $$$V(G) \setminus V(T)$$$ must have weights larger than all weights in $$$T$$$, since otherwise, we could obtain a better solution by replacing an edge in $$$T$$$ with a lighter edge between $$$V(T)$$$ and $$$V(G) \setminus V(T)$$$ (to see that the better solution is still not a tree, observe that we do not break any cycles). In other words: If we execute Kruskal's algorithm on the input graph, we will produce $$$T$$$ at some point.

When we have such a candidate tree $$$T$$$, we now add any $$$n - 1 - |E(T)|$$$ edges not incident to any vertex in $$$T$$$. If $$$T$$$ does not span the entire graph, the produced solution will not be connected, so it will be a valid solution. Clearly, we want to choose the lightest edges possible.

To quickly find the total weight of these edges, we maintain for each component the set of all incident edges in a treap. With smaller-into-larger merging we can do this in total time $$$\mathrm O(m (\log n)^2)$$$. Then, we will choose some prefix of the edges not in the treap. We can represent this by a prefix of all edges, and a prefix of edges in the treap which is subtracted. All necessary computations can be done in time $$$\mathrm O(\log n)$$$ (see code for details, this is essentially a weird binary search).

The total runtime is $$$\mathrm O(m (\log n)^2)$$$. This passes in slightly under half timelimit.

Why mine this div-2 D solution got tle : Submission
And this passes : Submission

i just stored dp[i][left] in a variable in accepted one. Is this related to cpu cache?

Also both have complexity $$$\mathcal{O}(k^4)$$$ . So i think both should tled as they are not intended to fit in time constraints.

hey I'm looking for a cp peer group to solve problems daily & discuss contests, if anyone is open then please inform me. thank you!

Div 2 B was a nightmare.
Even to generate an array with all XOR's of all subsegments non-zero was a nightmare.
Alternate solution:
0) Write a bruteforce and see the results on small n, cross fingers to see some pattern. This step os optional if you are smart enough, hehe :)
1) Take some power of 2 and put it in the middle of array, with intention to never use that power of 2 (never set the corresponding bit to 1) further. So, every subsegment which crosses that number will be for sure non-zero.
2) Solve recursively for left and right parts.
3) Now we have an array with XOR's of all subsegments non-zero. Shift elements from [l, r] to [l + 1, ...]. Thus making so that XOR(l, r) = 0 will not harm to subsegments which cross both l and r boundaries.
4) Fill [l, r] in a similar way, so all XOR's inside of [l, r] are non-zero.
5) Set a[r] = XOR(l, r — 1), so XOR(l, r) = 0 now.
6) Add some unused power of 2 to a[l] and a[r] (XOR(l, r) stays 0), thus no subsegment which crosses l or r boundary (bot not both) will be non-zero.
So, the main idea is put some big power of 2 as a separator and switch to smaller power of 2.
Probably this is also not easy enough for div2b, but just an alternative way.

I got a method of O(nk^2), and have been checking it for hours, but it keeps getting WA on test 9, and I really can't find where I made a mistake. The way is to use dp[i][j] to record the happiness and max(bi) when you use j cards on first i friends, and assume that no friends coming later bring any card. Then use b[i][j] to calculate b[i+1][j], it turns out to get correct answers in most tests, but goes wrong on several specfic test points, I wonder where I made mistakes and how should I fixed it, my code is in my latest submission, I'd appreciate it if anyone can help me check my code.

I like div2D, but my $$$O(\sum k^4)$$$ solution(link) have accepted this problem, I wonder why hacks are disabled in this problem and why the tests aren't strong enough.

I don't really understand how the array generated in B is always valid can somebody explain?

div2 B is too hard for me

352351370 why this submission shows TLE , the time complexity is 26*n please help

In the "Input" of the statement of problem C, "The only line of each test case contains 3 integers $$$n$$$, $$$m$$$, and $$$r$$$"，should $$$r$$$ actually be $$$p$$$?

Can anyone find why this solution is incorrect.Your text to link here... I know it might fail time limit, but what about correctness?

352439329

for DIV2 -Problem D , can someone please point out my mistake in this code

its K^4 solution , it should give TLE, but it gives WA on TC 5 also.

dp[i][j][l] — > ith index ; j number of cards used up till i , including bi ; the max card , ie max b is l till now , including i

array aa is the modified array , where i am keeping the first non zero k elements , as the a[i]=0 elements won't affect the distribution , however they would influence the score calculation , so for that i have kept another array cnta, which works like follows

2 0 0 4 5 =a 2 4 5 =aa 3 1 1 =cnta so basically whatever max is calculated at 2 , is counted 3 times (for the two 0s ahead also )

EDIT ::: my doubt is cleared , thanks for reading

B. XOR Array | Codeforces Round 1069 (Div. 2) | EASY EXPLANATION | Varun

Youtube link

C. Needle in a Haystack | Codeforces Round 1069 (Div. 2 & Div. 1) | EASY EXPLANATION | Varun

Youtube link

Step by step, very easy explanation along with code.

D2E/D1C is a very nice problem. However, I think the proof at the end leaves some unhandled cases (or maybe I was unable to fully understand it). For what it is worth, here is a sketch for a another proof to show that for non-concentric substrings $$$S_1$$$ and $$$S_2$$$, we lose $$$|S_1 \cap S_2|$$$ degrees of freedom, which is an equivalent statement to what the editorial attempts to prove.

1. For each string, group symmetric character (for the center of the strings with odd length, considered it to be a a separate group by itself).

2. Each group (from both strings) will represent a vertex in a bipartite graph, where vertex A from $$$S_1$$$ is connected to point B in vertex from $$$S_2$$$ iff their groups share a character.

A couple of observations:

1. No double edges: a group cannot be in both sides. Otherwise the strings are concentric.
2. Each edge in the graph represents the shared character, and their number is exactly equal to $$$|S_1 \cap S_2|$$$.

3. For each connected component of length $$$n$$$, we lose $$$n-1$$$ degrees of freedom.

To see why note $$$3$$$ is true, originally we had the freedom to give any group any character, but when they are connected, they have to have the same character. So difference in degrees of freedom is $$$n - 1$$$.

Now, the key claim is that this graph has no cycles. To see this, assume that a cycle exists $$$G_1, G_2, ...., G_n$$$, with $$$G_1$$$ belongs to the groups of $$$S_1$$$ and $$$G_2$$$ and $$$G_n$$$ belongs to those of $$$S_2$$$.

Assume, $$$G_1 = (a, b)$$$, $$$G_2 = (a, c)$$$, $$$G_n = (b, d)$$$, and $$$c_1, c_2$$$ represents the centers and $$$d_1, d_2$$$ represents the diameters of each string respectively.

This means $$$dist(a, c_1) = d_1$$$, $$$dist(b, c_1) = d_1$$$, $$$dist(a, c_2) = d_2$$$, $$$dist(c, c_2) = d_2$$$, $$$dist(b, c_2) = d_2$$$, $$$dist(d, c_2) = d_2$$$

But this means that $$$a$$$ and $$$b$$$ are equidistant from both $$$c_1$$$ and $$$c_2$$$. This cannot happen unless both strings are concentric, a contradiction.

Since the graph has no cycles, this means that the number of vertices (i.e. groups) of each components is $$$edges + 1$$$. So for each component, the number of degrees of freedom we lose = the number of edges in that component. Adding these up, gives the number of edges in the graph, which is $$$|S_1 \cap S_2|$$$.

what is the expected rating breakdown of the questions ?

In D1B, if total number of cards is k or less, then number of prefix Maxima is o(sqrtK) since sum of first n integer is o(n^2)

so isn't the complexity o(k^2)? even naive transition can pass o(k^3)

Hello Codeforces Admins(@KAN,@MikeMirzayanov), I am writing regarding my skipped submission "https://codeforces.me/contest/2175/submission/352219881" for the problem 2175D in the contest Codeforces round 1069 (Div2),beacuse of which whole contest was skipped. After reviewing the matching submissions , i think i have done "unintentional leakage", though i did not copy from others and one of two users "elon_fan" has committed that he has cheated. During the contest, i wrote my solution in online compiler OneCompiler. I was unaware that these platforms index code publicaly by default. I believe that this caused my code to be leaked and found by others, resulting in matches. I apologize for this oversight and violation of rules if any done by me. I will from now use local IDE that i have (Clion). I respectfully ask that you consider this explanation. I did not intend to cheat, but i accept responsibility for using an insecure tool.

To Codeforces Admin, I appeal the code coincidence notice for my submission (#352216291) of Problem 2175D. My solution is independent; similarity comes from problem constraints and standard algorithms, not plagiarism. The problem limits k≤360, forcing O(k²) DP + greedy—only feasible approach. All valid solutions must preprocess a (remove zeros/redundant) and update DP by valid a_i’s max count, leading to structural convergence. My code has unique details: 1-based array indexing, idx/lim arrays for preprocessing, i64 alias, span array for coverage, and personalized DP loop logic—reflecting my own coding habits. I wrote directly in the online editor without local drafts, but these details prove independent work. I respect fair competition and never plagiarize. Please recheck my submission and revoke the notice to avoid unfair account penalties. Thanks! jintuling Submission ID: #352216291

Upsolving div1D I found a linear-time solution that does not use any advanced data structures. Use a selection algorithm to partially sort the edges so that $$$e_{n-2},\cdots,e_{n+1}$$$ are the $$$(n-2)$$$-th to $$$(n+1)$$$-th smallest, and the remaining nodes are partitioned onto one side or the other. After checking the $$$\left\lbrace e_1,\cdots,e_{n-1}\right\rbrace$$$ and $$$\left\lbrace e_1,\cdots,e_{n-3},e_{n},e_{n+1}\right\rbrace$$$ special cases, find via DFS in $$$T=\left\lbrace e_1,\cdots,e_{n-1}\right\rbrace$$$ the path from $$$u$$$ to $$$v$$$ where $$$e_n=(u,v)$$$, and call this the "chain", noting that the chain makes a cycle with $$$e_n$$$. For any edge $$$e_i$$$ not in the chain, $$$T-e_i+e_n$$$ has a cycle, so check $$$w_T - w_i + w_n$$$; after this, we only need to look at chain edges, so we can forget about the non-chain edges. Map all vertices onto the chain, and precompute prefix/suffix max on the chain. Then for each remaining edge, we can find the max chain edge and check that sum.

in the solution of 2174E 'return f(mod * m, k — 1) * mod' the last statement of the python looks like wrong, lack of m

according to the discription "So, we can distinguish numbers up to mod⋅m⋅f(mod⋅m,k−1)" it should be 'return f(mod * m, k — 1) * mod * m'

problem 2174E, use this query tree to accept. if the number is larger than 71874, then it can be solved by CRT.

/* 33 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ 4 2178 / \ / \ 2 8 / \ / /\ / \ / / \ / \ [1,3][4, 7]][8,32] / \ / \ 66 71874 / \ / \ [33, 65] \ [2178,71873][71874, 2e9] [66, 2177] */

Div1C2 editorial mentions "the number of pairs of non-concentric substrings with a total length of $$$s$$$", but doesn't describe the way to find this number. Seems not obvious to me. Tried googling and stuff. No convolutions are required for this, right?

I used binary lifting in B to construct. It tooks me so many time:(.

Can anyone explain the precomputation part in Wishing Cards and give the code..

This B made my brain hurt