Codeforces Round 924 Editorial

Codeforces Round 924 Editorial

• 27 hours ago, # ^ | ← Rev. 4 →   +18 Because the solution with binary search is hard to prove. This works, but we didn't expect contestants to prove it during contest. I agree, maybe removing would have been better. Anyway, the difficulty of problems D and E as they are seems adequate for their position.

  • 27 hours ago, # ^ | is the link you provided correct? is seems to be a diffrent problem. is the problem simular to problem d?

    • 26 hours ago, # ^ | Yes, the formula used in that problem is the same up to rescaling.

      • 26 hours ago, # ^ | thank you.

  • 26 hours ago, # ^ | I think nobody proved, frankly it was incredibly intuitive for me.

    • 25 hours ago, # ^ | not to me sadly :( can you explain how you thought of it? I guessed it was convex of course, but i couldn't feel that with my heart.

      • 25 hours ago, # ^ | ← Rev. 2 →   0 Me too, but then I wrote linear search and I looked every k, it seemed it was convex. I tried and it worked. Also, you can see my first linear search submission which gets TLE.

        • 25 hours ago, # ^ | did u solve as indicated in tutorial and got tle?

    • 25 hours ago, # ^ | Bruh ur rating chart is kinda unique tho :)

      • 25 hours ago, # ^ | Thanks, lol :D

  • 25 hours ago, # ^ | Isn't that precisely the issue? When you set a problem with a correct solution that is easy to come up with and hard to prove you are rewarding the people who implemented without proving it. Which probably shouldn't be the case?

    • 24 hours ago, # ^ | ← Rev. 2 →   +2 Is it even possible to prevent solving problem without proving? besides, there is time penalty for WA verdict. especially in cp, almost no one tries to prove the logic. I think it's the contestant's job to keep the balance between intuition(for time) and proof(to reduce risk of WA, stupid impl) while competing

  • 20 hours ago, # ^ | Perhaps it's difficult to definitively prove it, but it's quite intuitive. One increasing function is how much the power increases, another is how much it decreases, added together they make a convex function.

  • 16 hours ago, # ^ | ← Rev. 4 →   +2 Nope. We can prove the ternary search solution more easily. Suppose the number of squids is . The contribution of each is a convex function of . Since the sum of several convex functions is also convex, the statement is proved. Additionally, the allowed a brute force to pass the problem — just by noticing that there are at most different -s.

    • 9 hours ago, # ^ | Yes, but why is the contribution of each convex? The only proof we found is the one in the linked comment.

      • 3 hours ago, # ^ | ← Rev. 3 →   +10 I thought it was well known (I also missed the constraint), for example, here goes: Let be the function that we want to prove being convex. If we replace with , then we can consider this as a function not of positive integers, but of positive reals. I claim that this function is now piecewise linear, continuous, and convex. Indeed, if for some nonnegative integer , then , and is linear in on this half-interval with the slope . Therefore, if we prove that is continuous, then it's convex because the slopes are nondecreasing. To prove that it's continuous it suffices to check that (exercise for the reader).

• 22 hours ago, # ^ | I only solved D, so I am replying to problem D only. I think it affects the difficulty of the problem significantly. I came up with an easy solution that depends on the array's maximum number of different elements, which is feasible due to this constraint. My idea is that the maximum number of different elements would be achieved by an array that looks like 1 2 3 4 5 .... n. which would sum to n*(n+1)/2. So using the summation constraint you can easily prove that the max number of different elements is about 700. Which makes trying each possible squad size for every element feasible. Here is a link to my solution, I hope it helps someone. https://codeforces.com/contest/1928/submission/245866373