### Kilani's blog

By Kilani, history, 16 months ago,
code

Author: Salem_Alwarawreh

code

Author: Warawreh

code

Author: Kilani

Preperation: Warawreh

code

Author: Kilani

code

Author: Warawreh

code

Author: Kilani

• +215

 » 16 months ago, # | ← Rev. 2 →   0 Thank you for the quick editorial
 » 16 months ago, # |   0 Damn, really fast editorial. Thanks, the problems were great!
 » 16 months ago, # | ← Rev. 3 →   -64 Problem C was not so good....
 » 16 months ago, # |   0 really quick
•  » » 16 months ago, # ^ |   -9 膜
 » 16 months ago, # | ← Rev. 2 →   -8 good problems
 » 16 months ago, # |   -11 wow -__- fast editional
 » 16 months ago, # | ← Rev. 2 →   -67 Boring implementation problems (first 4)
 » 16 months ago, # |   -15 really fast,the editorial was ready while system testing
 » 16 months ago, # |   -15 Thank you for the fast editorial
 » 16 months ago, # | ← Rev. 2 →   -86 "DELETED"
 » 16 months ago, # | ← Rev. 3 →   0 https://ideone.com/ZpbCHH can someone tell me how is the above code wrong for problem C. I have done almost the same thing as tutorial , the only difference is that tutorial checks that we have enough painter to paint at the end and i check that in the beginning UPDATE : The mistake has been found and corrected
•  » » 16 months ago, # ^ |   +4 I believe you don't check if the last painter has a color that doesn't appear in b (ie ans=-1) in which case you should say No and you say yes
•  » » » 16 months ago, # ^ |   0 I have checked that , I have checked that whether Vis[c[m-1]]== false . Vis is true when the no. Appear in the array b.
 » 16 months ago, # |   -9 Thanks for the contest!
 » 16 months ago, # |   -27 D was lengthy :|. Got the idea but can't implement it.
•  » » 16 months ago, # ^ |   -14 怎么做啊？？？？
 » 16 months ago, # | ← Rev. 2 →   -25 B was brute force! C was hard implementation!! Let's see the editorial for D!!!
 » 16 months ago, # | ← Rev. 2 →   +5 Thanks for quick editorial and wonderful problems, I got stuck on problem C but during the after-contest discussion with my classmates, I found that it was just hard implementation, while I was thinking of something like DP.
•  » » 16 months ago, # ^ |   0 As your senior,I have to point out that you've made A grammer mistake.
•  » » » 16 months ago, # ^ |   +9 As The Principal of your school, I have to point out that you've made a grammar mistake.
•  » » » » 16 months ago, # ^ |   +5 Lets laugh together :)
 » 16 months ago, # |   0 Can someone help me find the error in this solution. I have done exactly as the solution above states.
•  » » 16 months ago, # ^ |   +12 hack: 3 2 1 2 3 3 2 3 1 3 the ans can be Yes 1 1 but your output is No
•  » » » 16 months ago, # ^ |   0 Thankyou so much!
•  » » » 16 months ago, # ^ |   0 It works for mine, but Im still getting WA
•  » » » » 16 months ago, # ^ |   +6 Your code fails to pass this: 1 3 4 1 1 1 1 3 2 1 2 3 1 
•  » » » » » 16 months ago, # ^ |   0 thnxs for the testcase
•  » » » » » 15 months ago, # ^ |   0 Hey VTifand, Can you tell a counter example for this code 107294260 for Problem C?
•  » » » » » » 15 months ago, # ^ |   0 Test this: 1 2 2 2 1 1 1 1 2 
•  » » » » » » » 14 months ago, # ^ |   0 Hey VTifand Can you please tell where I am going wrong in this solution? 109939615 because it passes all the above test cases that u mentioned in the comments.Thanks in advance...
•  » » » » » » » » 14 months ago, # ^ |   0 1 3 3 1 1 2 2 1 1 2 2 1 
•  » » » » » » » » » 14 months ago, # ^ |   0 thank you so much brother! I found my error thanks...
•  » » » 16 months ago, # ^ |   0 Can u clear my doubt in problem C editorial, while searching an index in B-array which matches last element in C-array, it is said that a[i] should not equal to b[i].
 » 16 months ago, # |   -35 Problem C was worst in my veiw
•  » » 16 months ago, # ^ |   +9 I think it was pretty good problem for Div2, because it does not require algorithm but the way you implement your idea into your code. So yeah, I personally enjoyed it
 » 16 months ago, # |   -6 For Prob D, can someone clear my doubt. I had the same idea but was not able to prove one case.Let's say there are no two nodes that have the same value on the edge. (If x and y are nodes then they will have value as a and b) and we have m as an even number,I am not able to proof if we don't find two consecutive edges whose values are the same then the answer will always be NO. I was trying to figure out a case where it's possible.
•  » » 16 months ago, # ^ |   +3 As mentioned in the editorial, for $n\geq 3$ it's actually always possible to find two consecutive edges that are equal. just consider 3 vertices $x$, $y$ and $z$. Then two of $xy$ $yz$ and $zx$ edges must be equal.
 » 16 months ago, # |   +8 Video solution to problem D: https://youtu.be/U93sCV3I17Y
•  » » 16 months ago, # ^ |   +1 Please if possible also post a video editorial of C
•  » » 16 months ago, # ^ |   -23 Thank you! And if you are ever feeling down, know that we all love you (in a brotherly way). :-)
 » 16 months ago, # |   -8 Thank you for the questions and editorial. Much appreciated as a participant
 » 16 months ago, # | ← Rev. 4 →   +38 I have a different solution regarding problem D when m is even and there's no cycle with length 2 with the same character (i.e. $x \to y = y \to x$).Observation: For every cycle with length 3, there will be always 2 adjacent edges with the same characterProof: There are 3 edges in the cycle. We put $x \to y = a$ and $y \to z = b$. If we put $z \to x = a$, then $x \to y$ and $z \to x$ will have the same characters. Conversely, we can do the same for $z \to x = b$ and yielding similar result.Therefore, it is enough to only consider the node permutation $1, 2, 3$. If $m \bmod 3 = 0$, then arrange it in such way so the string becomes "abaaba...". If $m \bmod 3 = 1$, then arrange it in such way so the string becomes "baabaab...". Lastly if $m \bmod 3 = 2$, then arrange it in such way so the string becomes "aabaabaa...".The above strategy will work for $n \geq 3$, and it can be proven that it is impossible for $n = 2$.
•  » » 16 months ago, # ^ |   -10 Your solution is more proven and understandable than the solution in editorial! Thank you!
 » 16 months ago, # |   +5 Thanks for quick Editorial! I think Problem D is really ingenious!
 » 16 months ago, # |   0 Can someone tell me how is this code for problem C giving TLE on pretest 3. I think it's complexity is also O(N).
 » 16 months ago, # | ← Rev. 2 →   0 for problem C, here is my code(python[submission:106605351]), it is showing error on 4th input on test case 2 and, I am unable to look at that input? can someone help me out in my solution? https://codeforces.com/contest/1481/submission/106605351
•  » » 16 months ago, # ^ | ← Rev. 3 →   +3 (Input#4, TestCase #2) 24 24 19 19 19 17 24 7 12 15 11 23 3 11 1 20 10 23 24 1 23 18 23 17 3 7 19 11 19 17 24 7 12 15 11 13 3 11 1 20 10 23 24 1 23 18 23 1 12 7 22 15 3 20 22 11 18 9 10 21 11 2 13 12 10 12 16 11 16 16 12 16 11 1  Answer: YES 22 22 22 22 22 2 22 22 22 22 22 22 10 23 22 22 22 22 22 22 22 22 22 22 
•  » » » 16 months ago, # ^ |   +1 Thanks a lot,you saved my day,I literally had no idea why my case was failing. And as I debugged this case, boom it got "Accepted". And if you don't mind could you please let me know that how did you get to know about the test case. Once again thanks a lot for helping me a lot.
 » 16 months ago, # |   0 Can Problem B be done in less than O(n^2)?? using stacks ?? something like rain water trapping ? i wasn't able to code one !! would appreciate some help, if possible code XD
•  » » 16 months ago, # ^ |   +4 Consider the algorithm, because the height of each does not exceed 100, and when filling a part of the pit ($h_{i-1}\geq h_i •  » » 16 months ago, # ^ | ← Rev. 2 → +3 The solution from the tutorial is actually not O(n^2) but O(n^3). Consider the input: 1 100 10000 1 1 1 ... 1 1 100 We have to do (100 — 1) * (100 — 1) throwing simulations. Those are O(n). So that solution is O(n^3). (In this case we will need 490149 comparisons to be precise.)If you want a O(n) solution take a look at my solution. (although one needs to change the vector to doubly linked list to reach O(n) because i use erase alot.)106632891(It is not trivial that my solution is O(n) because I don't always increment my index. But every iteration either fills a pit or increases the index. You can't have to fill more than n pits in an array of size n (this can be shown using induction over n) so this is O(n).)  » 16 months ago, # | 0 Good problems  » 16 months ago, # | +1 Problem D looks like a graph problemEditorial — Well yes, but actually no!  » 16 months ago, # | 0 Can anyone help me to know the case I missed here 106605508 •  » » 16 months ago, # ^ | +5 Nevermind it was an issue of colors being 1 ... n and I assumed it as 0 ... n-1. I want to die •  » » » 16 months ago, # ^ | 0 Aren't you the guy who writes beautiful explanations?Your code looks clean. Would be great to know about your thought process. •  » » » » 16 months ago, # ^ | +9 You have to think that what is important ?.Important is in this case is that to paint every plank where a[i] != b[i].Second thing that is very important is that every painter is coloring some(exactly one) plank.Let's call the planks that need to painted some color other than a[i] as bad planks and rest (a[i] == b[i]) as good planks.We need all planks to be good at the end. Next thing is that Assume count is number of bad planks that wants color b[i]=k then we need atleast count painters that paint color k. If there are more than that and since every painter must paint (they are behaving like spoiled children) they can paint any good or bad plank of color k (if there exists such plank). Reasoning for this is to divide into three cases. Case 1 the extra painter is painting a good plank then he is just repainting it and it really doesn't do any harm. Case 2 the extra painter is painting a bad plank to its correct color but since he is extra that plank was going to be painted to its correct color at some moment , so either he is repainting or painting before its last painting.Degenerate Case is that there doesn't exist any plank that wants a color that m-th painter wants then in that case there is no answer. if there doesn't exist a plank that wants a color that (m-1)th or lesser index painter provides then he can color the unwanted color to the same plank the (m-th) last painter is going to paint at last.Assuming there exists an answer then you can be sure that last painter is going to paint or repaint some plank correctly. So any painter that comes at (m-1)th or lesser index can paint that exact plank since his paint will not remain in the end anyways.It must be clear by now that the last painters of some color k are to be processed first and other painters of color k are extra and they can paint any plank that b[i] = k (Case 2 or Case 1).Except degenerate case but that can be check by asking "Is there any painting done after this?". A flag variable can help you here.Iterating from mth painter to the first helps us a lot. For implementation details check my submission 106614841  » 16 months ago, # | ← Rev. 2 → 0 Could anyone tell me what's the difference between the AC code and this 106549562 •  » » 16 months ago, # ^ | 0 For example,$px=0$and$py=1$, the string is$\text{UUDD}$, your code is wrong. •  » » » 16 months ago, # ^ | ← Rev. 2 → 0 Code id edited .. the current id is my 1st submission •  » » » » 16 months ago, # ^ | 0 An error occurred in the$x<=0,y>=0$part •  » » » » 16 months ago, # ^ | +3 It should be if (cnt['L'] >= -x && cnt['U'] >= y) But in the code if (cnt['L'] >= -x && cnt['U'] >= -y)  •  » » » » » 16 months ago, # ^ | ← Rev. 2 → 0 RIP .. thanksthat cost me green and -123 T_T  » 16 months ago, # | +74 It's hard to understand E's solution! Why when$l[a[i]] \neq i$, I should move all elements except$a[i]$? •  » » 16 months ago, # ^ | +5 There are 2 things to do when$l_{a_i} \ne i$: We can either move everything except books with color$a_i$so they are next to each other. Or move book$a_i$so it can become next to the other books with color$a_i$. Both points are covered in case number 2 and 3. •  » » » 16 months ago, # ^ | +17 Can you share intuition behind this: (note that here we move all books even those after rai) •  » » » » 16 months ago, # ^ | +5 If we keep all books of color$a_i$unmoved and there are still books of color$a_i$to the left of$i$how will we make them adjacent, lets say we have this array$[1,2,2,1,1,3]$and$i = 4$and we don't want to move the last 2 books of color 1 how could we make all books of color 1 adjacent, simply we say that I will move all books of color 1 to my left then move all books between books of color 1 which is books between$i$and$n$.So the sequence of moves are move the first book you will get$[2,2,1,1,3,1]$, then move book with color 3 to get$[2,2,1,1,1,3]$. •  » » » » » 16 months ago, # ^ | +1 Considering example and trying to dry run51 2 2 1 3dp[i]: maximum number of books that can be left unmoved if looking at subproblem of books a[i], a[i+1]...a[n-1]dp[5] = 0 (base case)start with i=4 (0-indexed):dp[4] = 1 + dp[4+1] = 1 (scenario 1 from editorial)dp[3] = max(dp[4], cf) = max(1, 1) = 1 (scanario 2 and 3)now if dp[3] means the max number of books that can be kept unmoved when solving subproblem [i,n], shouldn't dp[3] be equal to 2. Since the suffix array is {1, 3} and both of them can be left unmoved in this subproblemAm I interpreting the meaning of dp[i] incorrectly? •  » » » » » » 16 months ago, # ^ | +15 When calculating$dp_i$we don't treat suffix$[i,n]$alone (as a sperate new array) we still take into consider that there is still more books of color 1 that will be processed later. •  » » » » » » » 16 months ago, # ^ | ← Rev. 2 → 0 Could you explain in case 2, why do we even move the books after Rai? I'm a bit confused here. •  » » » » » » 16 months ago, # ^ | +3 I think you got the idea. There are two ways to achieve the target. move book with color$a[i]$to join the book behind. keep book with color$a[i]$ummove and guarantee$a[i]$is the first book on the shelf. To do the first way, we make$dp[i]=dp[i+1]$. To do the second way, we can do the process as Warawreh says : move all elements except color$a[i]$and be ready for the elements$a[i]$that is before$i$to move to the right. But when$i==l_{a[i]}$, we have extra thing to do : just keep all$a[i]$ummove and don't need to consider element before, since there are no$a[i]$s exist before. That is$dp[i]=f[a[i]]+dp[r[a[i]]+1]$. •  » » » » » » » 16 months ago, # ^ | 0 "move the book with color$a[i]$to join the book behind" — can you elaborate a bit please? And how$dp[i] = dp[i+1]$accomplishes that? •  » » » » » » » » 16 months ago, # ^ | +1 The idea is to keep as many of books unmove as possible. That means all others books should be moved. It is obvious that we can arrange those moved book correctly to make the shelf beautiful. •  » » » 16 months ago, # ^ | 0 In case no. 3 when we are moving book$a_i$, shouldn't$dp_i = dp_{i+1}+1$instead of$dp_{i+1}$because we are moving$i^{th}$book also. Moreover, I can't understand why in case 1,$dp_i = dp_{r_{a_i}+1}+f_{a_i}$. According to my understanding, it should be$dp_i = dp_{r_{a_i}+1}+(r_{a_i}-l_{a_i}+1-f_{a_i})$as there are$(r_{a_i}-l_{a_i}+1-f_{a_i})$books between first and last instance of book with color$a_i$. Kindly help me out with this. •  » » » » 16 months ago, # ^ | +13 We are counting books that are "not" moved •  » » » » 16 months ago, # ^ | +9$dp_i$which will find for each i the maximum number of books that we can leave unmoved in the suffix$[i,n]$.You are trying to find the minimum number of moved books, but I am trying to find the maximum #unmoved books. •  » » » » » 16 months ago, # ^ | ← Rev. 8 → 0 So in case when L[a[i]]!=i...then dp[i]=max(dp[i+1],cf[a[i]]+dp[r[a[i]+1]) but u are only considering cf[a[i]](maximum unmoved books from i to n-1) cf[a[i]]+dp[r[a[i]+1]>=cf[a[i]] as term one is greater. so shouldn't it be like the way i have shown. I am vey confused over this..Please correct me. •  » » » » 16 months ago, # ^ | 0 Sorry, got it, noob error ;( •  » » 16 months ago, # ^ | 0 In my opinion, dp[i] means if books from 1 to i-1 must be moved, the maximum number of books we can leave unmoved in the suffix [i,n]. So if a book in [1,i-1] has the same color with book i, because it must be moved to the back, all the books except a[i] should be moved in order to make all books colored a[i] next to each other.  » 16 months ago, # | ← Rev. 2 → 0 The only reason the solution to AB graph (problem D) needs to be O(n^2 + m) is because it takes that O(n^2) to read the input and O(m) to print the solution. Solving the actual problem can be done O(1). See https://codeforces.com/contest/1481/submission/106613756 (which sadly I only got right after the contest had ended).The trick is that, however big the graph is, you only need look at the first three vertices. Either one of these has the same edge label in both directions, or you can find two consecutive edges in the triangle with the same values. You can then solve the problem using these three vertices as described in the editorial ignoring every other vertex and edge.This also makes it clear that the only case with no solution is the two vertex case with different edges and an even m.  » 16 months ago, # | 0 Can someone help me find the error in this solution. I have done exactly as the solution above states. •  » » 16 months ago, # ^ | ← Rev. 3 → 0 An error occurred in the (mp[1][2]==mp[2][3]&&mp[2][3]==mp[3][1]) partWe should printf("YES\n") first.  » 16 months ago, # | +1 Why my submission 106617241 is wrong? please provide me a counter case. •  » » 16 months ago, # ^ | +2 Here is a counter case: 1 3 3 1 2 2 1 1 3 3 3 1  •  » » » 16 months ago, # ^ | ← Rev. 2 → 0 Can you tell a counter example for this code as well https://codeforces.com/contest/1481/submission/106608493 •  » » » » 16 months ago, # ^ | +1 1 3 2 1 2 1 1 1 1 3 1  •  » » » » » 16 months ago, # ^ | 0 Thanks for the help man. •  » » » » » » 16 months ago, # ^ | 0 Can you tell a counter case for this code as well. https://codeforces.com/contest/1481/submission/106676613 •  » » » » » 16 months ago, # ^ | 0 Can you tell a counter case for this code as well. https://codeforces.com/contest/1481/submission/106676613 •  » » » » » » 16 months ago, # ^ | 0 1 3 3 2 2 2 2 1 1 1 3 1  •  » » » » » » » 16 months ago, # ^ | 0 Thank you. •  » » » 16 months ago, # ^ | 0 Thanks man  » 16 months ago, # | 0 Does in Ques A if the changing position was allowed would the answer be different? •  » » 16 months ago, # ^ | +5 as long as we can delete , changing positions won't make any difference .  » 16 months ago, # | ← Rev. 3 → 0 What is case 57 of test 3 ?My logic is same as editorial idk why failing ? codeEDIT: nvm Got it!Btw if there's any way to see a complete test case please comment down! •  » » 16 months ago, # ^ | 0 I'm also wa at case57 test3, have you catch the bug? •  » » » 16 months ago, # ^ | 0 i also got it now. 1 3 4 aa b*a bb this case can cause my fault •  » » 16 months ago, # ^ | 0 Failing on the same case, what is different about this case?  » 16 months ago, # | ← Rev. 2 → 0 {deleted}  » 16 months ago, # | ← Rev. 3 → +3 We don't need to find x,y,z in problem D because any three node will given us answer , so take first and second and third node and now in a loop 1->2->3->1 there will be atleast two continuous edges which are equal, this will make implementation easy , you can see my submission 106600375  » 16 months ago, # | 0 hi there! great contest, although I am still struggling with problem C.here is my submission: https://codeforces.com/contest/1481/submission/106619632probably there is some obvious reason why it fails but cannot find it, cannot deduce that also from test cases, anyone could advise? cheers! •  » » 16 months ago, # ^ | +1 Check with this input: 1 2 2 1 2 1 1 2 1 I believe your line last_index = colors_later.index(painters[-1]) is problematic. There is no guarantee that this index will be chosen by any painter, as shown by the input above. •  » » » 16 months ago, # ^ | 0 Spot on mate! Thanks a lot, this was indeed the problem here.  » 16 months ago, # | 0 Cool problemset :3  » 16 months ago, # | +10 Using the technique described in this blog, you can improve the time complexity of problem F by a factor of$w$, where$w$is the word size of the machine (usually$32$or$64$).Instead of using the deque method to solve our 0-K knapsack, we instead decompose our items$(a_i, m_i)$into$log_2(m_i)$items and perform 0-1 knapsack on those.Usually, this would add a factor of$O(log(n))$, but in this case it is provable that the time complexity still remains$O(n \sqrt{n})$.The improvement comes from the fact that we can use bitsets for the calculation of the knapsack. Transitions are handled by simple OR functions, and tracing back can be handled by iterating over all new elements of the bitset. This speeds up the dp transitions by$O(w)$, allowing a complexity of$O(\frac{n \sqrt{n}}{w})$.Submission: 106619988  » 16 months ago, # | -21 Kilani The given code in this tutorial for 1481C — Fence Painting is giving wrong output for some cases.For example:INPUT:1 2 2 3 5 8 9 8 8OUTPUT(incorrect):YES 1 1Correct OUTPUT: NO •  » » 16 months ago, # ^ | ← Rev. 2 → +13 That input is invalid. All colors are in the interval$[1, n]$.  » 16 months ago, # | 0 Can someone tell me which case am I missing in problem C.106619774 •  » » 16 months ago, # ^ | 0 Try this: 1 2 3 1 1 2 2 2 1 2  •  » » » 16 months ago, # ^ | 0 Thanks for the test case but I resolved it and my code is still failing. 106624257 •  » » » » 16 months ago, # ^ | 0 1 3 3 1 1 1 2 2 1 2 3 2  •  » » » » » 16 months ago, # ^ | 0 Can you also provide a counter case for this submission?  » 16 months ago, # | 0 106617485 what's the problem with the second test case •  » » 16 months ago, # ^ | +8$k <= 10^9$you're making array of size$10^9$ » 16 months ago, # | 0 Can Anyone Explain me How B is solved And how can I improve my implementation How do I practice ? Please Help!!!!!  » 16 months ago, # | 0 Can Anyone Explain me How B is solved And how can I improve my implementation How do I practice ? Please Help!!!!! 1481B][PROBLEM:1481B - New Colony •  » » 16 months ago, # ^ | 0 If you look at the constraints you can place at most 99*99 boulders(worst case) before they start falling into waste collection system. Worst case will be like 100 10^9 1 1 1 1 ...... 100(last height) // n-1 times 1 and last height is 100. So what you can do is code a brute force solution start at 0th index drop the boulder manually traverse till you find the correct position such that h[i]  » 16 months ago, # | 0 Do we have to print the output in a specific order in problem C because when i tried some other order, i got WA in test case 2? •  » » 16 months ago, # ^ | 0 Take care of the order of painters, as if i  » 16 months ago, # | +61 The editorial for E completely fails to explain the core idea.The idea is that you can choose any element that you move at the very beginning. Then it becomes obvious that you can add any permutation of the chosen elements to the end of the array of non-chosen elements. So, one necessary condition is that the array of non-chosen elements is beautiful. To understand the DP-transitions, note that the the ONLY case where two equal elements can be both inside the chosen and not chosen arrays is if it's at the END of the array of non chosen elements. So, if it's not the last element, the only way we can add it to the array of not chosen elements is to choose everything before it. •  » » 16 months ago, # ^ | +3 Can you please share more insights on this? •  » » » 16 months ago, # ^ | +4 watch neal's explanation for this question. It really helped me. https://www.youtube.com/watch?v=pzwQbiT816w  » 16 months ago, # | ← Rev. 2 → 0 Thank you for the quick editorial! The problems are really great!  » 16 months ago, # | 0 can anyone help me with my problem C? 106634920 or maybe some hack samples ? thanks :) •  » » 16 months ago, # ^ | 0 https://codeforces.com/contest/1481/submission/106635785 here, i recoded it with "stack" instead of "vector", and I passed... What happened? •  » » » 16 months ago, # ^ | ← Rev. 2 → +4 Spoilerin this piece of code you wrote i0) { puts("NO"); return; } }  •  » » » » 16 months ago, # ^ | +4 whoops my fault... :| thank you so much! o7 •  » » » » » 15 months ago, # ^ | ← Rev. 2 → +3 I am facing the same problem 109694896. What's wrong? The spoiler's missing •  » » » » » » 15 months ago, # ^ | ← Rev. 3 → 0 I tried to stress-test your solution and got this test: Spoiler1 4 3 1 2 4 3 3 2 3 4 3 2 3 the actual answer is "NO" but your solution prints "YES".hope it helps •  » » » » » » » 15 months ago, # ^ | ← Rev. 3 → +3 Thanks! I immediately find out it should be rep(i,1,n+1)if(need[i].size()!=0)ok=false since the color is index from 1 to n, not 0 to n-1. This is inconsistency of the index. I am aware that I could have such bugs but unable to find a counterexample. Thank you so much. Exactly the same fault as hehepig. I should use for(int i=1; i<=n; i++) encounting such inconsistent index next time to avoid messing up myself. •  » » » » » » » » 15 months ago, # ^ | ← Rev. 3 → 0 Yeah, this happens sometimes. In the contest I wrote m instead of n but it was good that I found out this bug in the contest. solution, wrong, what I changed •  » » » » 15 months ago, # ^ | +3 xD in need of help. What's the fault of that code  » 16 months ago, # | 0 106561762 Can anyone spot the bug in my code why it is not accepted? •  » » 16 months ago, # ^ | +1 what if (x!=0 and y==0) or (x==0 and y!=0) •  » » » 16 months ago, # ^ | 0 Can you please check my code why it's getting WA problem D  » 16 months ago, # | 0 In problem div2-D, what if it says path must form a circle i.e. start and end point are the same and also you can't visit same vertex or edge twice?  » 16 months ago, # | +1 Thanks for such a great contest and fast editorials! I love all the interesting problems especially F!  » 16 months ago, # | 0 Problem D is exciting but problem E maybe too classic? •  » » 16 months ago, # ^ | 0 And also thanks for the quick and good editotial! •  » » 16 months ago, # ^ | 0 Hey, can you point me to some problems similar to E? I kind of understood the editorial but feeling shaky about how to arrive at the basic intuition  » 16 months ago, # | ← Rev. 2 → 0 Could anyone help me find my mistake in this code of problem C?It got WA on 2 but I can't see the exact test data.Here's the code : 106592765Thx a lot. •  » » 15 months ago, # ^ | 0 You must have inconsistent index usage. I don't look closely into your code but remind yourself that this problem index is from 1 to n, NOT 0 TO N-1. Probably you miss a particular index, check it.  » 16 months ago, # | ← Rev. 2 → 0 My solution for C is giving WA I've implemented it same as in editorial Please help me find what's wrong with my solution 106644778 •  » » 16 months ago, # ^ | ← Rev. 2 → 0 The loop which you were using for the greedy distribution of the painters is going till i=m-1, but you have already given the painter for the last one, thus the loop should go only till i=m-2. I changed that and got your solution accepted. 106646446 •  » » » 16 months ago, # ^ | 0 But even if i goes to m-1(last painter) it will execute else condition only and assign ans[m-1]=ind which did not change the ans as it is already assigned to ind . Please explain if im missing something •  » » » » 16 months ago, # ^ | 0 I explained C in my blog https://codeforces.com/blog/entry/87540. I hope you like it. •  » » » » » 16 months ago, # ^ | 0 Your link doesn't work. It redirects to the tutorial of this contest. •  » » » » » » 16 months ago, # ^ | ← Rev. 2 → 0 I deleted it. but here is my comment https://codeforces.com/blog/entry/87523?#comment-757834 •  » » » » 16 months ago, # ^ | 0 No, it is not necessary that it will execute the else condition. It can execute the if condition too. Consider the case that s[C[m-1]].size() = 1, then it will execute the if condition and then when you are checking the size of the s[C[i]] (after that in which you are setting the 'flag' to zero), it would be empty and thus 'flag' won't be set to zero. But, in reality, you already have painted the last one earlier and thus, s[C[m-1]] shouldn't have been empty and flag should be set to zero. And this case occurs because a painter can paint only one fence and you have already chosen the fence for the C[m-1] when you are finding the value of 'ind'. •  » » » » » 16 months ago, # ^ | 0 Oh I got it now thanks dude  » 16 months ago, # | +3 B will be more interesting when h[i]<=10^9. •  » » 16 months ago, # ^ | +16 Then it wouldn't be B :p  » 16 months ago, # | +3 Can anyone solve my problem: In problem E, when i is not equal to l[a[i]], we move all the books except for the color a_i, even if it is on the right side of R_a[i]. Why? •  » » 15 months ago, # ^ | ← Rev. 2 → 0 The idea behind this is that for example if your original array is 1,2,1,1,1,2,2,2,2,3 you can't say that the numbers that will be unchanged from 3rd number(which is 1 ) to the last one since in this case you need to move the first one and there is no sequence to move the first one to be beside all the other ones (you can read rananjay23 's comment) so you want to have subsequence of numbers such that except for the last color in the subsequence all the colors occurrence (count) in the original array is the same as the subsequence so let's define dp[i] to be the length of the longest subsequence that satisfies that all colors count in the original array is the same as the subsequence except possibly for the last color in the subsequence so if i not equal to l[a[i]] and you considered only the number of colors in the range from i to r[a[i]] + dp[r[a[i]]+1] so in this case your dp[i] won't represent what we want it now will count for subsequences that have number of occurrence not equals to the original number of colors e.x. a=[1,2,2,1,1] so your dp[2]=3 (zero indexed) which is incorrect it should be 2 since you can't take the sequence 2,1,1 but your possible sequences so far are [2] the 2nd 2 or [1,1] the 2nd and 3rd 1 and the longest of them is [1,1] so dp[2]=2  » 16 months ago, # | 0 Problem D can be solve using dfs + random(for even m). It's my code: https://pastebin.com/29jv66h3  » 16 months ago, # | 0 I am getting WA in div2-D. Can someone help me find the error in this solution? Submission Link  » 16 months ago, # | ← Rev. 2 → 0 https://codeforces.com/contest/1481/submission/106664046 can someone help me with my approach on C problem. its showing wa on test case 376 in test 2. the need map stores the index in which we need to repaint. the sb map stores a index of every element in b array. the count array is for checking we have enough painters of that color that we need. UPDATE : found the mistake  » 16 months ago, # | +11 In problem E , I failed to understand through editorial completely , so i came up with following thought process while upsolving (might be same as editorial):Note that answer is$n-sum$, where$sum$is largest subsequence of the array similar to$1,1,1,1,1,4,4,4,4,4,5,5,5,5$. Important thing to note here is except the last color ($5$here) , count of all other colors in subsequence must be equal to count in the original array.For example if array was of the form :$1,1,2,1,1,3,1,4,4,4,4,4,5,5,5,5$, then we cannot choose$1,1,1,1,4,4,4,4$because$1$is not the last element in subsequence and we haven't taken all of it's occurrences.Once we have chosen the largest subsequence such that all similar colors in subsequence is consecutive and except last color in subsequence all other color count in subsequence is equal to that in original array , we can see that we can move all other colors greedily to the end of the subsequence .For example if array was$1,1,2,1,1,3,1,4,4,4,7,4,4,5,5,5,5,2$. Then we can choose$1,1,1,1,1,4,4,4,4,4,5,5,5,5,2$as largest subsequence , then we can move the$2$( at 3rd position),$3$(at 6th position) ,$7$(at 11th position) to the end of the subsequence and thus final arrangement will be$1,1,1,1,1,4,4,4,4,4,5,5,5,5,2,2,3,7$.For implementation while iterating we can keep track of largest such subsequence ending with$a[i]$and also largest subseqeunce such that all colors in subsequence have count equal to that in original array (even the last color) . Code is very short for this problem . submission •  » » 16 months ago, # ^ | 0 I think I understood your idea, but could you help me figure out the implementation please? I didn't understand the submission you posted. •  » » » 16 months ago, # ^ | ← Rev. 2 → 0 you can try to see how code works line by line (i.e dry run) by taking samples in question and in my comment .  » 16 months ago, # | 0 I have heard that B can be solved in O(n).Does anyone know how to solve B in O(n) using stack?  » 16 months ago, # | ← Rev. 2 → +4 106663413 Can anyone please point out the error in this code for problem D?Its been hours since I am trying to debug this code but its not getting an AC. •  » » 16 months ago, # ^ | +3 I haven't solved this problem yet, but I think this input is a counter case: 1 3 2 *ab b*a ab* Your code outputs 1 2 1 which I believe corresponds to a non-palindromic string 'ab'`? •  » » » 16 months ago, # ^ | ← Rev. 2 → +3 Yes, I understood that what was the error in it, if (m/2) was odd so I was trying to print aabbaabbaa..... and so on and the last 2 letters would be 'aa' but through my code the last 2 letters were not coming out as 'aa' always, I just had to print d2+1 in place of d+1 at the last line, thanks for pointing out the error.  » 16 months ago, # | 0 Can someone please help me find the error in my submission for the problem C. TIA Here is my submission  » 16 months ago, # | -22 and the shiitiest implementation of the year award goes to problem C. congrats Kilani  » 16 months ago, # | 0 Why if M / 2 is even we cannot write out the vertices in the order x -> y -> z -> y -> x? (Task D). •  » » 16 months ago, # ^ | 0 Of course, we can. Problem was in my code. Sorry :(  » 16 months ago, # | 0 My Submission for C is exactly the same as editorial. Why am I getting WA at test 2? Pls help.  » 16 months ago, # | 0 Can someone please help me understand why my solution for problem B is WA? I'm placing boulders until there is no i that satisfies a[i]  » 16 months ago, # | ← Rev. 3 → 0 https://codeforces.com/contest/1481/submission/106907738can anyone tell me whats wrong in the code it is giving wrong answer on test 3.D  » 16 months ago, # | 0 problem E was just amazing !!!  » 16 months ago, # | +3 So for the problem E, why if i != l(ai) cant you just leave all ai unmoved and move only those between i and r(ai) same as if i = l(ai) and add dp(r(ai) + 1)?  » 16 months ago, # | 0 If you can read Chinese，I'd like to recommend my blog  » 15 months ago, # | 0 For problem C, why do you choose$b_x \not= a_x$? Wouldn't this solution still work if$b_x = a_x$as long as$b_x = c_m\$?Thanks!
 » 15 months ago, # |   0 Can someone help with this: https://codeforces.com/contest/1481/submission/107022262I did almost same explained in tutorial, but there is something wrong with my code, it doesn't pass all test cases, it stuck on test case 59 or 3rd set. It shows, that output string isn't a palindrome. Any help effort is appreciated.Thank you!!
 » 15 months ago, # | ← Rev. 2 →   0 https://ideone.com/hOl1eGCan anybody tell me the mistake in this solution for problem D. I am getting the following error in test case 3 wrong output format Expected integer, but "YES" found (test case 59)
 » 15 months ago, # | ← Rev. 2 →   +3 Problem E — Can anyone tell me how to get the answer in 4 moves for the following input? 8 6 6 1 6 3 1 8 8 10, AC program outputs 4.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +1 1: move first 8 to end, 6 6 1 6 3 1 8 8 10 82: move 10 to end, 6 6 1 6 3 1 8 8 8 103: move first 1 to end, 6 6 6 3 1 8 8 8 10 14: move the other 1 to end, 6 6 6 3 8 8 8 10 1 1
 » 10 months ago, # |   0 Problem B is a good problem but the solution to it is quite bad
 » 8 months ago, # |   0 Kilani In problem F, when ans == mx + 2, why do you sort the vertex by its size as a subtree out of greed ? Can you explain it
 » 4 months ago, # |   -10 Why does problem A always has to be observant one? Don't have new ideas?????????????????????????????????????????????????????????????????????????????????????