By Vladosiya, history, 3 months ago, translation,

1907A - Rook

Idea: pashka

Tutorial
Solution

1907B - YetnotherrokenKeoard

Idea: pashka, MikeMirzayanov

Tutorial
Solution

1907C - Removal of Unattractive Pairs

Tutorial
Solution

1907D - Jumping Through Segments

Tutorial
Solution

1907E - Good Triples

Idea: pashka

Tutorial
Solution

1907F - Shift and Reverse

Idea: pashka

Tutorial
Solution

1907G - Lights

Idea: pashka

Tutorial
Solution
• +27

 » 3 months ago, # | ← Rev. 2 →   +27 It would be better if you added formatting for the solution to Problem F.UPD: Thanks
•  » » 2 months ago, # ^ |   0 It is too difficute to understand.
 » 3 months ago, # | ← Rev. 4 →   +22 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.
•  » » 3 months ago, # ^ |   0 How did you get this equation? ((x+1)*(x+2))/2
•  » » » 3 months ago, # ^ |   0 Summation of numbers from 1 to n = (n*(n+1))/2
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Why do I calculate numbers from 1 to x+1 ?
•  » » » » » 3 months ago, # ^ |   0 I think you might be confused in this line : "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." that's why you need to calculate the sum from 1 to x+1. Please correct me if I am wrong.
•  » » » » » » 3 months ago, # ^ |   0 It is not clear to me why we will stop at x+1 "
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 Maybe this will help:When a=x, there is 1 combination: (x,0,0)When a=x-1, 2 combinations: (x-1,1,0),(x-1,0,1)When a=x-2, 3 combinations: (x-2,2,0),(x-2,1,1),(x-2,0,2)...When a=1, x combinations: (1,x-1,0),(1,x-2,1),(1,x-3,2)----(1,1,x-2),(1,0,x-1)When a=0, x+1 combinations: (0,x,0),(0,x-1,1),(0,x-2,2)----(0,1,x-1),(0,0,x)Total combinations =1+2+....+x+(x+1)
•  » » » » » » » » 3 months ago, # ^ |   0 I understand now, thank you
•  » » » » » » » » 3 months ago, # ^ |   0 really nice
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 This is called stars and bars. U can read more about in this article in TOPCODER https://www.topcoder.com/thrive/articles/Basics%20of%20Combinatorics
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thank You Very Much for sharing this
 » 3 months ago, # |   +5 Video Editorial For Problems A,B,C,D,E,F,G._
•  » » 3 months ago, # ^ |   +3 After this video, can you speak English or have subtitles in English for your video so that all coders around the world can understand it?
•  » » 3 months ago, # ^ |   0 Greeting sir/bhiya I am trying this question from tomorrow smjh nahi aarha kaha galti kr raha hu , if you could point it would be great help .Thankyou
•  » » » 2 months ago, # ^ |   +1 The way you are moving from one node to another while applying topological sort is wrong and also you are code is bit messy while solving around cycle of the graph. You can look at my code to understand it better. My code
 » 3 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   +1 Yes, topological sort with some greedy approach.
 » 3 months ago, # |   +12 Video solution for Chinese:BiliBili
•  » » 3 months ago, # ^ |   0 gratitudes!
 » 3 months ago, # | ← Rev. 2 →   0 Video ExplanationsProblem A 1907A RookProblem B 1907B YetnotherrokenKeoardProblem C 1907C Removal of Unattractive PairsProblem D 1907D Jumping Through SegmentsProblem E 1907E Good Triples
 » 3 months ago, # | ← Rev. 2 →   +29 My DP solution for E - Good Triples#include const int N = 1e7 + 1; long long dp[N]; int main() { dp[0] = 1; for (int i = 1; i < N; ++i) { if (i < 10) { dp[i] = dp[i - 1] + i + 1; } else if (i % 10 == 0) { dp[i] = dp[i / 10]; } else { dp[i] = dp[i - 1] * dp[i % 10] / dp[i % 10 - 1]; } } int t, n; for (std::cin >> t; t--; ) { std::cin >> n; std::cout << dp[n] << '\n'; } } 
•  » » 3 months ago, # ^ |   +4 Can you explain the transition states in this DP.
•  » » 3 months ago, # ^ |   0 Wow! It so a beautiful DP
•  » » 3 months ago, # ^ |   0 If anyone gets this solution , kindly do explain.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 From the editorial, we know    dp[i] = dp[i / 10] * dp[i % 10],    dp[i - 1] = dp[(i - 1) / 10] * dp[(i - 1) % 10]if i >= 10 and i % 10 == 0 then    dp[i] = dp[i / 10] * dp[0] = dp[i / 10]if i >= 10 and i % 10 > 0, then    dp[(i - 1) / 10] = dp[i / 10],    dp[(i - 1) % 10] = dp[i % 10 -1]so dp[i] = dp[i / 10] * dp[i % 10]    = dp[(i - 1) / 10] * dp[i % 10]    = dp[i - 1] / dp[(i - 1) % 10] * dp[i % 10]    = dp[i - 1] * dp[i % 10] / dp[i % 10 -1]
•  » » » » 2 months ago, # ^ |   0 Ummm, if i >= 10 then dp[i] = dp[i / 10] * dp[i % 10] is good enough.
 » 3 months ago, # |   0 Div.3 at its best! :)
 » 3 months ago, # |   0 Can someone explain F,i don't understand tutorial at all.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +20 You can think that: RR <=> 0(doing nothing) SRS <=> R So, we can conclude that: There will be no consecutive R It doesn't make sense to insert R in consecutive S The final structure must have a long string of S's in the middle, and an optional R at the beginning and end.
•  » » » 3 months ago, # ^ |   0 Thank you very much!
•  » » » 3 months ago, # ^ |   0 how does writing the array twice and then looking at the increasing and decreasing segments help ?
•  » » » » 3 months ago, # ^ |   0 Such array contains all shifts of initial one, if there is an increasing or decreasing segment of length $n$ it is one of the shifts we are searching for.
•  » » » 3 months ago, # ^ |   0 How can someone reach SRS===R condition?(How to think of this condition,intuition wise)
•  » » » » 3 months ago, # ^ |   0 Consider RSR, you move the first element of array to the last place, and shift all other elements to the left, it's a reversed operation to S, so S(RSR) will not change the array, therefore SRS === R:)
 » 3 months ago, # |   0 did anyone got rating for this contest
•  » » 3 months ago, # ^ |   0 nah yet, not so fast this time
 » 3 months ago, # |   +2 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.
•  » » 3 months ago, # ^ |   0 Does anyone have a formal proof for this?
•  » » » 3 months ago, # ^ |   0
 » 3 months ago, # |   +1 Nearly 24 hours have passed, and the rating still doesn't change?
 » 3 months ago, # |   0 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.)
•  » » 3 months ago, # ^ |   +3 Consider the segment after x steps, if you can find one with intersection. For all points inside this segment there is a point in the last segment you could have reached it from. In other words you can pick any point in the current valid segment, and there is a point in the last segment from where you could reach this. You can continue this reasoning to the first segment. I agree, this is not that trivial to see.
 » 3 months ago, # |   0 tql
 » 3 months ago, # |   0 My back traversal solution for Problem B: Solutionvoid 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<
•  » » 3 months ago, # ^ |   0 why is my solution giving TLE, even though im using the same approach
•  » » » 3 months ago, # ^ |   0 I think the way of adding characters was causing TLE, shorthand form is faster.
 » 3 months ago, # |   0 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 This isn't a mathematical proof but more of an intuitive one: If you have an odd length of string with different characters, you can remove all but one of them. i.e: abcfdeg -> ... -> cNotice you can always pair the character with the max frequency with any other character. This is intuitive enough, but here is more (informal) intuitive reasoning in case you're not convinced:Assume it is not the case, it would imply the entire string has same characters (trivial), or that the max frequency character needs to be paired with some specific character for deletion which would violate the definition in the problem.As for the reasoning behind why it is 2*maxfreq — n, consider the following case: "xxxxxxxxxyyyyyxxyy" Note that y can be any character that is not x. We keep on deleting "xy" until a string of x is left.number of x in the end = freq[x] — freq[y]freq[y] = n — freq[x]Substitute that in and you will getnumber of x in the end = freq[x] — (n — freq[x]) = 2*freq[x] — n.In the case where the length is odd in which case we cannot delete one character. try "abc" or "xabcd". Also since we are pairing characters we can pair at most floor(n/2) characters.
•  » » » 3 months ago, # ^ |   0 Yes this I understood but suppose I have the string "aaaaabbccccddd", won't there be 2 d remaining after I paired all a with b and c. The order thing I'm not getting that how will the letters be paired .
•  » » » » 3 months ago, # ^ |   0 You can pair other letters as well. The key observation is that only the majority character will remain in the end of all moves. (only if it occurs more than n/2 times.) Consider the following sequence of operations.aaaaab bc cccdddaaaaa bc ccdddaaaa ac cdddaaa ac dddaa ad dda ad dad.
•  » » » » » 3 months ago, # ^ |   0 oh thanks a lot gentleman!! i understood
 » 3 months ago, # |   +13 Thank you for such a wonderful round pashka, Vladosiya, MikeMirzayanov. I will be looking forward to a new and interesting round from you.
 » 3 months ago, # |   0 G is very similar to https://codeforces.com/problemset/problem/1872/F. Just a little addition that the nodes now have states attached to them.
 » 3 months ago, # | ← Rev. 2 →   0 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++: 236125273I am having an identity crisis.*accidentally posted the comment in Russian, my apologies for the spam
•  » » 3 months ago, # ^ |   0 Because string concatenation via + is very expensive operation in Python. Here is you code but string and s += are replaced with array and s.append(). It passes. 236138895
•  » » » 3 months ago, # ^ |   0 Ah this makes so much more sense now, thank you! :)
 » 3 months ago, # |   0 can somebody explain what this line of code means in the solution of F: minn = min(minn, i-n+1, len(p)-i+1)
 » 3 months ago, # |   +14 Is this Tutorial written for those who don't need it?No proof, No explanation, Only conclusion. Oh, yes, I completely understood
 » 3 months ago, # | ← Rev. 2 →   0 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. 
 » 3 months ago, # |   0 236178810 Can Anyone tell me what is wrong in the mentioned code.
 » 3 months ago, # | ← Rev. 2 →   +16 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
•  » » 3 months ago, # ^ |   +1 So much better than the editorial, thank you very much!
•  » » 3 months ago, # ^ |   0 236178810 I did same approach ? Why is it wrong then?
 » 3 months ago, # |   0 [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.
•  » » 3 months ago, # ^ |   +2 Find any light that is on in the cycle. There are only two ways for it too be turned off — either you directly flip it's switch or you flip the switch of the previous node in the cycle. Once you've chosen the starting node to start flipping you can move through the greedily flipping any lights that are on. Calculate the number of flips for both starting nodes and choose the smaller.
 » 3 months ago, # | ← Rev. 2 →   0 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: Num decrements from [0, 1] to [n-2, n-1] is 0: No operations are required so output 0. Num increments from [0, 1] to [n-2, n-1] is 0: Only 1 reverse operation is required so output 1. 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. 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. 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. 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. 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.
 » 3 months ago, # |   +2 The editorials are very hard to understand, specially for E, F and G. :)
 » 3 months ago, # |   0 Please, upvote this comment
 » 3 months ago, # |   0 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.
 » 3 months ago, # |   0 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?
 » 3 months ago, # | ← Rev. 2 →   0 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.com/contest/1907/submission/236598692.P.S I found this solution more understandable than what is written in the tutorial.
•  » » 6 weeks ago, # ^ |   0 But hashing ( although the probability is very small) may lead you to collisions in the worst case..
•  » » » 6 weeks ago, # ^ |   0 Probability of collision with double hashing is very very small : )
 » 2 months ago, # |   0 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.
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   0 similar problem . This is explanation
 » 2 months ago, # |   0 can someone explain problem D
 » 4 weeks ago, # |   0 wo bu neng li jie ni xie zhe ge ti jie shi gei wo zhe zhong cai ji kan de dong de ma?!
 » 4 weeks ago, # |   0 There’s my view of the solution of problem E (in understandable English). https://youtu.be/VKqPUNGcD0k