So, if you paricipated in ER 176 and got WA2 on problem B, you might think this is a terrible problem, maybe one of the worst on CF. Let me try to explain why it was created, and maybe it will change your opinion about it (or maybe it won't).
This problem has an obvious solution: you have to maximize the sum of the first $$$k$$$ chosen elements and the last element you paint, so the sum of $$$(k+1)$$$ elements of the array. So, let's take $$$(k+1)$$$ greatest elements, add them up, and we get the answer. It even passes the sample test case, but it is wrong.
When preparing the problem, we had an option to discard the case when this greedy solution does not work. However, I didn't like that version of the problem because it just becomes a "guessforces" problem — people can just assume that you always choose $$$(k+1)$$$ maximums, submit the solution without proving it, and get Accepted. I believe we already have too many problems of this style on Codeforces.
To solve the current version of the problem, you have to actually find out what is wrong with the original idea, locate the case when the greedy solution does not work. I think that proving your solution or finding flaws in your ideas is a very important skill in programming contests, and this situation (when you have a "working" solution which does not pass the tests, and you need to find an issue with it) teaches this skill. This is also why the case when the greedy idea fails is not in the samples — otherwise finding the issue would be too effortless.
Were there any flaws with the problem itself? There was at least one, but it is not in its idea/preparation, but it is a mistake I made during the contest itself. The first global clarification for the problem was poorly worded, so some people assumed that an element has to have exactly two blue neighbours if we want to paint it. This was a mistake, and I am sorry for it. I probably should not have sent it in the first place.
But I still think that such problems should be on CF, especially because most other problems are set in a way that if you have a greedy idea which passes the samples, it passes the actual tests.
And why $$$n \le 5000$$$? I'm not saying that it's wrong, I was always against guessing solution from the constraints, but I'm interested in why you made that decision.
Mostly to allow solutions with complexity $$$O(n^2)$$$. For example, picking $$$(k+1)$$$ largest elements without having to use sort or nth_element.
Yeah I could feel that taking k + 1 elements was the correct greedy for k > 1 but could not explicitly prove it with 2 WA already . I just did O(n^2) solution with if I take last element to be first or last then just take the largest k elements and if the last element i take is in middle then I need atleast one element with index smaller than that element and one element with index greater than the last element . Hence I feel O(n^2) seems reasonable for Div2 — B
also today's problem F had low constraints on a[i] not sure why
the problem is trivially exactly the same with a[i] <= n and a[i] <= 10^9, since only relative order matters
despite it not making solution easier, i would request authors to always put <= n if the fact of "only relative order mattering" is trivial
I solved it using Fenwick tree haha 311142303
When you got the correct solution with the proof but you miss some other stupid case (didn't took the case where a[0]+a[n-1] can be maximum) such a sad LYF :c
Otherwise the contest was good thx for the contest
I hate it when people always complain about weak samples or weak pretests. If passing samples likely means passing the main tests, it's gonna be guess-forces!
It is not a "fun" problem at all. But I'll give credit where its due, its very possible to think about this problem (including the edge case) by considering when to make a particular element as the last element. You can then deduce that there must be a blue node both on the left side and on the right side and this guarantees that the starting element must be on the border. This kind of builds the intuition for the edge case.
You can then deduce that there must be a blue node both on the left side and on the right side and this guarantees that the starting element must be on the border.
Even after deducing that, I decided to solve it using fenwick tree lol
why they downvote you
Finding edge cases is part of the problem-solving process
We need more problems like this that are not "guessforces"
The problem is good. But it must be properly rated (at least 1400).
I couldn't solve it in time, but still enjoyed to think about it. For me, it was more like how to logically prove that with just two points I can always "cover" three maximums. Sadly, I was always thinking about the case
(.**..*.)and couldn't realize :) that we can always do this:(.*[*]..*.)where [*] is last.i think the issue was not the in problem it self (as of the concept) but everyone i knew managed to misread the "you have to select" part, i was included, well time to learn how to read :pensive:
eye issue
Actually, I got wa on test 2 on this problem, but it was actually a pretty good problem.
In greedy solution there is an edge case which k=1. I couldnt find it bcs i thought 2<=k<n, but it wasnt. It was a good problem!