DS007's blog

By DS007, 3 years ago,

Many thanks to infinitepro, BledDest and alimq for helping me write the editorials.

Solution

Solution

Solution

Solution

Solution

UPD: Also, have a look at this comment for an explanation of the sample test case of C.

• +114

| Write comment?
 » 3 years ago, # |   +106 My sincere apologies for misjudging the difficulty of B. Most of the testers solved it hence I thought it was fine for a div2B. Hope you all enjoyed the other problems.
•  » » 3 years ago, # ^ |   +34 It was just unusual, I guess people (of course including me) fell for some short greedy type approaches. Problems were nice.
•  » » » 10 months ago, # ^ |   0 Congrats to "DS007" for making one of the worst contests in code forces history. I strongly recommend you to make more contests.
•  » » 3 years ago, # ^ |   +37 In hindsight it was fine. It gives the impression that it suffices to reduce the input to a sequence of -1, 0, 1, and work on that. At least I did that — and it felt really clever — until I got WA.
•  » » 3 years ago, # ^ |   -234 Fcuk off to you and your problem setting.
•  » » » 3 years ago, # ^ |   +10 This comment that's your account, right?
•  » » » 3 years ago, # ^ |   0 Fuck you is right.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 I disagree. Although I didn't solve it and it ruined my contest, I think This is an excellent problem for Div 2 B. It requires a one simple observation and then can easily be solved by doing a case by case analysis. it's trivial to calc the initial intimidation, init. then, by the key fact that changing a_i affects at most 3 elements, our output = init — delta, where delta = 3, 2, 1, or 0. If one carefully analyze the conditions under which delta = 3, then repeat for delta = 2 ..., one figures out the complete solution for sure. I like it. thank you.
•  » » » 3 years ago, # ^ |   0 I applied the same concept. However, I have missed some case. Can you let me know some easy test case so that I can figure out my mistake? I am getting WA in test case 3 (23rd token)
•  » » » » 3 years ago, # ^ |   0 23rd Token : 23 16 9 4 14 9 4
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you let me know some easy test case or points that I missed so that I can figure out my mistake? I am getting WA in test case 3 in DIV2B(163rd token). Thank you.
•  » » » » » » 3 years ago, # ^ |   0 2 6 1 5 10 4 6 12 6 10 8 5 15 7 6answer — 1 1
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 how did you find the 23rd case?
•  » » » » » » 3 years ago, # ^ |   0 add this:"if(count==23) {cout<
•  » » 3 years ago, # ^ |   0 its alright, This will help us improve even more.I have a doubt regarding the solution for the problem 2. What I did was that I found the max consecutive extremes(hill or valley) then from the total sum I subtracted the min(3,consecutive). So basically if there are 3 consecutive extremes then we can neutralize it and reduce it by 3. Similarly if there are 2 consecutive extremes then we can change the vaues and reduce the sum by 2. If there is atleast extreme then we can reduce it by at least 1. Please tell me what is wrong with this logic? Where have I gone wrong, so that I can improve in the next contest.Thank you
•  » » » 3 years ago, # ^ |   +3 I also did same during the contest but run your code on this test case 23 16 9 4 14 9 4. I think your code will give 0 but answer is 1.
•  » » 3 years ago, # ^ |   0 I found my mistake overnight it was just the index when I was checking how my change affected the integer on my left... Like instead of setting i>=3 (thus the integer on my left has an integer on its left) I said i>=2 and in 5 hours of debugging I could not see it.The problem for ranking up from Expert or Specialist to CM is not the concept of the problems. The problem is actually being able to write code with 0 bugs. Like I understand how to improve myself when it comes to the concept of problems (learn more algorithms and solve more problems) but I don't see how can I improve myself into not making mistakes while coding, I do believe solving more problems won't really help one stop making mistakes when implementing a solution.. The focus one has when implementing IMO comes from 3 importnat factors genetics, sleep and food. I will search for medication that can help one stay more focused like royal jelly and see if it makes any difference.
•  » » » 3 years ago, # ^ |   +1 Hi dude, I did not participate into the actual contest but tried div2 2 in practice and spend 2 hours trying to figure out why I got WA on Test case 3 and it was a simple index error, I was having a hill_or_valley(i) function and I was assumming that i is between 2 and n — 1, but that was not always the case.Totally agree that you can practice algorithms and logic, for example this div2 c idea has completely caught me off guard, but I also believe that you can practice not making mistakes. You can take for example WA submissions to div2 b and try to find the mistake in other people's code.
•  » » » » 3 years ago, # ^ |   0 Yes I do agree that you can partially improve your debugging skills but here is the thing: Even spending a minute in debugging is costing. I'd rather spend 5 more minutes writing the correct code rather than loosing a submission (which may cost 10 minutes penalty in some cases) and then have to debug that 1 extra minute. I bought coffee for tomorrow and we will both see if the experiment will fail or succeed.
•  » » 3 years ago, # ^ |   0 In problem div 2 C in 1ST LINE OF PROOF IN EDITORIAL::: DS007IT SHOULD BE CRITERIA 1 NOT 2 ...PLEASE CORRECT IT.
•  » » » 3 years ago, # ^ |   0 No, I don't see what wrong in the editorial.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 My sincere apologies for saying DS007 as asshole
 » 3 years ago, # |   +3 Please fix this => "Unable to parse markup [type=CF_MATHJAX]" in problem C and also I am not able to see the submissions.
 » 3 years ago, # |   +6 The editorial will be translated to Russian tomorrow.
•  » » 3 years ago, # ^ |   0 bruh
 » 3 years ago, # | ← Rev. 2 →   +16 I can't view any of the author's submissions. It gives me the error: You are not allowed to view the requested page.UPD: Fixed!
 » 3 years ago, # | ← Rev. 2 →   +26 Hard, but nice quality contest! Learned the techinique of multiplying two dp values and adding them leading to the answer in D. Thanks :)
•  » » 3 years ago, # ^ |   0 Can u explain to me that part about multiplying dp[i][j] * dp[i][k-j] where 0=
•  » » » 3 years ago, # ^ |   0 How does that tell us that a particular element at index i occurs in a path where it is not the beginning or the end of it
 » 3 years ago, # |   +16 Really great explanation to C, probably one of the most beautiful problems in recent rounds. The graph modeling approach is amazing!
•  » » 3 years ago, # ^ |   0 ScrappyDoo Can you please explain the idea ?
•  » » » 3 years ago, # ^ |   +16 I'll suppose that the part about vertices and edges is clear. Suppose that we draw a rooted tree for the following example: 2 3 4 1 2 3 4 5 6 7 8 9 Notice that a-(b-c) is actually equal to a-b+c. This corresponds to the following graph example: a | c | b First we remove b, and change c for b-c, then we get the following tree: a | (b-c) Then we remove (b-c) and change a for a-(b-c) leading to: a-b+c This implies that we will be calculating our final answer as difference of sums of elements on even levels and sums on odd levels.Because nodes can connect only elements from different sets we observe that we can create a tree with at least 3 levels, which turns out to be just enough to get all the nodes in a tree. Here's an example of such tree using the previously mentioned sets:  1 / \ 3 6 / / \ \ / \ 2 7 8 9 4 5 What do we see? We can include just two elements from two different sets on our odd levels and all other elements on even levels. So if mn1 and mn2 are the two smallest values that don't belong to the same set (one belongs to 1. and other to 2., one belongs to 2. and other to 3., or one belongs to 1. and other to 3. set) the answer in this case is: sum of all elements - 2 * (mn1 + mn2) As we already counted mn1 and mn2 in total sum we have to remove them twice. There's another case where we'll store one complete set on the second level and two other sets on level 1 and level 3 (I'll leave it as an exercise for you). Again we take the minimum of those three cases and compare them to our answer.I hope this explanation was clear. TBH I'm not too good at doing these, so feel free to ask about any part of my solution.Here's a sample implementation I've done for you to understand completely:https://codeforces.com/contest/1467/submission/103829704
•  » » » » 3 years ago, # ^ |   +3 ScrappyDoo Thank you for the wonderful explanation. This is indeed a beautiful problem :)
•  » » » » » 3 years ago, # ^ |   +1 No problem, glad you found it helpful! :)
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Great explanation, but I think there is an error in the tree for a-b+c. The tree would be:a | b | c
•  » » » » » 3 years ago, # ^ |   0 Yeah, I see I messed that part now. Thanks for the correction!
•  » » » » » » 3 years ago, # ^ | ← Rev. 8 →   0 Hi, I thought about it a lot but still can't figure out how to determine when to add the whole set. Could you please give an example of it?UPD: I think I figured it out. 3 3 3 a b c d e f g h i Here we can do this, lvl 0 -> a lvl 1 -> d, g lvl 2 -> b, c, h, i connected to d lvl 2 -> e, f connected to g So, we subtract d and g. But we could have also done, lvl 0 -> a lvl 1 -> d, e lvl 2 -> b, c connected to d lvl 2 -> g, h, i connected to e lvl 3 -> f connected to g Here we are able to construct the tree and delete all items from bag 2 (d, e, f).If removing the whole bag gives a better result than removing 2 items from different bags then we remove the whole bag. i.e. if (d + e + f) < (d + g) and so on.
•  » » » » » » » 3 years ago, # ^ |   0 I think that you are overcomplicating the substraction of whole set, here's a simpler idea I've come up with.Put single element from first set on the first level (say a).Put all the elements from second set on the second level (d, e, f) and connect them with the only element from the first level.Lastly connect all the remaining elements with any of the elements from second level and put them on the third level.Here's one of approaches which solves your provided input: First level: a Second level: d e f, connected to a Third level: b c g h i, connected to d We know that all the elements from last level belong to either first or third level so we can connect them with any of the elements that belong to second level (as they belong to the second set). The story is same for the first two levels.But yes, your approach also works as there are many ways to construct a tree here.And answer to your second comment — No problem, glad I could help!
 » 3 years ago, # | ← Rev. 5 →   +18 I have a different solution for problem E. I'll explain it here. Let me know if you have any questions.Root the tree arbitrarily. Let's define $x[u]$ as the number of paths starting at node $u$ such that the value of the node at the other end of the path exists multiple times in the path. A node $u$ is distinctive iff $x[u] = 0$. Suppose you know $x[u]$ for some node. What paths could change the answer for a child $c$? There are two possible types: paths starting from $u$ that ends in $c$'s subtree s.t. they end with a node with the same value as $u$, and have exactly 2 nodes with the same value ($u$ and the ending node) paths starting from $c$ that end at a node that's not in $c$'s subtree s.t. it ends with a node with the same value as $c$ Using these facts, run a dfs starting from the root. You can pre-calculate the number of paths starting at each node of types one and two using a map. Using this, we can calculate $x[u]$ given $x[parent of u]$ (you add all paths of type 1 and subtract all paths of type 2). The answer is the number of nodes $u$ with $x[u] = 0$. Here's a link to my accepted submission: 103931989
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 This fails on 4 1 2 1 1 1 2 2 3 3 4 (Test 104)It's because the '1,1' path in the subtree of 2 isn't accounted for by your two possible types.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 I've edited my code to account for those paths. The general idea is still the same. Lmk if you find another hack test.Edit: This submission was hacked too, I'll try to fix it again.Edit 2: I fixed it, it was a small mistake (I had to swap the order of two lines)
•  » » » » 3 years ago, # ^ |   0 Try printing out the pv values in your dfs2 method on this case: 12 1 3 3 1 1 1 1 1 1 1 3 1 1 2 2 10 1 3 3 4 7 9 3 5 5 7 7 8 1 11 11 12 3 6You should see that many of these values are greater than 11 (which shouldn't be possible because given some fixed vertex, there are at most 11 other nodes a path can end at). While your code technically gives the correct answer on this case (as it's trivially 0), for your type 2 paths, you only want to consider the number of paths starting from c which end at a node that's not in c's subtree and have exactly 2 nodes with the same value along the path (similar to the condition in type 1). Not accounting for this results in massive over-counting which accumulates in the pv values.I'm not sure how you'd actually efficiently compute this in one dfs.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 I realized that too, but it doesn't actually matter. The only cases in which I over counted don't actually matter, since everything in that subtree isn't distinctive anyway. On an unrelated note, the tests in this problem are apparently pretty weak considering my first solution was hacked on a really simple test case (but you can't really blame the authors for this since there are so many possible solutions).
•  » » 3 years ago, # ^ |   +3 Thanks a lot
•  » » 3 years ago, # ^ |   +8 Problem E is obviously a lot of ways to do it.
•  » » » 3 years ago, # ^ |   0 Can you say how you solve it ?
 » 3 years ago, # |   +88
 » 3 years ago, # | ← Rev. 5 →   +9 Can anyone explain/provide test case of why the noob method of finding cases of decreasing 1,2,3 hills/valleys and writing if statements for it does not work in problem B .My submissioncases like this also run fine161 3 5 2 4 6There's something else Im missing.update : 2,22,23,14,18,18 is the case that breaks my codethanks :)
•  » » 3 years ago, # ^ |   0 same doubt my submission
•  » » 3 years ago, # ^ |   +5 1 3 5 2 4 6 You have (3 5 2) and (5 2 4) but you can't fix them both without producing extra one
•  » » » 3 years ago, # ^ |   0 thanks:)
•  » » » 3 years ago, # ^ |   0 These cases are handled in my code, there something else I'm missing. Any other test case ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 Here is a test case that fails the method you describe:23 16 9 4 14 9 4I think my method was the same as yours. Under our method, it seems that, since the first 4 is part of valley 9-4-14 and hill 4-14-9, that we can eliminate both of those hills/valleys by simply changing the 4. However, that is not possible, since eliminating the 4-14-9 hill requires 4 to be increased to at least 14, which will create a new hill (a 16-9-x hill).
•  » » » 3 years ago, # ^ |   0 I think this corner case can be summarised as destruction of a hill compulsively creates a new valley or hill and vice versa.
•  » » » 3 years ago, # ^ |   0 For these types of cases, my code runs fine. For the input you gave my output is 1. Any other test case?
•  » » » » 3 years ago, # ^ |   0 what is your answer for test case 1 3 1 3 5?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 the code works for this test case its output is 0. The test case that would fail is:2,22,23,14,18,18(Conditions for handling hv and vh pattern fail).
•  » » » » » » 3 years ago, # ^ |   0 thanks :)
•  » » » » » » » 3 years ago, # ^ |   0 Can you tell me the intuition behind the condition. I couldn't figure it out.
•  » » » » » » » » 3 years ago, # ^ |   0 It's just observation/hit and trial ..also there is a better way to solve this (the tutorial one) without caring about the corner cases.
•  » » » » » 3 years ago, # ^ |   0 0 . I guess its right
 » 3 years ago, # |   0 Can someone plz explain c in easy way ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +11 Ignoring the proofs of my claims, first, you calculate the sum of all numbers in all the bags. Then from this, you subtract 2 * min(sum of the 2 smallest numbers such that they appear in different bags, minimal sum of all numbers in one bag).
•  » » » 3 years ago, # ^ |   0 But what is reason behind this? Can u just give a brief ..bcz i am unable to get editorial
•  » » » » 3 years ago, # ^ |   +7 I have put the best proof that we could come up with in the editorial. If you want to look at it from a different perspective, try to work out how the numbers would change after an operation, and how you can make the net effect of some number positive.Let's say that you choose bag 1 as the final bag. Then all numbers in bag 1 can be made positive. Now we try to make all elements in bag 1 positive by passing them through the minimum number in bag 2 and vice versa. However, if the net effect of this turns out to be negative, then we just flip the signs of all these numbers.
•  » » » » » 3 years ago, # ^ |   0 DS007 are there any similar problems to Div2C? I am encountering this variety of problem for the first time.
•  » » » » 3 years ago, # ^ |   +5 I found the explanation in the editorial not super intuitive (though it makes for a nicer proof).Less formal: Essentially, you pick one number to be your final number. Then you can add any number to it, buy passing it off twice. Now you have to empty two bags, so you cannot pass the last number in the bag and therefore you subtract the minimum (instead of adding it, therefore *2). Alternatively, you can also do what happens in the first example test case and subtract one complete bucket if that is cheaper than the smallest sum of two minima.
•  » » » 3 years ago, # ^ |   0 My first idea to the problem was, that we subtract one big number from some small number, then subtract that negative difference from another big number to get a "bigger" number, than subtract that from some small number, to subtract that negative number again... and so on.And I still not get the prove why this is not the optimal strategy. Or is it, somehow?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 I went along the same lines and decided I need to create the largest possible negative numbers in two bags then finally add it to the positive numbers in the third bag. Got WA on 6. Will try some more and check if it takes me anywhere.UPD : This does work,just got an AC. First observation is we keep one bag aside and create two big negative numbers in each of the other two bags. If you can reach this stage the answer is the sum absolute values of all the numbers.The following is how to create these big negative numbers. Let's say the sum — minimum(note not just sum so asm + amin = sum of numbers in a) and minimum of the last two bags is asm,amin,bsm,bmin.Now we compare bmin with asm and bsm with amin. We are trying to keep as much of the sums as possible by subtracting against the smallest number in other bag. We take abs(bmin-asm) and abs(bsm-amin) as it is possible that the minimum turns out to be larger than the other bags sm. These two are our large negatives.There is one edge case to handle however if either of the bags happen to have just 1 element. We take abs(sum of a — sum of b) as our only negative.How to choose which two bags to do the operations on? Just try all 3 possibilities.Here is my solution https://codeforces.com/contest/1467/submission/103854808
•  » » » » 3 years ago, # ^ |   0 I think it's correct, tho you have not mentioned your entire approach but I think, I've done something similar, maybe if this helps. 103844818
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 In my opinion, the easiest method to understand this problem is by analyzing the process. It's easy to see that each method of combining all the elements to obtain one single element can be reduced to some arithmetic expression.For example If I'm having three sets of forma1, a2 b1 c1, c2if I try to move c2, a1, a2 to the second set, and then everything to the third set the answer will be : c1 — (b1 — c2 — a1 — a2) = c1 — b1 + c2 + a1 + a2.From now on, if you do some kind of brute force where you try every possible way of combining the elements you will observe that there are two possible types of outputs :1) Two random elements from dfferent sets gets subtracted from the sum of the other elements. (or twice subtracted from the total sum).2) A whole initial set gets subtracted from the sum of the other elements (or twice subtracted from the sum).I know this is kind of a dumb way of observing the pattern but actually I do think it might help a lot of times.
•  » » » 3 years ago, # ^ |   +3 Hi, could you please explain how you determined the point 2 (1 whole initial set gets subtracted) ?
 » 3 years ago, # |   +6 https://youtu.be/Q8mVSk9VBlc if anyone is stuck in C.
 » 3 years ago, # |   +8 The solution code in problem C is incorrect. If you submit it to CF, it gives the verdict Runtime Error. To fix this, change the return type of the solveTestCase function to void.
•  » » 3 years ago, # ^ |   0 I had tried all the solutions in c++17 before writing the blog, and they all gave me AC. Which version of c++ did you submit in?
•  » » » 3 years ago, # ^ |   +6 I submitted in 64 bit. Here's a link to my submission: 103831188
•  » » 3 years ago, # ^ |   0 An identical issue is answered in the stackoverflow thread
 » 3 years ago, # |   -58 what a land contest
•  » » 3 years ago, # ^ |   +32 what a land person
 » 3 years ago, # |   +13 Sorry but i'm confused with answer for problem D. I understand the building of dp but i dont understand the build of a[i][j] because when you take number of paths that end with i (dp[i][j]) why does it mean that the answer will be that multiplied with number of pats starting with i(because some of the paths in dp[i][j] may have a[i] several times so doesn't that change things?) Thanks in advance for the answer
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 dp[i][j] = number of paths of length j that start or end at i. a[i][j] = number of paths of length k where i appears after exactly j moves.To achieve such a path, you must start from a path of length j that ends at i. From here, you have multiple choices to complete the path. For every path of length j that ends at i, you can complete it in dp[i][k-j] ways by starting at i and moving the remaining k-j moves. Hence a[i][j] = dp[i][j] * dp[i][k-j]
•  » » » 3 years ago, # ^ |   0 Oh okay i get it now. Thanks for thr explanation :)
•  » » » 3 years ago, # ^ |   0 I am not getting how the formula of cnt[i] is valid for the case when robot moves back and forth about a[i].can you pls explain giving examples.
•  » » » » 3 years ago, # ^ |   +2 Yes, it's a very common confusion on such problems.When use "cnt[i]+=(dp[i][j]*dp[i][k-j])", it's possible that the robot walk on a[i] more than once in its first (j-1) steps or its last (k-j) steps? And the answer is: absolutely yes.But it doesn't matter, when we use "cnt[i]+=(dp[i][j]*dp[i][k-j])", it means the number of paths whose j-th step are on the a[i], and iterate for j we can get the sum of the ways. For example, if there is a path which stay at a[i] in its 1st step and 3rd-step, you may think this path contribute 2 for a[i](and it's correct), but in our method, this path contribute 1 while we calculate "cnt[i]+=dp[i][1]*dp[i][k-1]" and contribute another 1 while we calculate "cnt[i]+=dp[i][3]*dp[i][k-3]".To conclude, cnt[i] in this problem can be decomposed by paths(yours) or j-th step(editorail's). Both are correct but only the later one works for this problem.
•  » » » » » 3 years ago, # ^ |   0 can you please explain a little, why dp[i][k-j] is multiplied? Thanks
•  » » » » » » 3 years ago, # ^ |   0 Hint: dp[i][j] means not only "paths with length=j START at i", but also "paths with length=j END at i" (consider reverse the paths).
•  » » » » » 3 years ago, # ^ |   0 thanks understood :)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Thank you so much fried-chicken for the explanation!
•  » » » » » » 3 years ago, # ^ |   0 No problem :)
•  » » » 3 months ago, # ^ |   0 1) To take contribution of each cell in all paths 2) To take contribution of occurence of cell at index j in all pathsAre both 1 and 2 same except one we take in given array and other in path(which is another array) ?
 » 3 years ago, # |   +9 WA on Pretest 3 of Div2B must be the biggest pandemic of 2021. Unfortunate :(
•  » » 3 years ago, # ^ |   0 I don't understand what's wrong in my sols, I'm also getting WA on pretest 3. Your help would be appreciated!https://codeforces.com/contest/1467/submission/103802598
•  » » » 3 years ago, # ^ |   +3 the testcase is 1 6 1 2 3 1 2 3 i believe
 » 3 years ago, # |   0 My solution for problem C failed on test case 17. Can anyone please suggest an easier case on which this solution is failing?
•  » » 3 years ago, # ^ |   0 1 2 378 94 10 12 Solution: 36(Ex: Subtract everything but 4 from 7 and then subtract this result from 4)Ans = 4 - (7 - (8 + 9 + 10 + 12) ) = 36 Your code's output: 28
•  » » » 3 years ago, # ^ |   0 Got it! Thank you!
 » 3 years ago, # |   0 Oh, I just got it... What a brute force way for problem B, never thought like that before. I just thought to check every continuous 5 elements and check if they affect the answer by 0,1,2 or 3, and how to check is just divided them into many cases and the contest was in the evening and I just was confused by many cases by myself.Nice problem bro.
 » 3 years ago, # |   0 Div2B was pretty similar to a problem from a recent contest.I don't remember the exact problem or its code. But this is what we had to do.We had to make a swap to minimize/ maximize the total number of minima/maxima/(minima+maxima).
 » 3 years ago, # |   0 I finished a DSU-on-tree solution for problem E during the contest. Here is the reviewed code with comments to explain the idea.
 » 3 years ago, # |   +19 Problem C can be solved in another angle of thought. Without loss of generality, lets assume that the final element will belong to bag A.Now, think of the problem as ans = a1 + a2 + ...an + -b1 + b2 + ...bn + -c1 + c2 + ... cn(Move all but 1 element in A to B. Move all but 1 in C to B. Move all but one in B to C. Now move all back to A. So all the elements except the ones unmoved in B and C will have a -(-) positive contribution to the sum.There is one more possibility. Assume c1 was infinite, so a -c1 is not affordable. So we move all Cs to B and then to A, and ignore moving B twice.Answer in this case will be Sum(A) + Sum(C) — Sum(B). Swap A, B, C and find the max case. 103801386→ Reply
 » 3 years ago, # |   0 Finally became EXPERT !!!
•  » » 3 years ago, # ^ |   +3 same
•  » » 3 years ago, # ^ |   0 Same
 » 3 years ago, # |   -21 I can't seem to figure out the problem in my code for Hills And Valleys Problem.I first count all the hills and valleys. Then I check if any Hill-Valley-Hill or Valley-Hill-Valley combination occurred. If this is true, I decrement the counter by 3. If not true, then I search for Hill-valley or Valley-Hill pair, In this case, I decrement the counter by 2. Else final answer is Counter -1.  #define ll long long using namespace std; int main() { int t; cin >> t; while (t--) { vector arr,vis; int n; cin >> n; for (int i = 0; i < n; i++) { ll int p; cin >> p; arr.push_back(p); vis.push_back(0); } ll int counter =0; for(int i=1;iarr[i-1]&&arr[i]>arr[i+1]) { counter+=1; vis[i]=1; } else if (arr[i]
•  » » 3 years ago, # ^ |   0 1 3 5 2 4 6 check for this case
•  » » » 3 years ago, # ^ |   0 It's answer should be 1?
 » 3 years ago, # | ← Rev. 2 →   0 Can anybody help me figure out why I am getting WA for tc3 in Problem C 103860085
•  » » 3 years ago, # ^ |   +9 It took a long time to figure out and in the end it turned out to be overflow of integer. Since each value can be 1e9 their sum can be near 1e14. Here 10 10 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 » 3 years ago, # |   +3 Problem C. The solution looks interesting yet I find it very hard to understand it. So we want to build a rooted tree ?There is an additional node that is the root ? Any node is a leaf except the root ?What is the definition of valid in : "the constructed rooted tree is valid" ? It would be nice to have a simple example or some references : books, article, similar problems ...
 » 3 years ago, # |   0 https://codeforces.com/contest/1467/submission/103855499Can anyone please tell me, what I did wrong here. It is giving this verdict on 3rd test case "wrong answer 8th numbers differ — expected: '0', found: '1'"
 » 3 years ago, # |   0 Nice editorial for Problem C
 » 3 years ago, # | ← Rev. 2 →   +3 .
 » 3 years ago, # |   0 Can anyone tell me the 23rd case of test case 3?I am just curious to know what's wrong in my code!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Maybe similar with this Input2 6 10 4 2 10 4 3 6 2 4 10 2 3 4 Answer1 1 your output00
•  » » » 3 years ago, # ^ |   0 Legend how did u get it
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I just thought of some test case for which my code could get wa.
 » 3 years ago, # | ← Rev. 2 →   0 Nice and clean editorial solution code! for div 2 B. Thanks.
 » 3 years ago, # | ← Rev. 3 →   0 Actually your code of problem B shouldn't take AC, (int a[N]) and (int tmp = a[i]) tmp and a[i] should be long at least according to the constraints !!
•  » » 3 years ago, # ^ |   0 Nevermind this stupid comment
 » 3 years ago, # |   0 REALLY GREAT CONTEST !! NOW, AFTER STRUGGLING WITH A , I HAVE SOLVE IT NICELY AND I AM BECOME PUPIL NOW.
 » 3 years ago, # |   0 Can anyone please explain problem E. And also some of the topics related to it, which might help in solving it.
•  » » 3 years ago, # ^ |   +3 You can check out my editorial.It is not the best tutorial but it can give you a rough idea. https://codeforces.com/blog/entry/86601
 » 3 years ago, # |   0 Can anyone explain me the below line ? and what is the role of is[] array ?? ans = min(ans, s — is[i — 1] — is[i] — is[i + 1] + isHill(i — 1) + isValley(i — 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
•  » » 3 years ago, # ^ |   0 is[i] denotes whether index i was a hill or a valley initially.In the line that you have mentioned, I remove the contribution of indices i-1,i,i+1 to the intimidation value of the unchanged sequence. Then I find whether these indices have now become hills or valleys and update it accordingly.
 » 3 years ago, # |   0 Can anyone explain for me that why in prob B the answer is equal to (count of hill and valley) — x with x = 0/1/2/3?
•  » » 3 years ago, # ^ |   0 because if you change $a_i$,only $a_{i-1},a_i,a_{i+1}$ can be effected,so x can not be greater than 3.And if there's no hills and valleys,x can not be less than 0.So x is a integer in [0,3].
 » 3 years ago, # |   +8 Wow I don't know how do people solve problems like C. Greedy is certainly not one of my skills. Was it just a blind guess or do you actually find an intuitive way to "prove" your approaches?I found problem D easier to approach, maybe a little bit harder to code but no so much. In fact I had to skip C during contest.Nice problems!
•  » » 3 years ago, # ^ |   0 I was close to solving C on my own — just made a mistake wifh the case with the whole array (I thought it can only happen when whole array has length of 1). I come up with conclusion that we should look for the biggest negative number. By blindly guessing I've realized that we can always connect two elemnents from two groups with all the other elements (e. g. erase all elements besides three twice and than erase them again which ends up being addition, than add one element and erase two that are left), I've even sketched out the edges. The thing is that they weren't supposed to create a graph, I was just tracking what I've used so far. Lmao, turns out I was right.So I'd say I've guessed the graph modeling approach, bu t did so greedily, without any proof, but knew that it was impossible to erase only one element, shich would end up being the intended solution. I've talked to 5-6 people that have solved it — all of them did so without a proof...
 » 3 years ago, # |   +5 VIDEO TUTORIAL FOR DIV 2 PROBLEM B WITH IN DETAIL EXPLANATION OF CREATIVE TESTCASES AND LINE BY LINE CODE HERE IS THE LINK : https://www.youtube.com/watch?v=I4oSzeygRzs HOPE YOU GUYS WILL ENJOY THE VIDEO !!!!
 » 3 years ago, # | ← Rev. 2 →   0 Observe that $dp_{i, j}$ is also equal to the number of good paths of length $j$ that start at cell $i$. I didn't get this part from problem D, how is it the same?
•  » » 3 years ago, # ^ |   0 $dp_{i,j}$ is the number of good paths of length $j$ that end at cell $i$, then the reverse of those paths are paths of length $j$ that start at cell $i$
•  » » » 3 years ago, # ^ |   +3 Oh, that makes sense, I'm wondering how did I miss thinking about the reverse part.Thank you :)
 » 3 years ago, # | ← Rev. 4 →   +7 Nice contest
 » 3 years ago, # |   0 can somebody easily explain C. Three Bags problem??
•  » » 3 years ago, # ^ |   0 You can check out my editorial.It is not the best tutorial but it can give you a rough idea. https://codeforces.com/blog/entry/86601
•  » » » 3 years ago, # ^ |   +3 thank you
 » 3 years ago, # |   0 Can anyone explain this paragraph of editorial of Problem D?Let ai,j denote the number of times cell i appears after exactly j moves in all valid paths of length k. Well ai,j=dpi,j∗dpi,k−j because we can split a path of length k into two paths of length j and length k−j, with the first path ending at cell i and the second path starting at cell i.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 For each i, we want to calculate how many times the cell i occur in all good paths, right ? this is the goal. Let f[i] denote that. Consider a good path of length k [x_0, x_1, x_2, ..., x_k]. Do you see that f[i] is equal to the SUM of the following: the number of times cell i occur in a good path in position 0, PLUS the number of times cell i occur in a good path in position 1, PLUS '' the number of times cell i occur in a good path in position k. So, the task now, for each j in [0, k], we need to calculate how many times a cell i occur in a good path in position j = " After j move" ? Let a[i][j] denote that.Let's now consider how we can calculate a[i][j] for specific i and j. Consider a good path of length k in which cell i appeared after j move, It will look like this [x_0, x_1, ....., cell i , ......x_k]Do you see that this path can be broken down into 2 paths: a path of length j which ends with cell i a path of length k — j which starts with cell i Let dp_en[i][j] denote number of paths of length j ending at cell iLet dp_st[i][j] denote number of paths of length j starting at cell iwe know that any path of the first type can be joined with any path of type 2 to make a length-k path that contain cell i after j move. meaning a path that we should count it in when calculating a[i][j]. Hopefully, It's clear now that a[i][j] = dp_en[i][j] * dp_st[i][k-j]. This is the key conclusion. now one extra unnecessary observation is that dp_en[i][j] = dp_st[i][j] for all i and jwhich means that a[i][j] = dp_en[i][j] * dp_en[i][k-j]The task now is to calculate dp_en[i][j], This is a simple dynamic programming task. Given dp_en[i][j] -> a[i][j] -> f[i] -> ansIf any thing is not clear, please tell me
•  » » » 3 years ago, # ^ |   0 Very well explained , Thank You :)
 » 3 years ago, # | ← Rev. 2 →   0 Problem DI didn't understand solution. But I am now.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Bye !
 » 3 years ago, # |   0 I highly doubt about Problem C solution: the summation of given data should overflow 32bit integer. Any thoughts?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 define int long long
•  » » » 3 years ago, # ^ |   0 Ah. Thanks.
 » 10 months ago, # | ← Rev. 3 →   0 I sincerely apologize for calling "DS007" stupid,asshole,worst,rascal,scoundral,idiot,my foot on your face "DS007"
 » 10 months ago, # | ← Rev. 2 →   0 Problem E honestly feels like it should be 2000/2100, here is an alternate brainless solution:Observations: If there exists some value $x$, such that there are $\geq 3$ occurences of $x$ in the tree, and one occurence lies on the path between some two occurences of $x$, then there is no distinctive root. So firstly, just run a dfs, and check if this condition is satisfied by the tree, if yes the answer is $0$. If the condition is not satisfied, this means all the values (exclude values whose frequency is one) occur in one of the following manners: Case 1: No occurence of $x$ is a parent of another occurence of $x$. Case 2: Only one occurence of $x$ is a parent of another occurences of $x$, call this node $r$. $r$ must lie strictly above the LCA of all the other occurences of $x$. (Red nodes correspond to occurences of some particular x) Let us call the region between red nodes (which contains distinctive roots wrt this value of x), a "good zone". Now, we can just do a dfs while maintaining the set of current good zones we are in. Any node $u$ which is in the good zone of all the values which have $>1$ occurences, will be a distinctive root.Implementation: link