solved 1st 3 ques very fast but got struck on 4th ques,btw nice contest :)

Can someone please explain the solution that's given in tutorial of problem D thanks. I have done a simple solution in that that prints a + ab + ac + .... + az and so on , but I want to understand how the editorial solution works for this

For 1511B — GCD Length it can be another easy approach

cout<<(ll)pow(10, a-1)<<" "<<(ll)(pow(10, b-1)+pow(10, c-1))<<"\n";

I believe everyone wonders how top 1 risujiroh use O(n^2) brute force to solve G without being hacked(

My (faster) solution to G, using binary jumping/lifting/whatever:
It's obvious that for range $$$[L, R]$$$ we want to consider a game of nim where a token at column $$$L\leq i\leq R$$$ corresponds to a pile of size $$$i-L$$$.
Let $$$x[i][j]$$$ denote the xorsum of tokens in the range $$$[i, i+2^j)$$$, where the left border is $$$i$$$ (i.e, a token at $$$i+k$$$ contributes $$$k$$$ to the xorsum).

If we know $$$x[i][j]$$$ for all $$$i, j$$$, the xorsum of $$$[L, R]$$$ can be computed as follows.
(Below, $$$\oplus$$$ denotes xor)
Initialize the xorsum $$$G = 0$$$.
For each $$$k$$$ in descending order, if $$$L+2^k \leq R$$$, do:
1. $$$G = G \oplus x[i][k]$$$
2. If there are an odd number of tokens in the range $$$[L+2^k, R]$$$, further do $$$G = G\oplus 2^k$$$
3. $$$L = L+2^k$$$
At the end of this process, $$$G$$$ is exactly the xorsum we want, so we simply check whether it is $$$0$$$ or not.

So, we want to be able to compute all the $$$x[i][j]$$$ fast — this can be done with a similar process:
1. $$$x[i][0] = 0$$$ for all $$$1\leq i\leq m$$$.
2. $$$x[i][j] = x[i][j-1] \oplus x[i+2^{j-1}][j-1]$$$
3. If there are an odd number of tokens in $$$[i+2^{j-1}, i+2^j)$$$, further do $$$x[i][j] = x[i][j] \oplus 2^{j-1}$$$

Note that we need to be able to check whether some range contains an odd number of tokens, but that's easily done with prefix sums.
Time complexity is $$$\mathcal{O}(mlogm)$$$ for the binary jumping precalculation, and then each query is answered in $$$\mathcal{O}(logm)$$$.

My submission: 112843116

BledDestForces

I believe that everyone wonders how top 1 risujiroh use O(n^2) brute force to solve G without being hacked. Can someone explain why this solution 112827572 run so fast:)

Could someone pls tell the combinatorics / dp approach for E ? I saw in the announcements page but is very unclear.

For problem E, can anyone tell the way to find the OEIS sequence (incase anyone else did by finding contributtion method).

In problem D how will we get a Euler cycle of length k*k + 1, do we also have to add self loop for that, because without that you cannot get an Euler cycle of k*k + 1, can someone explain, possible taking example of k = 3.

How to find Eulerian Cycle in 1511D - Строка минимальной стоимости

How to find eulerian cycle in 1511D - Min Cost String

can someone explain e more properly?using dp etc

I problem F I had slightly different approach. I tried to compute $$$DP[L][i][j][k]$$$ which would mean the number of pairs of chainwords, such that first of them has length $$$(L + i)$$$, second $$$(L + j)$$$ and last part of longer chainword comes from $$$k$$$-th word. We can compute it quite straightforward without using any kind of tree structures. All we have to check is whether some parts of words match. We just see that it is enough to store only $$$((d * (d - 1)) / 2) * n + d$$$ interesting states (though we don't have to use symmetry to pass tests).

Code: https://pastebin.com/04kf681r

Was anyone else confused by the legend of F, thinking it meant count the number chainwords that have resolved ambiguity? This isn't the case tho, right?

Is this rare way to solve B...?

" Now, let's suppose there are two strings i and j such that cnti−cntj≥2. Then, if we somehow reduce the number of occurrences of the string i by 1 and increase the number of occurrences of the string j by 1, the cost will decrease " What does that mean ?

Can someone help me to in problem d (min cost string)? What's the intuition behind the greedy approach. like this

Taken from submission (random)

Can someone explain how to produce your logic for questions similar to problem B during competitions? I solved C and D in the second hour but I couldn't solve B after wasting the first hour in virtual participation...

For problem F, I generate the input that requires 141 states.

abcde
bcdef
cdefg
defga
efgab
fgabc
gabcd
a

And I believe this to be an upper bound. If there is no string that become other string prefix, the number of states will be at most 49. If there is a string that become other string prefix, the number of states will be at most 161 — 20 = 141

Can someone please explain me how the logic of D work?

Problem G can be solved with MO.

1511G - Chips on a Board Isn't complexity of solution from editorial should have log N outside of square root?

I want to share my solution of 1511G - Chips on a Board.

All we need to do is to find XOR of $$$c_i - L$$$. For details "why?" look into editorial. I'll describe here how I calculate it. Notice that we can represent each number as two digit number XY in some base $$$2^k$$$. Then $$$c_i$$$ is some xy and L is XY. But this is the same as XOR all (y-Y) and (x-X) but some of them will turn into (x-X-1) when y < Y because of carry. My idea was to view it as points in table, where X digit is on X axis, and Y digit is on Y axis. Notice, that size of table is $$$2^{2k}$$$, so with appropriate k it is O(m) memory. Then we need to XOR all xy-XY. Then, to count how many times there is x among $$$c_i$$$ is just segment in column which can be calculated as prefix sums. And, to count how many times there is y among $$$c_i$$$ is just segment in row which can be calculated as prefix sums. But here is the problem: how can we tell should we subtract 1 for carry or shouldn't? This is most tricky part of whole solution. It turns out that we subtract 1 when y < Y, but it also can be calculated as prefix sum! Because we need to find out how many of x from column we should subtract 1 and how many we shouldn't but within single column x there are exactly numbers xy where v < Y we should subtract 1, and v >= Y we shouldn't, because carry won't happen. So, we can make two tables of prefix sums: for columns and rows. Each table has $$$2^k$$$ in both dimensions, and then for each X, and each Y we calculate prefix sum which is $$$O(2 \cdot 2^k)$$$ for each request. Overall complexity then is $$$O(n+m+q\cdot\sqrt{m})$$$ 113146022

can you explain gcd length question i didnt get it

Can someone suggest some more problems which can be solved using probability for counting as mentioned in the editorial. I understood the solution but I want to practice more such problems. Thanks in advance :)

Alternative solution for problem 1511G - Chips on a Board
Consider each bit $$$b$$$ separately and keep a data structure that contains the remainder of the position of the coins in a suffix, modulo $$$2^{b+1}$$$. It should handle these operations:

• range sum on $$$[2^b, 2^{b+1} - 1]$$$ (get number of coins with that bit turned on)
• point update on $$$0$$$ (add a new coin)
• add $$$1$$$ to all elements (add a column on the left)

So you can use a Fenwick tree with Venice trick for each bit.
Total complexity: $$$O(n \log^2(n))$$$.
113692737

Is there any similar problem on codeforces as problem F but maybe of lower difficulty. I cannot understand the editorial at all.

Can some one explain the complexity in 3rd question

Can someone explain editorial's solution for problem D min cost string ?

Or can anyone explain the approach by eulerian path?

can someone please help me in question D.

i want to solve it without DFS and BFS as i dont know it yet.

can we solve it constructively??