Since we have the proof that the structure described in the problem E editorial is optimal, but Vovuh didn't post it for some reason, I'll try to explain it.

Consider the case $$$w \le b$$$. The structure from the editorial can handle at least $$$w - 1$$$ and at most $$$3w + 1$$$ black cells. It is impossible that $$$b < w - 1$$$, since $$$w \le b$$$. So we have to prove that there's no structure of component capable of supporting more than $$$3w + 1$$$ cells.

We can surround each white cell with four black cells, so we can't support more than $$$4w$$$ cells — but even this is possible only if $$$w = 1$$$, because we need do somehow connect all white cells. For a fixed black cell $$$i$$$, let's denote the number of white cells adjacent to it as $$$k_i$$$. The sum of $$$k_i$$$ over all black cells cannot exceed $$$4w$$$. Some cells can have $$$k_i = 1$$$, but if we want to connect some white cells, we have to use a black cell that has $$$k_i > 1$$$.

Let's analyze the sum of $$$(k_i - 1)$$$ over all black cells. I state that it is not less than $$$w - 1$$$, because we need at least $$$w - 1$$$ ''connections'' to connect all white cells. So, each value of $$$k_i$$$ is at least $$$1$$$, $$$\sum k_i \le 4w$$$, and $$$\sum (k_i - 1) \ge w - 1$$$. It means that there can be at most $$$3w + 1$$$ summands in these sums, so we can have at most $$$3w + 1$$$ black cells.

There's a typo, problem A links to 1015A instead of 1196A.

Wouldn't Floyd Warshall be too much for around 800 vertices?

Great editorial! All the solutions are very nicely explained.

Can anyone explain B to me please? And if we print k-1 positions of odd numbers, what if there are more than one numbers of odd numbers in a segment? Please help. Thanks.

Does someone use DP to pass the problem D.

You can make dp[i][j] mean from the i-th character and start with j=0('R'),j=1('G'),j=2('B')

make tab={'R','G','B'},ADD=(k-1)%3

so:

dp[i][0]=dp[i-1][2]-(s[i-2]!='B')+(s[i+k-2]!=tab[ADD]);

dp[i][1]=dp[i-1][0]-(s[i-2]!='R')+(s[i+k-2]!=tab[(ADD+1)%3]);

dp[i][2]=dp[i-1][1]-(s[i-2]!='G')+(s[i+k-2]!=tab[(ADD+2)%3]);

The best Div 3 ever ! Fast and quality

Why do we need only min(k,m) edges for problem F?

why there are two Tutorials

The solution to E is very beautiful

I don't understand why doesn't need more than min(k,m), somebody knows the reason for this it

How to solve F for greater K? I read about Yen's algorithm for single source K-th shortest path. But this one is different.

I was lazy to read the A statement, decided to read examples and send code.

It was easier to solve the problem with examples instead of the statement :D

Want moar!

I wrote n dijkstra's algorithms in F. I suppose it works in $$$O(nklog(n))$$$. It still passed in 450ms.

Please tell me where I am making mistake in solution of D1: 1) I make three strings of length K each starting with R,G,B. eg k=3 s[0]="RGB",s[1]="GBR",s[2]="BRG" 2) I am checking the longest common substring with each of the three strings with the given string and storing in mx. 3)return answer as k-mx; Pls Help /. My Solution

I tried to upsolve problem F. Once solved I submitted it. It failed on TC 3 so I spent some time trying to debug it but couldn't. I then read the editorial and it seemed that their approach was the same as mine. It would help me greatly if someone could tell me what was wrong with my solution.

57753983

Thanks in advance :)

Question F was nice, but can someone provide an efficient method to solve the harder variant of this question, where k can take any value between 1 and m.

Problem E:

Can someone help me understand why BFS does not work? Something like an island trying to increase to all sides, or a minesweeper.

So, I got hacked due to a time limit exceeded on problem B. I followed a similar process as shown in the solution with an O(q*n) solution. But I think the if(k==1) break; statement would have optimized my solution.

57661799

There is mistake in the solution to B: "at least one of k segments will have even number of odd elements (so will have odd sum)". An even number of odd elements yields an even sum, not an odd sum.

For F I got "accepted" when I did not use the "main observation" from the editorial solution and just used lazy Dijkstra-s from every node run in parallel with one shared priority_queue so that I find shortest distances one by one until I find k of them. I needed to make Dijkstra-s lazy because otherwise I had "memory limit exceeded"--I think because my priority_queue became too big. Here is my commented code:

https://codeforces.me/contest/1196/submission/57786369

I still can't figure out its complexity. Could you please help me with this?

vovuh can you please tell me why the solution for D2 is always working ?

I am asking for the case when we have already a substring of size k in string s that is also the substring for the infinite string . Now when we are going to modify the string s according to offset then their are pretty much chances that the substring will be changed and we don't get optimal ans which is zero for this case .

I think you got my question ? Please explain ?

Where can i find proof for problem F ?

Please, help. In F, Can someone explain answer on test: 4 4 4 1 2 1 2 3 1 1 3 1 3 4 3

Author's solution gives 3 but optimal way is 1 -> 2 -> 3 with length 2.

The tutorial for problem E is quite misleading.

$$$w−1$$$ black cells to the up (all cells $$$(1,2w+2∗i)$$$ for all $$$i$$$ from $$$0$$$ to $$$w−1$$$)

should be $$$ w$$$ black cells <...> $$$(1, 2 w - 2 i) $$$

$$$w−1$$$ black cells to the down (all cells $$$(3,2w+2∗i)$$$ for all $$$i$$$ from $$$0$$$ to $$$w−1$$$)

$$$ w$$$<...> $$$(3, 2 w - 2 i) $$$

Do I misunderstand something?

vovuh the editorial has not been linked to the contest page. Please look into it.

Hi! I don't understand why my code in python 3 do not works in the problem A — Three Piles of Candies

for a in range(int(input())): print(int((sum([int(i) for i in input().split()]))/2))

It says wrong answer on the third test....

Can somebody please explain the solution to problem d2

I coded the same idea for Problem F, but thought there might be a problem with it while coding. I got accepted anyways (and had a good moment of laughter bc i expected either TLE or WA) but now I'm here to ask, what if the weights of all the edges falls below the 400th minimum of all weights, so we're left with the very given graph... no reduction is made. How does this not face TLE?