### Newtech66's blog

By Newtech66, 4 months ago,

Thank you everyone for your participation. Do vote under the Feedback section, and feel free to give your review of the problems in the comments.

Idea: TimeWarp101
Editorial: TimeWarp101

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

Idea: Newtech66
Editorial: Newtech66

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

Idea: Newtech66
Editorial: Newtech66

Hints
Solution
Implementation (C++)
Feedback

Idea: Newtech66
Editorial: Newtech66

Hints
Solution
Implementation (C++)
Feedback
Challenge

Idea: Newtech66
Editorial: TimeWarp101

Hints
Solution
Implementation (C++)
Feedback
Challenge

Idea: Newtech66
Editorial: Newtech66

Bench0310 has written another proof for the solution to this problem here and here. Many thanks to him!

Hints
Solution
Implementation (C++)
Feedback

• +74

 » 3 months ago, # |   +12 Writing for the ones I solved: I noticed many people complaining about A in the main thread. Although I wasn't affected by the judge server failing, I thought the observations needed for this problem were fairly straightforward, although maybe for some it could have been tricky to implement. Problem B also had a very simple idea, but I found implementation for this problem to be quite hairy. Still a decent problem although a bit trollish for the second spot. Problem C required a very straightforward greedy observation. I think this should have been swapped with the B problem. Problem D is interesting. There exist other solutions than the one provided in the editorial. I'm not exactly sure how to describe it but the code is here. I spent more time on problem B than problems A, C, D combined, although that's mostly my fault.
•  » » 3 months ago, # ^ |   +4 I think the time you spend on each problem just depends on you, not on the problem's quality. I spent more time on A, than on B or C. Also, I do not get why you say B's implementation was hairy, I didn't have any problems implementing it and the idea was easy to get.
•  » » » 3 months ago, # ^ |   0 I agree that the idea was very simple. For me personally, I overcomplicated the implementation and ended up falling in a lot of traps. I knew that it was mostly my fault, but I saw that others had similar experiences, so I thought it would be fairly reasonable to bring it up.
•  » » 3 months ago, # ^ |   -45 Who tf asked?
•  » » 3 months ago, # ^ |   +12 For the problem D, I have the same solution as you. It is pretty hard to explain, because it is a result of making several observations.The first thing I noticed is that the first number is the (0-indexed) position of the first zero in the original array; n means that there is no zero. That is because we either have a zero there (which will never be replaced) or a one (which will be replaced as soon as we encounter a zero). After thinking for a while, I was able to extend this logic to "if $A_i = 1$, then $C_i$ is the 0-indexed position of the i-th zero in $A$". That's because we will replace 1 with 0 as soon as we find the i-th zero, but no sooner since we first have to set the first (i-1) elements to 0. From this, we infer the first rule: if $A_i = 1$, then $A_{C_i} = 0$.Now what about the case when $A_i = 0$? Well, if there aren't any 1's before it in A, then (and only then) $C_i = 0$. Otherwise, it will become a 1 on the i-th step, because it will be the last sorted element. And after that, it will become a 0 again when we add the i-th zero. That means that $C_i = Z_i - i$, where $Z_i$ is the position of the i-th zero. Thus, if $A_i = 0$ and $C_i \neq 0$, then $Z_i = C_i + i => A_{C_i + i}$ = 0.One last thing we need to observe is that after we encounter the first non-zero $C_j$, we always know $A_i$ before processing it, because we know the position of the (i-1)-st zero and there is at least one 1 before this point.
•  » » » 3 months ago, # ^ |   0 How do you prove that this is sufficient?
•  » » » » 3 months ago, # ^ |   +3 Essentially, we learn the position of every zero in the array. On all the other positions there can only be ones. So there is only one solution, and we find it.
•  » » » » » 3 months ago, # ^ |   0 How can you say that "at all other positions, there can only be ones"?
•  » » » » » » 3 months ago, # ^ |   +3 Because there isn't a zero, and the only other option is one.
•  » » » 3 months ago, # ^ |   0 Good explanation. Breaking it up into the core "observations" is a good way to put it.
 » 3 months ago, # |   +7 Thank you problem writers for problem B. I enjoyed solving it. Made me get my brain to work for the first time.
 » 3 months ago, # |   +51 I remember seeing blogposts that said A’s are too ad-hocish and if you are new to CP and have no math competitions background you can’t really solve them. And some even suggested that first problems should be more about implementation than about math observations. But yesterday’s A was about pigeonhole principle and outputting such string. So basic math (you may even not know what pigeonhole principle is but you understand it intuitively) plus implementation. However people complained that A is too hard. So may I ask what the hell is going on?
•  » » 3 months ago, # ^ |   +4 Here is an equivalent version of this rounds problem A that is rated 1500.https://codeforces.com/problemset/problem/746/DI suspect the authors were heavily inspired from this problem. So what you are saying is that the rating for problem A should be 1500?
 » 3 months ago, # | ← Rev. 2 →   0 Oh so that why I got WA on A, I'm suck at string problem as usualAnd I got the exact idea for B quickly but I outsmarted myself lol
 » 3 months ago, # |   +1 nice problems to training my weak brain.And i've been struggled on B for more than 30min :)
 » 3 months ago, # |   +4 For Problem D, We can also iterate from left to right in C and determine indexes of 0 in A.Video Solution : Problem A-D
 » 3 months ago, # | ← Rev. 2 →   0 In the implementation of E, this line seems redundant: rep1(j, 29) if(one[j].is_joined(u, v)) return 1; Because rep(j, 30) if(zero[j].is_joined(u, v)) return 0; is easier to satisfy than the above.
 » 3 months ago, # |   0 So nice problems for div2.I love them,especially D and E.
 » 3 months ago, # |   0 Problem A:In the solution it is written, p = r/(b+1) and q = r mod (b+1). However, in the implementation for Python, it is written p = r%(b+1). This can be slightly misleading.
 » 3 months ago, # |   +9 Solution for the challenge of problem D:First, we can check if the sum of values in $C$ is divisible by $n$, if not, then the array is invalid. Now, lets just solve the problem considering the array is valid, and later check if the resulting sequence produced by our algorithm can make the array $C$ or not. The goal is now to solve the reverse problem — we have the array $A$ and need to create the sums-array $C$ from it. I'll assume one-based indexing from here on. Consider finding the sum of ones for an index $i$ in the array $A$. First of all, we check its contribution in the first $i - 1$ iterations. Until then, $A[i]$ will remain unchanged, so, if $A[i] = 1$, then $C[i] = (i - 1)$, else $C[i] = 0$.From iteration $i$ onwards, $A[i]$ will also get sorted along with the previous elements. The $i^{th}$ value in the sorted sequence can only be $0$ if there are atleast $i$ zeros in the sequence. So, we need to find the index $j$ such that $A[j]$ is the $i^{th}$ zero in the sequence. We can do this by storing all zero value indexes in a separate array. From iteration $i$ and until before the $i^{th}$ zero has been found, the value of $A[i]$ will be one. If it is found at index $j$, then the contribution to $C[i]$ will be $(j - i)$. (If $i$ zeros do not exist in the sequence, then the contribution to $C[i]$ will be $(n + 1 - i)$.So, for each element, $C[i] = (i - 1) + (j - i)$ if $A[i] = 1$, and $C[i] = (j - i)$ otherwise.
•  » » 3 months ago, # ^ |   +3 It is actually possible to solve it without solving the reverse problem. The solution requires minimal additional casework. But good job. P.S.You can submit your solution for the reverse problem here :P
 » 3 months ago, # |   +3 If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints. If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
•  » » 3 months ago, # ^ |   0 Can't find a counter test case for my 153997173 of problem D ticket(s) : https://cfstress.com/status/5235 https://cfstress.com/status/5222
•  » » » 3 months ago, # ^ |   0 You've already used the website to infer that your code runs fine on thousands of small testcases, but only fails on bigger test cases on CFWhat's the most popular reason for that? Integer Overflows.Avoid using fancy stuff such as accumulate, without reading the documentation firstI leave it up to you to figure out why do we need to handle overflows.
•  » » » » 3 months ago, # ^ |   0 Thanks.
 » 3 months ago, # | ← Rev. 2 →   0 Hi guys, I have some wonders and hope to seek for explanations! In problem D: Submission 1: I use set and get AC -> complexity O(???) (I'm still confused about this)Submission 2: I use deque and get TLE -> I expect the complexity would be O(NlogN) So I hope you guys will point out for me where did I do wrong.Sorry for my bad clarifications! Thanks in advance!I have known why my code got TLE! Thanks!
 » 3 months ago, # | ← Rev. 3 →   0 If any one can help me finding test case for problem D which fails my submission https://codeforces.com/contest/1659/submission/153997173 it will be really helpful it passes almost all smaller test cases it is failing on when n is huge, thanks in advance.(sorry for my bad english)Edit: no need, found the bug.
 » 3 months ago, # |   0 Can someone help me figure out why my solution for A is WA'ing?153898766
•  » » 3 months ago, # ^ |   0 Your code fails for the below test case: Input: 12 10 2 Output: RRRRBRRRRBRR Expected Output: RRRRBRRRBRRR According to your code 10 is begin split into 3 parts i.e., 4, 4, 2 whereas optimal division is 4, 3, 3 So we need to split the parts such that Max valued part — Min valued part is as small as possible!My solution for reference — 153908138
•  » » » 3 months ago, # ^ |   0 Why does this matter, both have a maximum of 4?
•  » » 3 months ago, # ^ |   0 You can look at the testing details, the failed test isn't that long. Your solution uses too many R's in the beginning, which leads to a large cluster of B's in the end.
 » 3 months ago, # |   +3 Can someone explain how to solve problem C, I having hard time following tutorial!
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 The whole cost of moving capital and the cost of conquering the cities can be counted separately. I think the part where representing them as $a\cdot(x_j-x_i) \quad, \quad b\cdot((x_{i+1}-x_i)+(x_{i+2}-x_i)+\ldots+(x_j-x_i))$is pretty clear. in $(x_{j_1}-x_0)+(x_{j_2}-x_{j_1})+\ldots+(x_{j_f}-x_{j_{f-1}})=x_{j_f}-x_0$ formula,the author is trying to calculate the cost made by moving capitals(we can get the cost by multiplying $a$ to this formula). The capitals are in positions $x_{j_1} ,x_{j_2} ,x_{j_3} ,\ldots, x_{j_{f-1}} ,x_{j_f}$ chronologically ,where $x_{j_f}$ is the final position of the capital.According to the formula, it can be abbreviated as $x_{j_f}-x_0$.It means the cost of moving capitals can only be determined by the final position of the capital.Then,let's see $b\cdot(p_j-p_i-(j-i)\cdot x_i)=b\cdot(p_j-p_i)-b\cdot(j-i)\cdot x_i$ part.this is the cost of conquering cities from current capital before moving the capital to the next position. let's observe $b\cdot(p_j-p_i)$ first, if capitals are still in positions $x_{j_1} ,x_{j_2} ,x_{j_3} ,..., x_{j_{f-1}} ,x_{j_f}$, the entire sum can be represented as $((p_{j_1}-p_0)+(p_{j_2}-p_{j_1})+\ldots+(p_{j_f}-p_{j_{f-1}})+(p_{n}-p_{j_{f}}))\cdot b=p_{n}\cdot b$Finally, there is $b\cdot(j-i)\cdot x_{i}$ part that we haven't discussed yet. The sum of this part is represented as $C$ in the tutorial. which can be represented as $((j_{1}-0)\cdot x_{0}+(j_{2}-j_{1})\cdot x_{j_1}+\ldots+(j_{f}-j_{f-1})\cdot x_{j_{f-1}}+(n-j_{f})\cdot x_{j_{f}})\cdot b$. if we want to maximize this, we can move our capital every time to the right after we conquer a new city,since the cost of moving the capital is only determined by the final position of the capital. In this case, we will be able to maximize $C$ by making all $j-i$ s equal to 1. Thus it becomes $C=x_0\cdot 1+x_1\cdot 1+\ldots+x_{f-1}\cdot 1+\underbrace{x_f+\ldots+x_f}_{n-f\text{ }\mathrm{times}}=p_f+(n-f-1)\cdot x_f$Finally, all we have to do is to enumerate the possible final position of the capital.and find the minimum answer of it. (sorry for my bad English,please notice me it there is anything wrong or unclear with my idea)
•  » » » 3 months ago, # ^ |   0 Thank you!
•  » » » 3 months ago, # ^ |   0 I dont understand. I send a message to you. Check your talk, pls
•  » » 3 months ago, # ^ |   0 If the Math for this problem is hard to understand , you can pretty much implement the solution using concept of prefix array. Like you can put the capital at each and every index and compare and output the min cost, in theta(n) time****
 » 3 months ago, # |   0 Can Anybody give me the solution of Problem 'A' in C? Please
•  » » 3 months ago, # ^ |   0 #include void blind_eyes() { int n, r, b; scanf("%d %d %d", &n, &r, &b); int _r = r/(b+1); int x = r - _r * (b+1); char s[101];int c = 0; while(b--) { if(x > 0){for(int i = 0; i < _r + 1; i++)s[c++] = 'R'; r = r - _r - 1;} else {for(int i = 0; i < _r ; i++)s[c++] = 'R'; r = r - _r;} s[c++] = 'B'; x--; } for(int i = 0; i < r; i++) s[c++] = 'R'; for(int i = 0; i < c; i++)printf("%c", s[i]); printf("\n"); } int main(){ int t; scanf("%d", &t); while(t--) blind_eyes(); return 0; } 
•  » » » 3 months ago, # ^ |   0 THANK YOU :D
 » 3 months ago, # | ← Rev. 2 →   +3 In solution of D, paragraph 5, every case after "Otherwise" word is very ambiguous. Can someone explain with correct grammar please?
•  » » 3 months ago, # ^ |   0 let cnt1 be the number of 1's in the array A Now consider the last element in array A if it is 1 then it will stay 1 for all arrays B[i] (B[i][n] = 1) and because we have N of them then C[n] will be equal to n if it is 0 and cnt1 = 0 then C[n] will be 0 because (B[i][n] = 0) if it is 0 and cnt1 > 0 then for surethe last element for array B[n] (B[n] is the array generated by sorting the whole array) is 1 (B[n][n] = 1) and that means that the sum of all element B[i][n] is 1
 » 3 months ago, # |   0 B and C were beautiful that I only came to know when contest got over, but thanks alot for problem A that took all the confidence and time.
•  » » 3 months ago, # ^ |   0 Don't talk bullshit Dumbass. A and B were meaningless. I don't know which f**head published these problems.
 » 3 months ago, # |   0 For problem D reverse sort sum, the explanation in the editorial for how to efficiently compute the value of some element of the C array is unclear to me. Can anyone explain what does it mean by maintain a left border, what is t[i] (I don't see a t[i] in the implementation, is it b[i] instead?), and how the formula v[i]=c[i]-(t[i]-i) is derived?
•  » » 5 weeks ago, # ^ |   0 I maintained left borders by using a map. See here: https://codeforces.com/contest/1659/submission/159512816
 » 3 months ago, # |   0 pretty good
 » 3 months ago, # | ← Rev. 2 →   0 Can someone help me figure out why my solution for A is run out of time? 154216123
•  » » 2 months ago, # ^ |   0 because you are f**king idiot!!!
•  » » » 2 months ago, # ^ |   0 Please shut up,fucking stupid ass bitch,you just like the garbage
•  » » » » 2 months ago, # ^ |   0 even my dick could solve this problem. now you know who is garbage. dumbass.
•  » » » » » 2 months ago, # ^ |   0 hhh，I don't think u have any dick , you look so funny.
 » 2 months ago, # |   0 i think i solve C in another greedy way. here it is. codethe key is to see change location as saving money for further conquer. so every iteration i compare how much to change location(c2) and how much i can save(c1). if c1 < c2, that means worthless to change. otherwise, let's do change. though it get AC, i'm curious about this greedy correctness.hope for some help
 » 6 weeks ago, # |   0 In problem B, why is it correct to add all remaining moves to the last element? What if the number of remaining moves is odd? I just cant figure out how to prove the remaining number be even.
•  » » 6 weeks ago, # ^ |   0 The remaining number can be odd and it may make the last element go from 1 to 0, but since we want lexicographically maximum, its better to have the earlier element maximum, and then use the remaining moves on last.
•  » » » 6 weeks ago, # ^ |   0 I see, thank you
 » 2 days ago, # |   0 can anyone please tell the DP approach of problem C