It would be better if you added formatting for the solution to Problem F.

UPD: Thanks

In E, we can also notice that the answer to each digit x(0-9) is simply ((x+1)*(x+2))/2.

Explanation 1: Let, x be split as x=a+b+c. If a=x, b+c=0; this will generate one combination->(x,0,0). If a=x-1, b+c=1; this will generate two combinations->(x-1,0,1) and (x-1,1,0).Similarly you can notice that the total combinations for digit x= 1+2+3+..+x+x+1= ((x+1)*(x+2))/2. So, no need to use the loops to calculate this.

Explanation 2(Suggested by my brother): The combinatorics formula to distribute x as a sum of k non-negative numbers is C(n+k-1,k-1) which here transforms to C(x+3-1,3-1)=C(x+2,2)=((x+1)*(x+2))/2.

Or, you could have just figured this out by looking at the test cases.

Video Editorial For Problems A,B,C,D,E,F,G._

wasn't able to participate in this contest, but the problems were very good, I think. although G does feel like it reduces down to just applying a standard graph algorithm, no?

Video solution for Chinese:

BiliBili

Video Explanations

Problem A 1907A Rook

Problem B 1907B YetnotherrokenKeoard

Problem C 1907C Removal of Unattractive Pairs

Problem D 1907D Jumping Through Segments

Problem E 1907E Good Triples

Div.3 at its best! :)

Can someone explain F,i don't understand tutorial at all.

did anyone got rating for this contest

In C, how do you prove that if no character appears more than floor(n/2) times, we can always achieve n%2 length of the final string? Please help.

Nearly 24 hours have passed, and the rating still doesn't change?

Is the reason why editorial's check function for Binary Search works trivial? Because after x steps, if the intersection with the segment is non empty => I have one sequence of steps that lands me after x steps inside that interval. It does not ensure that those steps are consistent with the last x-1 regions right? (It should since the editorial is right, but I don't see how we can prove it.)

tql

My back traversal solution for Problem B:

`void solve(int test){`
``	debug(test)``
...

``	string s;	cin>>s;``
``	int n= s.size();``
```` 
``	string ans="";``
``	int cap=0, sm=0;``
``	for(int i=n-1; i>=0; i--){``
``		if(s[i]=='B'){``
``			cap++;``
``		}else if(s[i]=='b'){``
``			sm++;``
``		}else if('a'<=s[i] && s[i]<='z'){``
``			if(sm>0){``
``				sm--;``
``				continue;``
``			}else{``
``				ans+=s[i];``
``			}``
``		}else if('A'<=s[i] && s[i]<='Z'){``
``			if(cap>0){``
``				cap--;``
``				continue;``
``			}else{``
``				ans+=s[i];``
``			}``
``		}``
``	}``
``	reverse(all(ans));``
``	cout<<ans<<nline;``
}
 

in problem C, if max. freq is greater than or equal to half then the answer would be 2*max freq — total letters but if it is less than that ? would it always get paired up if its not odd. Please explain it in detail . I am not getting the intuition

Thank you for such a wonderful round pashka, Vladosiya, MikeMirzayanov. I will be looking forward to a new and interesting round from you.

G is very similar to https://codeforces.net/problemset/problem/1872/F. Just a little addition that the nodes now have states attached to them.

Hi, can anyone tell me why this is TLE in Python but AC in C++?

Python: 236125120 it is TLE without the fastIO line as well.

C++: 236125273

I am having an identity crisis.

*accidentally posted the comment in Russian, my apologies for the spam

can somebody explain what this line of code means in the solution of F: minn = min(minn, i-n+1, len(p)-i+1)

Is this Tutorial written for those who don't need it?

No proof, No explanation, Only conclusion. Oh, yes, I completely understood

Is the following true?

For a group of numbers, of size n, if the freq of each number is less than n/2 and if you were to eliminate 1 pair of unequal numbers at a time, you will be left 0 or 1 numbers.

236178810 Can Anyone tell me what is wrong in the mentioned code.

The problems are great, but I feel that the editorial is written rather poorly.

Here is a (hopefully) more intuitive editorial of problem F -

Let us consider the inverse of the operations given in the original problem, for the sake of better understanding.
Given a sorted array in non-decreasing order $$$s$$$, you can perform two operations:
- Shift Inverse: move the first element of the array to the last place, and shift all other elements to the left, so you get the array $$$s_2,s_3,...,s_n,s_1$$$.
- Reverse: reverse the whole array, so you get the array $$$s_n,s_{n-1},...,s_1$$$.

By observation, we realize, that there are three types of arrays that arise when we perform the above operations on some sorted array $$$s$$$:
i) The most basic of it is the reverse of $$$s$$$ — the array $$$s_n,s_{n-1},...,s_1$$$.
ii) An array of the form $$$s_k,s_{k+1},...,s_n,s_1,s_2,...,s_{k-1}$$$, $$$1<k \le n$$$.
iii) An array of the form $$$s_k,s_{k-1},...,s_1,s_n,s_{n-1},...,s_{k+1}$$$, $$$1 \le k<n$$$.

Thus, we can break down the original problem into the following cases:

1. If $$$a$$$ is sorted — No moves required, answer is $$$0$$$.

2. If $$$a$$$ is sorted in reverse order — reversing the array solves it, answer is $$$1$$$.

3. If $$$a$$$ is of the form presented in case ii) above —
   Let us break the array into two parts: the first part being the part of $$$a$$$ corresponding to $$$s_k,s_{k+1},...,s_n$$$ (let us call this part $$$F$$$) and the second part being the part of $$$a$$$ corresponding to $$$s_1,s_2,...,s_{k-1}$$$ (let us call this part $$$S$$$). We can solve this in two ways —
   (a) perform the 'Shift' operation on all elements of $$$S$$$. So total number of moves = $$$|S|$$$.
   (b) perform the 'Reverse' operation on $$$a$$$, perform 'Shift' operation on all elements of $$$F$$$, and then perform the 'Reverse' operation again. So total number of moves = $$$|F|+2$$$.
   We take the minimum of (a) and (b), and that is our answer.

4. If $$$a$$$ is of the form presented in case iii) above —
   Let us break the array into two parts: the first part being the part of $$$a$$$ corresponding to $$$s_k,s_{k-1},...,s_1$$$ (let us call this part $$$F$$$) and the second part being the part of $$$a$$$ corresponding to $$$s_n,s_{n-1},...,s_{k+1}$$$ (let us call this part $$$S$$$). We can solve this in two ways —
   (a) perform the 'Shift' operation on all elements of $$$S$$$, and then perform the 'Reverse' operation. So total number of moves = $$$|S|+1$$$.
   (b) perform the 'Reverse' operation on $$$a$$$ and then perform 'Shift' operation on all elements of $$$F$$$. So total number of moves = $$$|F|+1$$$.
   We take the minimum of (a) and (b), and that is our answer.

5. If $$$a$$$ is neither of the cases presented above, then the answer is $$$-1$$$.

C++ code for reference.

[DOUBT][PROBLEM G] — > can someone explain how to find minimum number of operations to turn off all turned on lights in the cycle? firstly, we will remove/turn off all nodes with in-degree=0 and will keep on removing till we find the cycle. I am struck after this point.

For F, we can also notice that the problem is essentially asking for the minimum number of steps to move the last decrement (or increment but flip it to become a decrement if num decrements <= 1) to the last position such that a[n-1] - a[0] > 0 and none of the other pairs are decreasing. To do this, we can analyze the various cases:

1. Num decrements from [0, 1] to [n-2, n-1] is 0: No operations are required so output 0.
2. Num increments from [0, 1] to [n-2, n-1] is 0: Only 1 reverse operation is required so output 1.
3. Num decrements from [0, 1] to [n-1, 0] > 1 and num increments from [0, 1] to [n-1, 0] > 1:
   It is not possible to shift and reverse the array into a non-decreasing order as shift preserves both num increments and num decrements while reverse swaps decrements with increments so number of decrements can never be 0 or 1.
4. Num increments > num decrements (i.e. 1):
   We need to shift the decrement to be at pos [n-1, 0]. Suppose the decrement is at pos [i, (i+1) % n]. Then this can be done in min(n-1-i, 3+i) moves as if it is closer to the front, we reverse the array twice to minimize the number of moves.
5. Num decrements > num increments (i.e. 1):
   We need to reverse the increment to become a decrement and shift the decrement to be at pos [n-1, 0] (in any order). Suppose the increment is at pos [i, (i+1) % n]. Then this can be done in min(n-i, 2+i) moves as if it is closer to the front, we reverse the array first to minimize the number of moves.
6. Num increments == num decrements == 1 and last increment pos i [i, (i+1) % n] > last decrement pos j [j, (j+1) % n]:
   We can choose to either shift the increment to [n-1, 0] and reverse the array or reverse the array and shift the decrement (now increment) to [n-1, 0] and reverse the array again. This will use min(n-i, 3+j) moves.
7. Num increments == num decrements == 1 and last increment pos i [i, (i+1) % n] < last decrement pos j [j, (j+1) % n]:
   We can choose to either shift the decrement to [n-1, 0] or reverse the array and shift the increment (now decrement) to [n-1, 0]. This will use min(n-1-j, 2+i) moves.

The editorials are very hard to understand, specially for E, F and G. :)

:D

can someone give a real proof to the claim in E, that the condition is satisfied only in the case when there is no carry over in addition, and thus never in the case there is a carry over? If not proof, a sound intuitive explanation will also help.

In Problem E. 1907E — Good Triples Can someone please tell the proof for:

"A triplet is considered good only if each digit of the number n was obtained without carrying over during addition."

This is a good observation, but how can I prove such information or approach it at least?

There exists a hashing solution to problem F.

You can save two hash values , one for the sorted non-decreasing array and the other for the sorted non-increasing array.

Then, you can try doing the operations on the original array or on the reverse of it ( with additional cost of one operation). Doing the operation on an element which is the last in array is simply subtracting the element from the current hash, dividing by base and adding this value * base ^ (n-1).

Then, the first moment where the hashes are equal , we have found an answer to minimize over it and stop doing operations.

Link to submission: https://codeforces.net/contest/1907/submission/236598692.

P.S I found this solution more understandable than what is written in the tutorial.

For problem C, why is it true that we can remove all possible pairs regardless of the order of deletions if no character occurs in the string more than n/2 times? For example, in the string aabbcc it does matter the order of deletion, because if we just deleted ab and ab we would be left with cc which is not optimal.

can someone explain problem D

wo bu neng li jie ni xie zhe ge ti jie shi gei wo zhe zhong cai ji kan de dong de ma?!

There’s my view of the solution of problem E (in understandable English). https://youtu.be/VKqPUNGcD0k

I have got a very easy solution for problem E i.e for which digit of input number, you have certain combinations available. so, its better to mulitply those combinations for each of the digits of input number. Also, you can pre-compute the combinations for each digit(0-9) by simply observing the test case.

For Problem D, how do we develop the segment where we end up ourselves after $$$ith$$$ iteration?
How do we prove that $$$[ll,rr]$$$ are always the bounds we find ourselves?

If anyone want solution for question F , i have explained in comments in simple words 273078914

My approach for Problem E:

Suppose there are n identical balls (0 <= n <= 9) arranged horizontally. Also, there are two identical bars that we will be using to separate the balls into three groups.

xOxOx...xOx

Here 'O' represents a ball and 'x' represents a position where you can put one of the bars. Thus there are n+1 such positions to put the first bar.

Let us put the first bar arbitrarily as follows:

xOxOx...xOxBxOx...xOx

Here 'B' represents a bar.

Now there are n+2 positions where you can put the second bar.

But the two bars are interchangeable, so we will have to divide by 2.

Thus for n, there are (n+1)*(n+2)/2 ways of arranging them. (Remember, here 0 <= n <= 9.)

We have to do the same for all the digits and multiply them.

Here is my solution (in PyPy3-64):

https://codeforces.net/contest/1907/submission/278685323