### DS007's blog

By DS007, 16 months 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

 » 16 months 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.
•  » » 16 months ago, # ^ | ← Rev. 3 →   -143 .
•  » » 16 months ago, # ^ |   +34 It was just unusual, I guess people (of course including me) fell for some short greedy type approaches. Problems were nice.
•  » » 16 months 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.
•  » » » 16 months ago, # ^ |   -9 Did a similar thing and was so confident of getting AC while I submitted, only to see a WA. Nice problem for sure!
•  » » 16 months ago, # ^ |   -234 Fcuk off to you and your problem setting.
•  » » » 16 months ago, # ^ |   +10 This comment that's your account, right?
•  » » » 16 months ago, # ^ |   0 Fuck you is right.
•  » » 16 months ago, # ^ |   -36 Apologies accepted. Just return me my rating though.
•  » » 16 months ago, # ^ |   0 well, exactly I pretty like this problem. I should have given up greedy approach at the time I find it's complicated.
•  » » 16 months ago, # ^ |   0 2A did make us sweat too XD !!!thanks for the fast editorial !!
•  » » 16 months 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.
•  » » » 16 months 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)
•  » » » » 16 months ago, # ^ |   0 same here
•  » » » » 16 months ago, # ^ |   0 23rd Token : 23 16 9 4 14 9 4
•  » » » » » 16 months 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.
•  » » » » » » 16 months ago, # ^ |   0 2 6 1 5 10 4 6 12 6 10 8 5 15 7 6answer — 1 1
•  » » » » » 16 months ago, # ^ |   0 CAN U PLZ PROVIDE 8 TOKEN OF TESTCASE 3
•  » » » » » » 16 months ago, # ^ |   0 The 8th Token : 22 9 29 17 17Expected answer : 0
•  » » » » » 16 months ago, # ^ |   0 Can you plz tell me how did you find the 23rd case?
•  » » » » » » 16 months ago, # ^ |   0 add this:"if(count==23) {cout<
•  » » 16 months 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
•  » » » 16 months 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.
•  » » » » 16 months ago, # ^ |   0 thanks, I was searching for this test case.well how did you find it?
•  » » » » » 16 months ago, # ^ |   0 if you have found out why let me know thanks
•  » » 16 months ago, # ^ |   0 After seeing the editorial today, I can easily say that it was one of the most beautiful collections of problems. Thanks for such a nice contest.
•  » » 16 months 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.
•  » » » 16 months 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.
•  » » » » 16 months 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.
•  » » 16 months ago, # ^ |   0 In problem div 2 C in 1ST LINE OF PROOF IN EDITORIAL::: DS007IT SHOULD BE CRITERIA 1 NOT 2 ...PLEASE CORRECT IT.
•  » » » 16 months ago, # ^ |   0 No, I don't see what wrong in the editorial.
 » 16 months 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.
 » 16 months ago, # |   +6 The editorial will be translated to Russian tomorrow.
•  » » 16 months ago, # ^ |   0 bruh
 » 16 months 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!
 » 16 months 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 :)
•  » » 16 months ago, # ^ |   0 Can u explain to me that part about multiplying dp[i][j] * dp[i][k-j] where 0=
•  » » » 16 months 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
 » 16 months ago, # |   +16 Really great explanation to C, probably one of the most beautiful problems in recent rounds. The graph modeling approach is amazing!
•  » » 16 months ago, # ^ |   0 ScrappyDoo Can you please explain the idea ?
•  » » » 16 months 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
•  » » » » 16 months ago, # ^ |   +3 ScrappyDoo Thank you for the wonderful explanation. This is indeed a beautiful problem :)
•  » » » » » 16 months ago, # ^ |   +1 No problem, glad you found it helpful! :)
•  » » » » » » 16 months ago, # ^ |   0 ScrappyDoo hey, just wanted to let you know your explanation really helped!
•  » » » » 16 months 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
•  » » » » » 16 months ago, # ^ |   0 Yeah, I see I messed that part now. Thanks for the correction!
•  » » » » » » 16 months 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.
•  » » » » » » » 16 months 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!
•  » » » » » » » » 16 months ago, # ^ |   0 Yeah, I understood that (the way you explained just now). But I wrote out the tree in that manner so that it doesn't seem like I'm blatantly subtracting 1 set without any logic :P
•  » » » » » » 16 months ago, # ^ |   0 Thanks for the great explanation.
 » 16 months 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
•  » » 16 months 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.
•  » » » 16 months 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)
•  » » » » 16 months 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.
•  » » » » » 16 months 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).
•  » » 16 months ago, # ^ |   +3 Thanks a lot
•  » » 16 months ago, # ^ |   +8 Problem E is obviously a lot of ways to do it.
•  » » » 16 months ago, # ^ |   0 Can you say how you solve it ?
 » 16 months ago, # |   +88
 » 16 months 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 :)
•  » » 16 months ago, # ^ |   0 same doubt my submission
•  » » 16 months ago, # ^ |   0 same thing happening with me. I am also getting wrong answer for 3rd test case. please help me to find out my mistake. my https://codeforces.com/contest/1467/submission/103823564
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   0 thanks:)
•  » » » 16 months ago, # ^ |   0 thanks you!
•  » » » 16 months ago, # ^ |   0 These cases are handled in my code, there something else I'm missing. Any other test case ?
•  » » 16 months 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).
•  » » » 16 months 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.
•  » » » 16 months ago, # ^ |   0 I think it should be (16-9-x) valley
•  » » » 16 months ago, # ^ |   0 For these types of cases, my code runs fine. For the input you gave my output is 1. Any other test case?
•  » » » » 16 months ago, # ^ |   0 what is your answer for test case 1 3 1 3 5?
•  » » » » » 16 months 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).
•  » » » » » » 16 months ago, # ^ |   0 thanks :)
•  » » » » » » » 16 months ago, # ^ |   0 Can you tell me the intuition behind the condition. I couldn't figure it out.
•  » » » » » » » » 16 months 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.
•  » » » » » 16 months ago, # ^ |   0 0 . I guess its right
 » 16 months ago, # |   0 Can someone plz explain c in easy way ?
•  » » 16 months 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).
•  » » » 16 months ago, # ^ |   0 But what is reason behind this? Can u just give a brief ..bcz i am unable to get editorial
•  » » » » 16 months 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.
•  » » » » » 16 months ago, # ^ |   0 DS007 are there any similar problems to Div2C? I am encountering this variety of problem for the first time.
•  » » » » 16 months 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.
•  » » » 16 months 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?
•  » » » » 16 months 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
•  » » » » 16 months 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
•  » » 16 months 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.
•  » » » 16 months ago, # ^ |   +3 Hi, could you please explain how you determined the point 2 (1 whole initial set gets subtracted) ?
 » 16 months ago, # |   +6 https://youtu.be/Q8mVSk9VBlc if anyone is stuck in C.
 » 16 months 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.
•  » » 16 months 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?
•  » » » 16 months ago, # ^ |   +6 I submitted in 64 bit. Here's a link to my submission: 103831188
•  » » 16 months ago, # ^ |   0 An identical issue is answered in the stackoverflow thread
 » 16 months ago, # |   -58 what a land contest
•  » » 16 months ago, # ^ |   +32 what a land person
 » 16 months 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
•  » » 16 months 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]
•  » » » 16 months ago, # ^ |   0 Oh okay i get it now. Thanks for thr explanation :)
•  » » » 16 months 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.
•  » » » » 16 months 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.
•  » » » » » 16 months ago, # ^ |   0 can you please explain a little, why dp[i][k-j] is multiplied? Thanks
•  » » » » » » 16 months 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).
•  » » » » » 16 months ago, # ^ |   0 thanks understood :)
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   +8 Thank you so much fried-chicken for the explanation!
•  » » » » » » 15 months ago, # ^ |   0 No problem :)
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 Is it possible to overcount the contribution by multiplied this both ways ? Why ? PS : I got it, nvm. You've already covered it. Thanks.
 » 16 months ago, # |   +9 WA on Pretest 3 of Div2B must be the biggest pandemic of 2021. Unfortunate :(
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   +3 the testcase is 1 6 1 2 3 1 2 3 i believe
•  » » » » 16 months ago, # ^ |   0 Damn that was good! I got it now. Thank you so much!!
 » 16 months 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?
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   0 Got it! Thank you!
 » 16 months ago, # |   0 From where can I get the complete test data of problem B.
 » 16 months 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.
 » 16 months 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).
 » 16 months 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.
 » 16 months 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
•  » » 16 months ago, # ^ |   0 Can you elaborate more?
 » 16 months ago, # |   0 Finally became EXPERT !!!
•  » » 16 months ago, # ^ |   +3 same
•  » » 16 months ago, # ^ |   0 I missed the chance to become expert 10 times in row. in the last 10 rounds!
•  » » 16 months ago, # ^ |   0 Same
 » 16 months ago, # |   0 awesome tutorial .....so many things to learn.
 » 16 months 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]
•  » » 16 months ago, # ^ |   0 1 3 5 2 4 6 check for this case
•  » » » 16 months ago, # ^ |   0 It's answer should be 1?
•  » » » 16 months ago, # ^ |   0 The answer should be 0 according to me and program is also giving 0. There is a single valley at 5,2,4 which would be eliminated if we change 2 ->4. so answer 0.
•  » » » 16 months ago, # ^ |   0 Found mistake on test case 23rd Token : 23 16 9 4 14 9 4 Expected answer : 1 Thanks for your help.
 » 16 months ago, # | ← Rev. 2 →   0 Can anybody help me figure out why I am getting WA for tc3 in Problem C 103860085
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   0 Yes I did replace the accumulate function with a manual loop to compute the sum and my solution got accepted. Btw thanks a lot for helping me out. Wishing you luck in your future contest.Here's the AC solution 103862699
•  » » » » 16 months ago, # ^ |   0 The following will also work; accumulate(all(a[i]), 0ll); 
•  » » » » » 16 months ago, # ^ |   0 Yes, Thanks a lot btw!
•  » » » 4 months ago, # ^ |   0 Can you please help me find what is wrong in this submission 141865379 for problem C?
 » 16 months 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 ...
 » 16 months 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'"
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 The 8th Test case : 22 9 29 17 17Expected answer : 0
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 Can you please give 23rd test (3rd test case) if possible thanks.
•  » » » » 16 months ago, # ^ |   0 23rd Token : 23 16 9 4 14 9 4 Expected answer : 1
•  » » » » » 16 months ago, # ^ |   0 Thanks :)
 » 16 months ago, # |   0 Problem A is interesting... looks easy but not at all
•  » » 16 months ago, # ^ |   0 It's very easy. The maximum number must start with '9'. for the second most significant digit, Ideally we want '9' but it is so clear that we can NOT have 2 equal adjacent digits. so the second best option is '8'. for the third most significant digit, again the best is '9'. So the biggest number, starts with '989' but there is only one way we can get this result.
 » 16 months ago, # |   0 I don't get how pausing the second panel from left helps every time...I mean how is it guaranteed that if we pause the second panel from left.. every time the first panel will be paused showing up 9? Suppose we have n = 3. If we pause the second panel...the third will pause showing 9 and the first will subsequently pause showing 0. But the editorial says it will pause showing 9. Please help me out..and kindly explain where am I wrong?
•  » » 16 months ago, # ^ |   0 If you pause the second panel, won't the first and third panel pause at the same time? Suppose the panels showing : 888 and you paused the second one, then after 1 second it will show 989.
•  » » » 16 months ago, # ^ |   0 Ah..I made a silly mistake...by pausing adjacent panels I thought that would happen only from left to right...but thank you so much for clearing my doubt
 » 16 months ago, # |   0 Nice editorial for Problem C
 » 16 months ago, # | ← Rev. 2 →   +3 .
 » 16 months 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!
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   0 Too many thanks brother :) Got AC
•  » » » 16 months ago, # ^ |   0 Legend how did u get it
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 I just thought of some test case for which my code could get wa.
 » 16 months ago, # | ← Rev. 2 →   0 Nice and clean editorial solution code! for div 2 B. Thanks.
 » 16 months 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 !!
•  » » 16 months ago, # ^ |   0 Nevermind this stupid comment
 » 16 months ago, # |   0 REALLY GREAT CONTEST !! NOW, AFTER STRUGGLING WITH A , I HAVE SOLVE IT NICELY AND I AM BECOME PUPIL NOW.
 » 16 months ago, # |   0 Can anyone please explain problem E. And also some of the topics related to it, which might help in solving it.
•  » » 16 months 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
 » 16 months 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));
•  » » 16 months 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.
 » 16 months 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?
•  » » 16 months 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].
 » 16 months 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!
•  » » 16 months 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...
•  » » » 4 months ago, # ^ |   0 Can you please help me find what is wrong with this submission 141865777 for problem C?
 » 16 months 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 !!!!
 » 16 months ago, # |   0 103879400submission is in python language can any boby help me out, why my code break(stop unexpectedly) without giving any error for tastcases k > 1500.
 » 16 months 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?
•  » » 16 months 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$
•  » » » 16 months ago, # ^ |   +3 Oh, that makes sense, I'm wondering how did I miss thinking about the reverse part.Thank you :)
 » 16 months ago, # | ← Rev. 4 →   +7 Nice contest
 » 16 months ago, # |   0 can somebody easily explain C. Three Bags problem??
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   +3 thank you
 » 16 months 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.
•  » » 16 months 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
•  » » » 16 months ago, # ^ |   0 Very well explained , Thank You :)
 » 16 months ago, # |   0 can anybody explain what is wrong in my dp solution of div2B https://codeforces.com/contest/1467/submission/104257843
 » 16 months ago, # |   0 can anyone tell me the concept of multiplying d[i][k-j] in d problem i couldnt understand?
 » 16 months ago, # | ← Rev. 2 →   0 Problem DI didn't understand solution. But I am now.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Bye !
 » 16 months ago, # |   0 I highly doubt about Problem C solution: the summation of given data should overflow 32bit integer. Any thoughts?
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 define int long long
•  » » » 16 months ago, # ^ |   0 Ah. Thanks.
 » 16 months ago, # |   0 Does there exist an abstract guidance for coming up with such solutions as here for problem C? Or is it only a matter of pure creativity of the mind?
 » 16 months ago, # |   0 Can anyone explain problem E in a clearer way? I tried to read the editorial several times but still get lost.
 » 6 months ago, # |   0 Can anyone explain A pls?