By Vladithur, history, 2 weeks ago,

Hope you liked the problems! We apologize for the (very?) weak tests in H.

Editorials for problems will be added over time (and hints), for now, please take a look at the available hints and model solutions.

Easter eggs

Hints
Tutorial
Solution
Feedback

1987B - K-Sort

Hints
Tutorial
Solution
Feedback

1987C - Basil's Garden

Hints
Tutorial
Solution
Feedback

1987D - World is Mine

Hints
Tutorial
Solution
Feedback

1987E - Wonderful Tree!

Hints
Tutorial
Solution
Feedback
Hints
Tutorial
Solution (F2)
Feedback (F1)
Feedback (F2)

1987G1 - Spinning Round (Easy Version)

Hints
Tutorial (by errorgorn)
Solution
Feedback

1987G2 - Spinning Round (Hard Version)

Hints
Tutorial
Solution
Feedback

1987H - Fumo Temple

Please try solving the problem with a deterministic solution :)

Hints
Tutorial
Solution
Feedback
• +180

 » 2 weeks ago, # |   +69 Tutorials are broken
•  » » 2 weeks ago, # ^ |   +29 If an editorial isn't showing properly, it should be because there currently isn't one.
•  » » » 2 weeks ago, # ^ |   +26 Oh alright, thanks for the great contest btw :)
 » 2 weeks ago, # |   +2 Can someone please explain why greedy won't work for D? My solution: https://codeforces.com/contest/1987/submission/268165706
•  » » 2 weeks ago, # ^ |   0 This is the exact greedy solution I did.But not able to figure out why it fails.
•  » » » 2 weeks ago, # ^ |   0 Did you remember monotonicity? I messed up b/c of it.
•  » » 2 weeks ago, # ^ |   0 Sorting by freq won't work here as someone with higher freq that has a lower tastiness would be eaten by alice which could be prevented by bob by eating that first
•  » » 2 weeks ago, # ^ |   +1 Check for this frequency array F = {4, 4, 4, 3, 5, 5, 2}Correct answer is 5
•  » » » 2 weeks ago, # ^ |   0 Sort: 2 3 4 4 4 5 5Alice: 2Bob: 3Alice: 4Bob: 5Alice: 5Bob: rest two 4'sSo Alice will get total 3 cakes. This is what i was trying greedily but it didn't worked, can you tell me what i am doing wrong here?
•  » » » » 2 weeks ago, # ^ |   0 Given array F is Frequency array, not the array containing tastiness values of the cakes. F[i] contains number of cake with tastiness value i.Check this comment
•  » » » » » 2 weeks ago, # ^ |   0 Let the array you mentioned is tastiness array, then is my approach correct?Or let tastiness = {4,3,2,5,6,8,3,4} then after sorting:2 3 3 4 4 5 6 8A/c to my approach:Alice: 2 Bob: 5 Alice: 3 Bob: 6 Alice: 4 Bob: 8Now Alice can't choose any so total she will choose 3 cakes.Is this a correct approach, Bob will choose the cake whose frequency is as minimum as possible and greater than Alice's last chosen cake.
•  » » » » » » 2 weeks ago, # ^ |   +1 This approach wouldn't work always.Check for this = {1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7}According to your approach, Bob will start with 7 but optimal is start with 4 and complete it then take 7.
•  » » » » » » » 2 weeks ago, # ^ |   0 Got it, thanks!
•  » » » » » » » 2 weeks ago, # ^ |   0 My approach is as follows:Alice 1 Bob 4 Alice 2 Bob 4 Alice 3 Bob 4 Alice 5 Bob 7 Alice 6 Bob 7 But I get wrong answer on test 2. 268201241 Can you help, please?
•  » » 13 days ago, # ^ |   0 Please simulate the last test case to know why greedy won't work.
 » 2 weeks ago, # | ← Rev. 2 →   +49 Problem G1 coincides with QOJ 3797 Wireless Communication Network.
•  » » 2 weeks ago, # ^ |   +31 Seems like G1 unfortunately does :( The subtask was added later to help balance the problemset and we weren't aware of such a coincidence.
 » 2 weeks ago, # |   0 Problem D. World is Mine ***** 2 pointer approach -> sorting the array -> (i)one pointer of alice is on left -> (j)bob's pointer is on right . HashSet -> cakes have been eaten by the alice -> i encounters a cake at a[i] -> if the a[i] is already present in the set -> not present -> cake is added in set -> j encounters a cake at a[j] . didn't work can anyone pls tell me why.
 » 2 weeks ago, # |   +33 I have a $O\left(n \log n\right)$ solution for D. https://codeforces.com/contest/1987/submission/268177088
•  » » 2 weeks ago, # ^ |   +1 can you please explain?
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   +1 ok! Obviously, we need to iterate through all the elements in smallest-to-largest order to simulate Alice's choices, and I'm using a std::map to keep track of how many of each number there are for subsequent calculations. First, I'll try to have Bob try to stop Alice from selecting the current element every time, and for convenience we'll write the number of times the current number occurs as $c$. This requires that Bob has been unable to stop Alice at least $c$ times before, so we'll maintain a variable ("hv" in the code) representing the number of times Bob has been unable to stop Alice. But the above is clearly wrong. We need to reverse the operation. Specifically, if we are now certain that we cannot stop Alice, we replace this operation with the previous successful stopping operation, the most consumed one, if that is preferable. In the code, I use a std::multiset to keep track of successful blocking operations.
•  » » » 2 weeks ago, # ^ |   +6 I wrote a version with comments, which should be easier to understand https://codeforces.com/contest/1987/submission/268356662 I understand this as there might be a tastiness appears later, that costs less "skip points" than the skip before, so you record all the skip happen in the previous, and keeps finding for better solution which costs less rounds for b that happens later
 » 2 weeks ago, # |   +73 nice problem h guys, really appreciate your testing
•  » » 2 weeks ago, # ^ |   +2 yes, it seems that they just generated 300+ random tests and thought "hmmm, maybe on some test the square will get a time limit")))
•  » » 2 weeks ago, # ^ |   +4 268226747It seems like this solution uses no more than $50$ queries on the current data. Can anyone construct a counter-test?
•  » » » 2 weeks ago, # ^ |   +52 Sure.
•  » » » » 2 weeks ago, # ^ |   +6 Cool. Do you have any estimate of how many queries are used for the test you constructed (as a function of $N$)?
•  » » » » » 2 weeks ago, # ^ |   +11 I guess $\mathcal{O}(\sqrt{N})$? The idea is to have a square of $1$s in the corner (and also the hidden cell there). So almost wherever you ask, you see something around $x+y+(\sqrt{N})^2$, so it only tells you that the hidden cell is not in this area (so you discard around $N$ cells, but we can show better). What gives you more information is asking about a rectangle that won't contain all $1$s. My initial idea was that if we get an answer larger than $N$, then we discard the area around the queried cell (hopefully discarding around $N$ cells), and if we get an answer smaller than $N$, then we restrict ourselves to a square (hopefully decreasing the number of cells geometrically). But yeah, it seems that it's even better. Also Idk what about $M$ much larger than $N$, probably you can show something too. I was mostly worried about TL and spent most of the time thinking how to optimize it, but it just passed, so...
•  » » » » » » 2 weeks ago, # ^ |   +6 Oh, actually (on a square grid) response greater than $N$ tells you that you can discard around $N \log (N)$ cells (a shape enclosed by hyperbolas).
 » 2 weeks ago, # | ← Rev. 2 →   +64 E can be solved in $O(N\log N)$ time by replacing the vectors in my solution 268156681 with mergeable priority queues.(or even $O(N)$ if we compress equal keys in the priority queue and merge the priority queues in time proportional to the smaller subtree depth)
•  » » 13 days ago, # ^ |   +5 I think my submission for E works in O(NlogN) using small-to-large merging technique. 268419277Let diff[node] be difference between a[node] and (summation of a[child]). Each subtree maintains a set of nodes ordered by depth such that diff[node] < 0. On DFS, if diff[currentNode] > 0, take first node in the set, update result and diff[firstNode]. To combine the sets of each child to parent, small-to-large merging is used.
•  » » » 12 days ago, # ^ | ← Rev. 6 →   +5 Actually I think it is $O(n \log^2 n)$. One is for dsu on tree and the other is for std::set.By using mergeable priority queues, the problem could be solved in $O(n \log n)$.
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 dsu is not used. For each node in DFS, either first element in set gets erased or diff[currentNode] becomes zero. As the number of elements in the set for a subtree is atmost n, this takes O(nlogn) time. Merging subtree for all nodes takes O(nlogn) time separately. I think this analysis is similar to amortized time complexity analysis.
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   +5 I'm sorry for not understanding what you said and I believe it's still $O(n \log^2 n)$. We can assume that the tree is already a wonderful tree, so we don't need to make any modifications to it. So according to your code, small-to-large merging is $O(\log n)$, and inserting them into the set is $O(\log n)$. What's more, we won't delete or modify the elements. So I think it's $O(n \log^2 n)$. I may not have understood your code and words. If there are any issues, please point them out.
 » 2 weeks ago, # |   +44 Personally, I like this round very much, not because I get positive delta, but because the problems are really cool. D & E are easy problems but they require you to seek for the solution (that is, I don't get the solution as soon as I read the problem statement). I think that reminds me how to set problems like this.UPD: It seems that the straight greedy solution to E works well. However I was writing minkowski sum, which seems of more correctness to me.The model solution for F seems fascinating (thus I'm looking forward to seeing the editorial soon) because my solution works in the same time complexity but is much more complex than yours (as a result, I've made many, many mistakes in some of the details). And I got WA on 3 on G1 during contest time. For now, I've understood why my solution to G1 is wrong through several small hacks. Sorry for being so weak, but I will try to spend more time solving G2 and H.
 » 2 weeks ago, # |   +73 I wonder whether using min cost max flow was expected to pass in E (268173238)
 » 2 weeks ago, # |   +10 D can also be solved NlogN by using priority queues
•  » » 2 weeks ago, # ^ |   0 How?
•  » » » 2 weeks ago, # ^ |   0 A will take the smallest value possible, B can make changes in the runtime. i.e go back in time and take the best ones using priority queues. Link to AC solutionhttps://codeforces.com/contest/1987/submission/268370561
•  » » » » 9 days ago, # ^ |   0 Very good solution dude, studied is completely!!
 » 2 weeks ago, # |   +1 Waooo...
 » 2 weeks ago, # | ← Rev. 2 →   0 Can anyone please help me understand why my idea for problem D is not working?Here is what I am trying to do.Alice always takes smallest number. Bob takes any number bigger than what alice took which also has the smallest frequency and alice won't be able to reach it.
•  » » 2 weeks ago, # ^ |   +7 Bob sometimes may want to eat a less tasty cake with a higher frequency over a cake that has lower frequency but high tastiness.
•  » » » 2 weeks ago, # ^ |   0 Could you give example?
•  » » » » 2 weeks ago, # ^ | ← Rev. 3 →   +5 Let there be cakes with tastiness 1, 2, 2, 3, 3, 4, 4, 4, 5 Bob will want to eat the cakes with tastiness 3 first.
•  » » » » » 2 weeks ago, # ^ |   0 Thank you so much.
•  » » » 2 weeks ago, # ^ |   0 But how does Bob decide which particular cake to eat?
 » 2 weeks ago, # |   0 E. Tell me if my approach is correct or not. First, you calculate sum of values of direct children, just below, for every node, lets call it sum[i] for node i. Next we do a dfs traversal. For leaf nodes we do not have to do anything. Then for others nodes, if val[i]>sum[i], then we need to perform some operations. We need to add exactly val[i]-sum[i] to one of the child node, but in doing so you are changing the value of child node, which can result in val[child]>sum[child], and if this happens, you just need to add val[i]-sum[i] again to the child's children node, and so on.If I am going in the right direction, do tell me. If not, please point out the mistake.
•  » » 2 weeks ago, # ^ |   0 "We need to add exactly val[i]-sum[i] to one of the child node": this is wrongExample tree:  41 12 2 In this example you add 1 to each node in the second row, total cost 2. If you add 2 to a node, the cost will be 3
•  » » » 13 days ago, # ^ |   0 268472191can you please help me why am i getting WA, my approach- first calculated the min distance from the node to a leaf node in height vector and in diff vector stored the value a[node]-(sum of a[child])then for each node , if diff>0 this means that child nodes needs operations to be done,so i check if there is any child node such that its value can be increased without further nodes being affected then for the remaining difference i just multiply the distance stored in height vector Please point out the mistake
•  » » » » 13 days ago, # ^ |   0  9 1 2 4 3 4 10 => 9 4 5 4 5 4 10 
•  » » » » » 13 days ago, # ^ |   0 oh okay thankyou so much!!
 » 2 weeks ago, # |   0 I am curious on why a Greedy solution of removing the highest pair for problem F doesn't work. Couldn't find the counterexample during the contest. Example: https://codeforces.com/contest/1987/submission/268216353
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +46 181 1 3 4 1 2 2 1 taking the last pair gives 3 but there is optimal order to erase the whole sequence
 » 2 weeks ago, # |   0 Why iterating over the maximum possible cake Bob could remove and choosing the others greedely yields an incorrect answer? serious question
 » 2 weeks ago, # |   +2 dp-forces
 » 2 weeks ago, # |   +5 Could somebody explain me, how to solve D using DP, please?
•  » » 2 weeks ago, # ^ |   +7 I have used 2D DP. First state is for distinct positions and 2nd state is for Bob's time to eat all cakes of a specific tastiness. Bob will try to eat cakes in ascending order of their tastiness. He should eat all the cakes of a type so that Alice can't eat that type of cake. Bob will have 2 options. Either he will eat all copies of a cake if he has enough time before Alice reaches to that type. He can skip the cake and will move to the next one. You can see my code for better understanding: https://codeforces.com/contest/1987/submission/268196842
•  » » 2 weeks ago, # ^ |   +5 Firstly, it could be seen that the optimal strategy for Alice is to eat cakes in ascending orders of tastiness from the smallest to largest one. So if Bob wants to minimize her overall number of cakes, he must try to eat up all cakes of some particular tastiness in order to avoid Alice eats that type of cakes (I used the term type here instead of tastiness from now on for convenience). So let's get the frequency of each type of cakes and sort those in ascending order of tastiness. Let $dp_{i,j}$ be the minimum number of cakes that Bob will eat if we consider the first $i$ types and Bob has been eaten $j$ types of cake. The transition is pretty simple, but we need to ensure that the number of cakes that Bob eats needs to be smaller or equal to Alice does at any time of the transition. The answer will be the total number of types minus the maximum number types that Bob could eat which can be checked by the valid transitions we made.Submission: 268186295
•  » » 2 weeks ago, # ^ |   0 Have a look at my explanation in another thread.
 » 2 weeks ago, # | ← Rev. 2 →   +10 Video Editorials
 » 2 weeks ago, # |   +13 The problem were very interesting thank you
 » 2 weeks ago, # |   +14 C was also doable regardless of direction.The formula for the time taken, assuming the $i$th column is the bottleneck is: $h_i + i$ (proof is simple)So we just try out all $i$ and get the one that gives the max $h_i + i$, that would be the real bottleneck.https://codeforces.com/contest/1987/submission/268234160
•  » » 2 weeks ago, # ^ |   0 Can you please help me prove it.
•  » » » 2 weeks ago, # ^ |   +18 I should first clarify what I mean by bottleneck. Check out this example for initial heights 1 2 3 5 4:  # ## ### #### ##### 12354 The fourth flower is the "bottleneck" because it is taller than all the flowers behind it hence nothing from behind will stop it from going down every second (this is only the initial idea, we later explain how index, aka width, comes into play).Hence, the fourth flower reaches height 1 after 4 seconds.Notice how the previous flower heights will be dragged down along with the fourth column (we ignore after 4): 1235- 1234- 1233- 1232- 1221- 1210- 1100- 1000- 0000- There's this pattern where when $h[4]$ ($1$ indexed) is first $0$, then $h[3]$ is $1$, and so on...Hence after $h[4]$ is $0$ it will take $(4 - 1)$ seconds for the rest to become $0$.When we're $0$ indexed, the index of the fourth flower is $3$ anyway. Hence the $h_i + i$ formula.Also in case you're wondering, it doesn't matter if the sequence behind is monotonically increasing (the explanation is a bit long but think of the other extreme where it's actually monotonically decreasing before the bottleneck).Now it's perfectly possible something after the fourth column was the real bottleneck, especially since using this formula we got $h_i + i$, so there's an aspect of width to it too, not just height, hence why we take the max over the whole array.
•  » » » » 2 weeks ago, # ^ |   +3 Decent explanation!
 » 2 weeks ago, # |   0 Can anyone please explain to me why the second loop is used in problem D in the tutorial? Here's the code: ---> int n = a.size(); vector dp(n + 1, inf); dp[0] = 0; for (int i = 1; i <= n; i++) { vector ndp = dp; for (int k = 1; k <= n; k++) { int nv = dp[k - 1] + a[i - 1]; if (nv <= i - k) { ndp[k] = min(ndp[k], nv); } } dp = ndp; }It would be very helpful if someone could explain it. Thanks in advance! ^-^
 » 2 weeks ago, # |   +18 Is the example array in problem F’s tutorial wrong? The array is [1,2,5,4,5,7,1,8] ,how can we remove a[7] and a[8] when a[7] != 7?
•  » » 2 weeks ago, # ^ |   0 Thanks, fixed.
 » 2 weeks ago, # | ← Rev. 2 →   0 Can someone please review my profile and guide me ? I have tried different problems of different ranges(900-1300 more frequently ), but still I am unable to think of even the easiest problems for eg I was unable to think in correct direction for C (which was probably of the range 1100-1200) and took a lot of time for B and came up with a difficult and unnecessary approach compared to other solutions for problem B. Can someone please guide me on how can I improve from my current situation? it would me a lot of help for me Thankyou
•  » » 2 weeks ago, # ^ |   +1 I do not personally think C was that easy though it had around 8k submissions, B was easy once you see whats actually happening, i would suggest you to solve codeforces ladders on your own as well as give virtual contest regularly, it would definitely help you grow!
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Thankyou Sir, and can you tell me more about Code Forces ladders ?
•  » » » » 2 weeks ago, # ^ |   0 Google them they are a set of 100 questions for each difficulty ranging from A to F.
 » 2 weeks ago, # |   0 In problem C, Ive seen that most have used dp to solve it. Ive spent the past 5 hours to prove that the approach is correct. I could only prove the following 1987C - Сад Бейзила 1. if A[i] > dp[i+1]+1 => dp[i] = A[i]I was not able to prove the other parts. And Im also wondering how the guys had gotten the idea and were also able to prove this confidently in a decently less quantity of time.Could someone please help me...
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +2 We let dp[i] be the seconds for arr[i] to reach 0. As you have proven, if arr[i] > dp[i+1] or i = n, then dp[i] = arr[i].So now let's assume arr[i] <= dp[i+1]. We need to prove that this means dp[i] = dp[i+1] + 1.First off, it's easy to see that dp[i+1] + 1 is a lower bound for dp[i]. In order for arr[i] to reach 0, arr[i+1] needs to have reached 0 too, and two consecutive elements of arr can never both decrease and reach the same value at the same second. Therefore dp[i] >= dp[i+1] + 1.Now let's establish that dp[i+1] + 1 is an upperbound for dp[i]. Suppose that it is not, and that dp[i] = dp[i+1] + c, for a constant c > 1. Then, after dp[i+1] seconds, arr[i+1] = 0 and arr[i] = c. That implies that arr[i] and arr[i+1] never got equalized, therefore arr[i] > arr[i+1] should hold. But if arr[i] can keep getting decreased while never getting equalized with arr[i+1], then dp[i] = arr[i] -> dp[i] <= dp[i+1] -> dp[i] < dp[i+1] + 1, and that violates the lowerbound.Therefore the upperbound is dp[i+1] + 1.Lowerbound is equal to upperbound, therefore if arr[i] <= dp[i+1], dp[i] = dp[i+1] + 1.
 » 2 weeks ago, # |   -9 In the problem F I just traversed from the back and whenever I find the element satisfying the condition just delete it and next element and then again traverse from the back again. doing this until we can. Most of the test cases are passing. Can someone please help. My solution 268194520
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Try this 1101 1 3 4 1 2 9 9 2 7 The answer is 4:1 1 3 4 1 2 9 9 2 71 1 1 2 9 9 2 71 2 9 9 2 71 9 2 72 7
•  » » » 2 weeks ago, # ^ |   0 thank you so much.
 » 2 weeks ago, # |   +5 so? everybody can provide solution pieces and make it a full solution?
 » 2 weeks ago, # |   0 Can someone please review my profile and guide me ? Thank you :-)
 » 2 weeks ago, # | ← Rev. 2 →   +25 The sample input in problem F is kind of weak so that even I mistakenly typed a <= as a >=, it would pass the sample.I consistently received Wa On Pretest 2 until I realized what a stupid mistake I had made.
•  » » 2 weeks ago, # ^ |   +11 me too bruh btw the sample is too weak I think, since any kinda algorithm can pass so I got a lot WAs on pretest 2 or 3.
 » 2 weeks ago, # | ← Rev. 2 →   +13 Upsolved G1 with dp:Since we know that the paths leading up to the root don't collide, we can keep track of 3 dps for each section, where segment i represents all numbers from l_i+1 to r_i-1. We can keep track of longest single path up to p_i, longest sum of lengths of two paths such that the root of the left path has higher p vale, and same thing but with the right path. Then, we can calculate answer by going through all the root positions. Update: it also worked for G2 with some (annoying) changes!
 » 2 weeks ago, # |   +11 Too much DP.
 » 2 weeks ago, # |   -8 How can C be solved if height can also be 0? Like test 9 0 9 0 and answer 9. I was wondering that the whole time and then realized the constrains :(
•  » » 2 weeks ago, # ^ |   0 it can be seen that ranges separated by 0 do not affect each others
 » 2 weeks ago, # |   +30 I spent 30 more minutes just to realize $O(n^3)$ can pass F2 lmao...
 » 2 weeks ago, # |   0 not my best performance but atleast i got the references
 » 2 weeks ago, # |   +1 Cheating has increased so much . At this point solutions should be leaked intentionally which fails on main test and passes the pretests . This would be good way to catch cheaters which changes the code using AI to avoid plag checks .
 » 2 weeks ago, # |   +10 OMG, a CrossCode reference! That game was amazing, not nearly well enough known considering how good it is.
 » 2 weeks ago, # |   0 I'm very much curious to learn that for problem D, is there any other approach than dp?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0
 » 2 weeks ago, # | ← Rev. 2 →   0 For those who were not able to understand the DP solution of D. 268157606 solution int n; cin>>n; vector v(n); mapmp; for(auto &it : v)cin>>it, mp[it]++; vectorfreq; for(auto &it : mp)freq.pb(it.ss); int bal = 0; multisetst; for(auto &f : freq) { if(f <= bal) { st.insert(f); bal -= f; continue; } bal++; if(st.size() == 0)continue; auto mxp = st.rbegin(); int mx = *mxp; if(f < mx) { bal += (mx - f); st.erase(st.find(mx)); st.insert(f); } } int bobEats = freq.size() - st.size(); cout<
•  » » 2 weeks ago, # ^ |   0 can you explain the idea also?
•  » » » 2 weeks ago, # ^ |   0 Let Bob greedily eat most types of cakes so that none of those types of cake are left for alice when she reaches there.By type I mean cakes with unique tastiness values.
•  » » 2 weeks ago, # ^ |   0 Vladithur add this approach for D as well if possible.
 » 2 weeks ago, # |   0 good blog
 » 2 weeks ago, # |   0 .
 » 2 weeks ago, # |   0 Can anyone explain me the dp in problem D how is it working and I am not able to see dp logic generally in problems how can I become better at it ?
 » 2 weeks ago, # | ← Rev. 2 →   0 someone please explain why my code for problem E is giving wrong answer on testcase 2 below is my submission https://codeforces.com/contest/1987/submission/268323462
 » 2 weeks ago, # | ← Rev. 2 →   0 Solution of problem D with priority_queue:
 » 2 weeks ago, # | ← Rev. 2 →   0 Can someone please help me to understand whats wrong in my B solution?1 -> put all differences in a ascending order heap2 -> for each peek, i know i can pick a maximum k equals to heap size, and i can pick it peek times3 -> sum coins and sum shifts from previous peek to next elements4 -> Ex:4 8 16I know i can choose K = 3, 4 times I'll spend (3 * 4 ) + 4 coins = 16 coins Shift 4 for all next -> 4 12 continueWhats wrong, pls? X-X Fails here: wrong answer 11th numbers differ — expected: '2020469122', found: '1207241465'
 » 2 weeks ago, # |   0 I came up with a solution to G1 during the contest, but it failed on pretest #3. The idea is to build the cartesian tree first, than enumerate the root of the diameter, which seperates it into two parts.When dealing with root u, first consider if the two parts come from different subtrees, which can be done by calculating the maximum depth in the subtree. It can be proven that going up from v to u on the cartesian tree is the longest way in all possible trees according to the constraints.Second, consider if the two parts come from the same subtree (for example, the left one). First we set v to the left son of u and keep going to its right son, and pull out the chain (the points on the chain are the only points whose $r_v$ is u). The diameter we are considering is made by fliping one choice from $l_v$ to $r_v$. By enumerating the point that is flipped, we can find the longest route. Since one point will be enumerated only twice, the complexity is $O(n)$.(Maybe it is hard to understand and you may have to check the code)I wonder whether the algorithm itself is right and how to hack it.Submission
•  » » 2 weeks ago, # ^ |   +10 1 6 5 2 3 1 4 6 ?????? I think the answer should be $5$.
•  » » » 12 days ago, # ^ |   0 thx
 » 2 weeks ago, # | ← Rev. 2 →   0 Can someone recommend similar problem to D but easier, like 1400, 1500
 » 2 weeks ago, # |   0 Thank you for the amazing contest
 » 2 weeks ago, # | ← Rev. 2 →   +10 Problem F is so beautiful, I love it. Also how did I miss the Celeste reference in problem H lol
 » 2 weeks ago, # | ← Rev. 2 →   0 void solve() { ll n ; cin>>n ; vll v(n); for(int i=0;i> x; v[x-1]++; } vll a; for(int i=0;i> dp(m+1,vector(m+1,-1)); dp[0][0]=0; for(int i=1;i0;j--){ dp[i][j]=dp[i-1][j-1]; if(j>=a[i]){ dp[i][j]=max(dp[i-1][j-a[i]]+1,dp[i-1][j-1]); } }}// for(int i=0;i
 » 2 weeks ago, # |   +5 More tasks like D??Thanks
 » 2 weeks ago, # |   0 Can someone tell me why my code is not working? I am getting a runtime error in test case 9 https://codeforces.com/contest/1987/submission/268383994
 » 2 weeks ago, # | ← Rev. 4 →   +20 Solution for G1 (440ms & 132MB):Define$f(\text{int l},\,\text{int r},\,\text{bool lemax},\,\text{bool remax}) = (\text{maximum diameter},\,\text{maximum depth},\,\text{maximum sum of depths of two vertices where one is connected to lemax and one to remax})$ if we only consider indices $[l,\,r]$ and the possible two extra vertices. If $\text{lemax} = \text{true}$ we also have a vertex to the left that we can connect to, similarly for $\texttt{remax}$, there's a vertex to the right if it's true. Also note that there's no restriction for the vertices to form a connected graph, because only the maximum must be connected to itself, for all the rest we can reconnect it if we had connected it to itself previously, thus being unconnected wouldn't be a better solution for any of our outputs.One can easily calculate $f(l,\,r,\,\text{lemax},\,\text{remax})$ from $f(l,\,m-1,\,\text{lemax},\,1)$ and $f(m+1,\,r,\,1,\,\text{remax})$ where m is the index of the maximum element in $[l,\,r]$. I won't bore you with explanations and different cases that may occur, you can read more in my G1 submission.Solution for G2 (420ms and 132MB):Do the same but instead of maximum depth, we output two maximum depths, one for vertices connected to the left and one to the right. Again, the detailed explanations are nothing crazy, but here's my G2 submission.Overall I loved E and F and liked the rest. They'll be good problems for practicing as well. Thanks very much. Also, this might interest you Vladithur
•  » » 2 weeks ago, # ^ |   0 In G2 the different cases that may occur will handle forced edges.
•  » » 13 days ago, # ^ | ← Rev. 2 →   +14 wanted to point out another similiar dp like recurrence approach.For G1, my initial idea was to categorize shapes into 3 broad classes : path (self explanatory), hill (2 paths from opposite sides merging at the highest element), skewed_hills (2 paths from same side merging at highest element) You naturally get left and right skewed hills. This is nearly enough for writing the dp recurrences for G1, except you notice that sometimes a technically invalid skewed_hill can later on be made valid. (for example consider a case like 5 2 1 3 4)I had to maintain 2 extra variables called skew_right_bad and skew_left_bad respectively. You can check my code for exact details of the recurrences https://codeforces.com/contest/1987/submission/268296892A similiar approach can be made to work for G2 but it is much cleaner to categorize things by actual properties instead of their shapes. I needed the following properties : one_path[dir] = largest path which can be extended in direction dir two_path[dir1][dir2][max] = largest set of 2 paths where the first path can be extended in direction dir1, second path in direction dir2, and the maximum element is path numbered max.
 » 13 days ago, # |   +10 Epic
 » 13 days ago, # |   0 For problem E I traverse each node and return a list of information in each nodehttps://codeforces.com/contest/1987/submission/268349130
 » 13 days ago, # |   0 Really enjoyed solving problem E! It took me a long time to come up with the idea but eventually I figured out I could treat each node as either a "source" or a "sink". Then we must send the difference between parents and their children down to sink nodes, in BFS order to minimize cost. Then it becomes clear that the cost to use a sink node is dist * difference, and we can use the sink node until it is equal to the sum of its children, or infinitely if it is a root. Codeint par[5001] = {}; int dep[5001] = {}; void dfs(int pos, vector>& adj, vector& csum, int last, vector& v, int d, vector& order) { order.push_back(pos); par[pos] = last; dep[pos] = d; for (auto i : adj[pos]) if (i!=last) { csum[pos] += v[i]; dfs(i, adj, csum, pos, v, d+1, order); } } void solve(){ int n; cin >> n; vector v(n, 0); for (int i = 0; i < n; i++) cin >> v[i]; for (int i = 0; i < n; i++) par[i] = dep[i] = n; vector> adj(n, vector()); for (int i = 1; i < n; i++) { int b; cin >> b; b--; adj[i].push_back(b); adj[b].push_back(i); } vector order; int ans = 0; vector csum(n, 0); dfs(0, adj, csum, n, v, 0, order); reverse(order.begin(),order.end()); for (int k = 0; k < n; k++) { int i = order[k]; queue q; int dif = v[i] - csum[i]; if (v[i] > csum[i]) for (auto j : adj[i]) if (j != par[i]) q.push(j); while (!q.empty() && dif > 0) { auto temp = q.front(); q.pop(); int can = csum[temp] - v[temp]; if (temp && adj[temp].size() == 1) { ans += dif * (dep[temp]-dep[i]); dif = 0; } else if (can > 0) { int use = min(dif, can); dif -= use; ans += use * (dep[temp]-dep[i]); v[temp] += use; } for (auto j : adj[temp]) if(j != par[temp]) q.push(j); } } cout << ans << endl; } 
 » 13 days ago, # |   0 Can someone explain the formal proof to the claim in Hint 3 of problem E?it is not less optimal to apply the operation on (v1,w2) and (v2,w1).or why the bottom up approach works in the small-to-large solution?
 » 13 days ago, # |   +15 So how soon can we see the tutorial of problem G & H
 » 13 days ago, # |   +10 To the problem F, can anyone tell me Why is the dp transition written that way? for this sentence: op =max(dp[l+1][m−1],dp[m+1][r]−(m−l+1)/2) I have some difficulties in understanding the content after the transition of dp
•  » » 13 days ago, # ^ |   +10 I think it's typo in editorial. Read the solution codein the code:$op = max((l + 1 - a[l]) / 2, dp[m + 1][r] - (m - l + 1) / 2);$
•  » » » 13 days ago, # ^ |   +3 Thanks for noticing, fixed
•  » » » 12 days ago, # ^ |   0 thank you and i finally understand!
 » 13 days ago, # |   0 Can somebody tell me whats wrong with this solution ? 268517922
 » 12 days ago, # |   0 F problem is really nice! Thanks for the round.
 » 12 days ago, # |   0 Could someone please explain the dp transitions for F1 if the dp state is dp[l][r][k] -> max operations on interval [l,r] if exactly k operations are performed to the left of l? I was thinking we could iterate m from l+1 to r such that we try to pair a_l and a_m, given that a_l == l — k and dp[l+1][m-1][k] == (m-1) — (l+1) + 1. If a_l != l-k, then dp[l][r][k] = dp[l+1][r][k]. If a_l == l-k and dp[l+1][m-1][k] == (m-1) — (l+1) + 1, then dp[l][r][k] = max(dp[l][r][k], 1 + ((m-1)-(l+1)+1)/2 + dp[m+1][r][k1], where I am not sure what the optimal k1 is because we can perform the operations on [l,m] and [m+1,r], in different orders. Thus I think that I would have to iterate over the possible values of k1, which would lead to an O(n^5) solution. TLDR: What are the dp transitions dp[l][r][k] for F1?[problem:F1]
 » 12 days ago, # |   +10 Can anyone explain the O(n) solution for problem E "Wonderful Tree"? I don't get it. Please help.
 » 12 days ago, # | ← Rev. 3 →   0 A simple greedy solution for problem D (with comments for better understanding)Don't know why so many people did DP on D.
 » 12 days ago, # |   0 can someone explain to me why you have to iterate from n to 1 in problem D? Thanks
 » 12 days ago, # | ← Rev. 5 →   0 5581485311 581485311 581485311 147717016 581485311can somebody explain why the answer for this testcase for problem C is 581485315 and not 581485313
 » 12 days ago, # | ← Rev. 3 →   +10 .
 » 11 days ago, # |   0 What's the intuition for problem F? Even if I understand the editorial, I can't seem to grasp how one would come up with this...
 » 11 days ago, # |   0 for problem F, why it is wrong that, i always chioce to delete the last legal position？this greedy idea seems like right.
•  » » 11 days ago, # ^ |   0 1 8 1 8 3 4 1 2 8 8 Answer should be 4. Greedy would give 3.
•  » » » 9 days ago, # ^ |   0 thanks
 » 10 days ago, # | ← Rev. 2 →   +10 In case those who are not able to understand the dp of the tutorial of problem D. after getting the freq array of the elements of the main array you just need to maximise the number of indices that Bob can take and then subtract it from the freq array size. Below is the simple understandable recursion + memoization code — const int MAXN = 5001; vector> dp; int helper(vector& v, int ind, int steps){ if(ind >= v.size()){ return 0; } if(dp[ind][steps] != -1){ return dp[ind][steps]; } int curr = 0; if(steps >= v[ind]){ curr = 1 + helper(v, ind+1, steps-v[ind]); } curr = max(curr, helper(v, ind+1, steps+1)); return dp[ind][steps] = curr; } void solve() { int n; cin >> n; vector a(n); map mp; for(int i = 0; i < n; i++){ cin >> a[i]; mp[a[i]]++; } dp.assign(mp.size(), vector(MAXN, -1)); vector v; for(auto x : mp){ v.push_back(x.second); } int ans = helper(v, 0, 0); cout << v.size() - ans << "\n"; } Thanks.
 » 8 days ago, # |   0 [problem:C] I think the approach to solving problem C is little difficult for me to figure out. I thought about it for a very long time!!!
 » 8 days ago, # |   0 lefist heap solution for E in O(nlogn) complexity:268358732
 » 7 days ago, # |   0 Anyone can please help with 1987E - Wonderful Tree! 269388889?For every node I try to go into its child, and its subchild and so on, I keep its height from the source node and the potential (val[node] — val[childs]) [Similar to Shayan's Editorial]. I then greedily increase the value if its potential is positive or it is a leaf node.
 » 7 days ago, # |   0 Can anyone debug my solution for F1 please? Spoiler#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,fma") #include using namespace std; const int MAX = 102; const int oo = MAX; int f[MAX][MAX], g[MAX], a[MAX], n; void solve() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (i > j) f[i][j] = 0; else f[i][j] = oo; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n - i + 1; j++) { int l = j; int r = j + i - 1; if (abs(l - a[l]) % 2 == 1) continue; if (l < a[l]) continue; for (int k = l; k <= r; k += 2) { if (f[l + 1][k - 1] <= (l - a[l]) / 2) f[l][r] = min(f[l][r], max((l - a[l]) / 2, f[k + 1][r] - (k - l + 1) / 2)); } } } for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) cout << f[i][j] << " "; cout << "\n"; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { if (f[j][i] <= g[j - 1]) g[i] = max(g[i], g[j - 1] + (i - j + 1) / 2); } } cout << g[n] << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) solve(); } `
•  » » 7 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Nvm, I got the bug.
 » 3 days ago, # |   0 Why did nothing happen to the cheater of the EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) contest and their rating? MikeMirzayanov & Vladithur
 » 44 hours ago, # |   0 A key thing to do in E is to work the tree from bottom to root level by level I missed that when I read the tutorial so in case some one else missed it too this test case will help you understand why910 2 7 5 1 1 1 3 21 1 3 3 2 4 4 5if you start from the root (1) and try to fix it using node (5) instead of (6) you will end up with answer equal to 6 instead of 5 because (3) now have to go two nodes down to fix itself instead of one to (5) draw it and it will become clear I got WA on test 9 because of this
 » 12 hours ago, # | ← Rev. 3 →   +8 I need some help.My approach for problem F: instead of a $dp[l][r][k]$ (range $l$ to $r$ with exactly $k$ elements removed before $l$), I tried $dp[i][j][k]$ ( $i$ current position, $j$ elements removed and $k$ unmatched positions to delete) . Basically, I use the claim: let $jumps:=i-a[i]$, if $jumps <= j$ and $jumps\mod 2==0$ and jumps are non-ngative we can like open a bracket since we can perform the previuos operations in such order to do this valid operation".
•  » » 5 hours ago, # ^ |   0 Take a look at Ticket 17460 from CF Stress for a counter example.