Editorial for Hello 2024

1919A - Wallet Exchange

Author: maomao90

1919B - Plus-Minus Split

Author: maomao90

1919C - Grouping Increases

Author: maomao90

1919D - 01 Tree

Author: maomao90

1919E - Counting Prefixes

Author: maomao90

1919F1 - Wine Factory (Easy Version)

Author: maomao90

1919F2 - Wine Factory (Hard Version)

Author: maomao90

1919G - Tree LGM

Author: maomao90

1919H - Tree Diameter

Author: maomao90
Full solution: dario2994

• 12 hours ago, # ^ | Yeah definitely, I think it should be around 1700 rated. Actually, I thought to find the longest non-increasing subsequence and remove it from the array. Then I have to calculate the cost of the remaining portion of the array. That should be the answer. But I could not implement it.

  • 12 hours ago, # ^ | people are saying that they tried this and it gives WA too!

    • 11 hours ago, # ^ | Yes i implemented that solution , got WA on pretest 2

  • 12 hours ago, # ^ | agree :))

  • 12 hours ago, # ^ | IMO, C was somewhat tricky to implement but the concept isn't that hard. I think D was pretty tricky, conceptually.

    • 11 hours ago, # ^ | Can you explain me the concept of C?

      • 11 hours ago, # ^ | You just greedy it. Maintain the two sets and keep on adding them in order. You do have to be careful with how to handle each case though.

  • 12 hours ago, # ^ | ← Rev. 3 →   +10 Longest non-increasing subsequence can fail sometimes, example 4 3 2 1 8 4 2 1. If your code detects 4 3 2 2 1, penalty is 1, but optimal answer is 0 (4 3 2 1 and 8 4 2 1).

    • 12 hours ago, # ^ | Oh right!

    • 11 hours ago, # ^ | this case is invalid

      • 11 hours ago, # ^ | Can you explain why? I don't understand

        • 11 hours ago, # ^ | the elements should be <= n but we can replace 9 by 8

          • 11 hours ago, # ^ | Thanks, I did not notice that!

    • 27 minutes ago, # ^ | I was trying doing it with LIS for whole 2 hours. If only i was able to observe this faster.

  • 12 hours ago, # ^ | I firstly implemented this way using longest subsequence, but it was WA. Than I implemented greedy that is accepted.

    • 11 hours ago, # ^ | Can you pls share your approach?

      • 11 hours ago, # ^ | Accepted approach is about the same as in editorial

      • 11 hours ago, # ^ | Basically: any item should either be in s or t It doesn't matter which one so have the last item inserted in each one in 2 vars: t,s if (s < t) swap(s,t) so t is the minimum(doesn't matter just wanna have the minimum) you agree that the most optimal approach is that the current element of the array goes to the one with the minimum, if it's less than min it's the best, if it was larger than min but smaller than the other one you put it into that, still free since it's smaller otherwise put it inside the any of those u like(doesn't matter since you'll swap them if wasn't good) in any of them the cost will be increased by one

  • 11 hours ago, # ^ | I did something similar and received WA. Time to try to solve it another way.

  • 11 hours ago, # ^ | I thought of that too and implemented it WA 2 but for anykind of tc like this: 1 2 3 4 5 6 7 8 9 where the ans is n-1, it'd output n but just going on the paper for 5secs and it clicked instantly got the exact approach of editorial it was nice

  • 10 hours ago, # ^ | I tried with longest decreasing subsequence removal from the array and calculating the rest array i was sure it was right but wasn't able to implement it.

  • 9 hours ago, # ^ | i thought the same but could not implement it

  • 2 hours ago, # ^ | Very same

• 10 hours ago, # ^ | I wrote DP code for part B and it ran out of memory, then I came up with a simpler approach. Figured the same would happen for part C, so I didn't even try using DP and ran out of time trying to think of a better solution. Oops.

  • 62 minutes ago, # ^ | I was going for the same approach , but calculated the value for the output of last sample case as 5 in my mind. The simpler approach was my only guess

• 11 hours ago, # ^ | Happy New Year!

• 12 hours ago, # ^ | For the same reason the segtree solution to C and the DP solution to B weren't mentioned.

  • 12 hours ago, # ^ | wait but the segtree solution to C is literally mentioned as solution 2

    • 12 hours ago, # ^ | Oh, my bad. A non-sarcastic answer to your question: it's overkill. Also, probably not forseen or intended, because N = 2 * 10^5.

  • 10 hours ago, # ^ | DP solution to B will probably time limit. could you tell me your approach for it, maybe I got it wrong.

    • 10 hours ago, # ^ | I didn't use DP, and I don't know how the solution worked, I just saw an array named dp while hacking. 240512150

      • 10 hours ago, # ^ | oh. I got it wrong then, you can check my solution also if you want 240611932

    • 8 hours ago, # ^ | There is an O(nlogn) dp on problem B

• 12 hours ago, # ^ | Side note, calling a magic number variable in your code "magic" is hysterical.

  • 12 hours ago, # ^ | ← Rev. 2 →   +1 got that habit from tfg

• 6 hours ago, # ^ | Can you provide me with a proof for why the greedy approach they gave works in the third case where x < ai < y ? I did not understand the following part: This is because if we consider making the same choices for the remaining elements ai+1 to an in both scenarios, there will be at most one time where the former scenario will add one penalty more than the latter scenario as the former scenario has a smaller last element after inserting ai . After that happens, the back of the arrays in both scenarios will become the same and hence, the former case will never be less optimal.

• 9 hours ago, # ^ | My F1 solution uses a ReLU segment tree. I wasn't able to adjust it to solve F2 in time though. I thought the problem was really terrible at first because it's an ugly mathy solution, but after seeing that the intended solution was optimized flow instead, I like the problem much more.

• 3 hours ago, # ^ | I updated the editorial tp have slightly more details about ReLU segment tree. Hope it helps!

• 11 hours ago, # ^ | Take a look at Ticket 17195 from CF Stress for a counter example.

• 11 hours ago, # ^ | Is C been solved completely on intuition ?

• 11 hours ago, # ^ | I'm not sure what you mean by that. Why is this proof not complete? My understanding is that because it's a subsequence, and every element must be inserted into either array b or c, it is a complete proof.

  • 11 hours ago, # ^ | The question is why if you have the optimal splitting of to subsequences and , then the optimal splitting of can be obtained by back inserting of either into or into . In general, the optimal splitting for may have nothing to do with and . The proof is written such that it looks like this fact is used, but may be I am just misunderstanding something.

    • 11 hours ago, # ^ | I think the idea is that the split doesn't really matter. The only thing that matters is the final number in each array. So suppose that X and Y are the final two numbers in array A and B respectively, then regardless of any of the prior decisions for splitting the numbers, based solely on the values of X and Y we can determine whether a number should go into array A or B. You might argue that X and Y could have been chosen to be greater which might lead to a more optimal result, but the algorithm maximizes the value of X and Y in the first two cases, and in the third case the editorial lays out an argument for why it is at least just as good putting it in the other array. Does this sound right?

• 11 hours ago, # ^ | If you do let me know, the same is the reason I wasn't able to give this greedy approach a try

  • 11 hours ago, # ^ | I believe, the following was implied. Assume that you have any splitting of to subsequences , which can be extended to a splitting of the whole array with penalty . Then the splitting of constructed greedily from also can be extended to some other splitting of the whole array with the same penalty or less. This works, and in order to prove it you need to construct these from , which is more or less done in the editorial.

• 11 hours ago, # ^ | ← Rev. 4 →   +5 I agree with you. The proof is not a standard greedy proof. It only says: when the splitting of the first k elements is fixed, we can obtain the optimal (optimal under this condition, not globally optimal) solution of the splitting of the first k+1 elements. Edit: Actually there is a mistake, when the first k elements are fixed, then out of all optimal splittings of the remaining n-k elements, it's always not worse to choose the splitting (in the editorial way) of the (k+1)th element, so it's always chosen that way.

  • 10 hours ago, # ^ | Can you please elaborate on why optimal choices at each particular step eventually lead to optimal partitioning globally? Still don't understand :(

• • 11 hours ago, # ^ | Thanks, can you tell me? If in a contest I start with a wrong approach how can I get around this wrong approach like this problem?

    • 11 hours ago, # ^ | One of the options would be to stress-tests your solution (see: stress-testing on linux, stress-testing on windows).

def dnc(i, j, h):
   if min entry in [i, j) != h, then not a valid height-h tree
   if j - i == 1, return true
   get positions pos in [i, j) at height h
   split [i, j) into ranges [lo, hi) corresponding to parts between height h values # concatenation is basically unique
   for each [lo, hi), check dnc(lo, hi, h+1) and return true if all succeed 

• 11 hours ago, # ^ | I too have done same, but our solution can actually be O(n). positions just keep increasing for a value. 240578953

• 11 hours ago, # ^ | Arrays = subsequences here

• 40 minutes ago, # ^ | I tried this approach but it's not working WA on pretest 2 Couldn't figure out what the issue https://codeforces.com/contest/1919/submission/240636698

• 11 hours ago, # ^ | I have done the same, but did not have time to do it in contest...

• 10 hours ago, # ^ | If b < A(i) <= a, Though assigning A(i) to b increases the penalty by 1, it will maintain the maximum endpoints and might lead to better answer in future right?

  • 10 hours ago, # ^ | At a later time , the maximum endpoint can at max decrease answer by 1 as as soon as we replace the max endpoint then it will no longer be used (it will be replaced). Hence we have to greedily decrease the answer wherever we can... Since b<A(i)<=a then replacing a by A(i) decreases the penalty by 1,which is also the maximum decrease that the endpoint a can contribute

• 9 hours ago, # ^ | ← Rev. 2 →   0 can you explain what does this mean ? This is because if we consider making the same choices for the remaining elements ai+1 to an in both scenarios, there will be at most one time where the former scenario will add one penalty more than the latter scenario as the former scenario has a smaller last element after inserting ai . After that happens, the back of the arrays in both scenarios will become the same and hence, the former case will never be less optimal.

  • 8 hours ago, # ^ | Think of this two cases. 1) two sequences ends with 10 and 8. 2) two sequences ends with 10 and 20. And you still have some elements to put into them. The optimal answers for both cases will differ by at most 1.

• 9 hours ago, # ^ | I think people get confused why prioritize minimizing the penalty first will give the optimal result. I believe the reasoning is that, no matter which choice you made, the final elements will always contains , so the two final elements will differ at most by one element. And in both cases, the future penalties can only differ by 1. So avoiding penalty now and take penalty later is always a better option.

• 9 hours ago, # ^ | Read the explanation for Case 3. Case 1 and Case 2 are trivial but Case 3 is where greedy is truly proved.

  • 6 hours ago, # ^ | Finally figured it out, you were right

• 6 hours ago, # ^ | This runs in O(n) for D. I maintain and update nxt[i] and bef[i] to store the next and previous undeleted indices for each element. There's no logn factor of time lost in searching for indices. 240624316

• 6 hours ago, # ^ | Say you take the penalty now, and you have to take at least X more penalty in the future. Then if you avoid the penalty now, then you will have to take at most X + 1 penalty in the future. So there is no benefits to take the penalty now.

• 111 minutes ago, # ^ | Check this

• 115 minutes ago, # ^ | Sorry that I didn't notice the Bonus part.