So one thing led to another and now I'm here to share my results.
Codeforces Round 889 (Div. 1)
As of writting this blog that's the most recent codeforces round and there was some controversy about some problems in it. I'm here to talk about a funny thing that happened involving its div1E.
This story starts during the contest.
Revisiting E after solving the other problems, I thought "maybe using a bunch of ones and high numbers to build the number of ways greedily by adding up values in a row of the pascal triangle might be enough" and tried submitting that. It got WA as the gods of AC weren't on my side at that point. Then something clicked and I remembered a past problem that I deemed to be similar and had one idea that I remembered as something like "why the fuck would I think of doing something like this". In my mind at that point there were 3 pieces of info: "the related problem had some idea of trying all possibilites of -+1 -+2 -+3", "I think that antontrygubO_o had something to do with that problem, not sure if he was on my team or if he set the problem or we just discussed about the problem" and "I think it was in some open cup". As the time was running and I didn't even remember the year that the contest took place, I just trusted my memory and tried the following solution:
For each multiset of values 1 and 2 with sum less than 60, greedily build the number of ways that the problem asks for.
So I made some random tests that confirmed that the first idea was bad, adapted the code for the new idea, tested it for some random cases and got AC. Submission
I'm not here to discuss about the controversy surrouding that problem in particular, the funny part starts from here.
Identifying the problem
After the contest, I chatted a bit in Um_nik's discord server lightly complaining while hoping for my solution to not FST about how I solved the problem with these exact words:
solving today's E by "I remember that there was a problem in some opencup that wanted number of subsets with sum 0 and the intended solution was using -+1, -+2, -+3, 0 and some big numbers or some shit, I hope the same works for this one" makes me feel dirty
Then anton himself showed up confirming that it was his problem. Fast forward from a few days ago to today, it turned into a chat about the problems being similar or not. That enticed my curiosity a bit, as my memory of the solution to that problem was a bit fuzzy. By googling "antontrygub opencup codeforces" I found this blog. I checked the codeforces gym to check if that contest was there and it was. Then, as reading every statement until finding the problem was too much work, I opened the editorial and looked for it in there, as I remembered the thing about -+1, -+2, -+3. Bingo! Browsing through it I found {−3, −2, −1, 1, 2, 3} in there, so it must be that problem. The problem is problem K and it seems to have been set almost 2 years ago. In fact, the link between me and the problem is that I took part in the Petrozavodsk camp that featured that contest.
The similarity between the two problems
Let's start this by first stating what both problems ask for
1854E
Output a sequence of size at most 60 of positive integers such that there are 1 <= K <= 1e10 subsequences with values that sum up to exactly 60.
K-onstruction
Output a sequence of size at most 30 of integers such that there are 1 <= K <= 1e6 subsequences with values that sum up to exactly 0.
From now on I'll call them "Problem 1" and "Problem 2". We can see from this that the problems indeed are very similar. Upon further inspection of the editorial, the intended solution for Problem 2 was some weird construction that expands values to be higher and higher along with a dp that links the ways of summing 0 and the transition is considering some sets with values +-1 +-2 +-3. That's quite different, since in Problem 1 we can't use negative numbers.
That lead me to the question of "how similar are these 2 problems?". I then found the following construction:
"Almost reducing" Problem 2 into Problem 1
If we're able to solve an instance of Problem 1 under some different constraints, then we can solve Problem 2. The constraints are: Output a sequence of size at most 29 of positive integers such that there are 1 <= K <= 1e6 subsequences with values that sum up to exactly 60. Let's call that Problem 3. We can solve Problem 1 for K by solving Problem 3 for K-1 and then appending -60 into the sequence. This is "almost reducing" since that idea by itself can't guarantee that a solution existing for Problem 2 implies a solution existing in Problem 3.
After finding that idea, I was very interested by this, since it might work and give me a chance of passing both problems using the same solution!
One stone two birds
I copied my solution to problem 1 and editted it to those constraints. After testing with some random values, I couldn't solve it with the same code because I used only numbers 1 and 2, so I added the possibility of taking 3s as well. After pressing up arrow + enter about 30 times, it seemed to be working so I changed the code in order to validate that it'd solve every value. It took about 20 minutes but my asserts weren't triggered, now our reduction is complete by exhaustion! Then it was just a matter of adapting the code in order to accept the input of both problems at the same time. I also did some constant optimization by memoizing the number of ways to sum each value up to 60 for every choice of 1s, 2s and 3s. This is the result and it indeed ACs both problems.
Conclusion
- If you have good memory, you can solve div1Es by just remembering past problems.
- Trust your instinct of "I remember seeing a related problem", it might lead you into guessing solutions.
- Proof by AC and guessing is optimal for codeforces, as confirming that the solution worked for 1e6 took 20 minutes.
- [notorious coincidence] Even if you're closely related to a problem you might not remember it, and that's how repeated problems usually happen. This is evidenced by antontrygubO_o not realizing that he set a problem that's almost the same thing to that div1E. Had he realized it, dario2994 most likely would've rejected the problem, as anton was a tester of that div1 round and he couldn't solve it during testing.
- I see nobody mentioning that problem other than me and that problem was set 2 years ago, so maybe repeated problems aren't all that bad for most people? [unconfirmed] I think that we've had problems that were related to IMO problems, why would that kind of problem be acceptable and not problems that were related to ICPC problems?
I wrote this in one go so I'm sorry if there are any grammatical mistakes. Those usually happen when I backtrack and add something to a sentence without checking if everything's connected properly.
I'd like to add that the problem getting into the round isn't anton's fault at all, as people forget things and he's also a human. Testing and setting problems is a tough thing to do and sometimes these things happen.
About conclusion 5, where do you get the idea that problems related to IMO problema are ok either? They are just as bad, and should not appear, however if they do, their impact is smaller.
I don't think they're ok but my impression is that less people will care about it since it's "novel for cp". Related https://codeforces.net/blog/entry/105259
I believe if there is stuff out there that is novel for competitive programming, then people should be introduced to it via blogs, not contests.
Problems should definitely not be copied or almost copied from other contexts to introduce ideas to cp, but I disagree with this general sentiment.
I think novel ideas in contests should be encouraged, whether it is a completely original thought or an idea taken from another area (but that doesn't mean it should be copy pasting problem from that area, it should be the idea is incorporated into a completely new problem fitted for cp). I think it's good to expand horizon's a bit of what cp can deal with rather than just being combinations of same old monotonicity arguments and super well known algo/ds bashed together.
The most amount of contestants will be exposed to a new idea if it is put in a popular contest, and people don't really care to learn new ideas unless it is part of an actual problem. Also, it gives the chance to see if top contestants really have original/creative thought or if cp problems are only recalling and bruteforcing previously seen ideas. It is boring I almost never see a problem with a completely new idea anymore, cp was probably most fun as a complete beginner when I was seeing new ideas novel to me in many problems.
I'd like to also see a blog about a new topic after the contest it's introduced in of course :).
Extra ideas: I'd also like to see some new problem formats, but where they still work in same submission setup. For example I'd like more interactive problems dealing with memory complexity or information theory like CEOI14 question. I remember JOISC having a few non-standard interactive setups over the years. Also more problems on some less common cs theory topics in cp would be nice, such as randomization and approximation algorithms.
I guess the context of my comment was not super clear — the comment just above mine says it's okay for a lot of people because it is novel for CP. The "stuff" I talk about are problems, sometimes taken almost verbatim from math Olympiads. That is the part I don't like.
Copying problems from MO gives a small subset of contestants an advantage, but for the rest it provides value that they could have potentially gotten from doing MO. That is the tradeoff involved here, and I am not really a fan of overemphasizing the value of copypasted MO problems in competitive programming, more than required. If certain problems are cool, people make blogs on them and there's quite a bit of discussion under them, and there's nothing wrong with that. Not to say making problems with a MO flavour is bad (in fact, I like MO flavoured problems much more than, say, data structure problems). I feel competitive programming is much easier to categorise, than for instance IMO shortlist combinatorics (famously the dumpyard of miscellaneous problems that no one wants in A, G or N), so there's definitely a lot of scope.
In short, the right way to introduce a meta/flavour to other people is to either put effort and tailor problems to the context you're adding value to or write blogs on them, rather than make competitions unfair and copypaste problems from such contests. I am someone who would have benefited as a contestant from the MO copypasting meta, but solving such problems makes me disgusted with the problemset and the authors most of the time, and induces a bit of guilt too.
You found a problem from 2 years ago that, after a nontrivial reduction, can be solved using your div1E solution (not the other way around). For this reason you claim: "you can solve div1Es by just remembering past problems", "Proof by AC and guessing is optimal for codeforces", "notorious coincidence", "Had he realized it, dario2994 most likely would've rejected the problem".
I am tired.
I thought we were in agreement in the "Proof by AC" comment, as you yourself mentioned that proving that the solution works isn't necessary even for setters unless you mean that your intuition is always correct, which if that's the case I wish I had such level of confidence.
About the reduction being nontrivial and whatnot, it's way easier and simpler than some stuff that gets omitted in editorials all the time, I wish everyone cared about stuff being nontrivial as you and me. In my opinion, it's not too hard to see how both problems are related. Would you actually use that problem even after knowing the other problem exists? If that's the case, then I'm slightly more glad than before.
The notorious coincidence part is just that the previous problem's setter tested the new problem and "notorious" just because of the meme, nothing deeper than that.
I'm also tired but in a different way.
It is interesting to see how tfg recently is bringing that much attention to the issue of problems being "guessable". My read on the situation is that before tfg saw competitive programming as the idealistic sport that is super fair and promotes real problem solving, but recently he realised that some things are not that fair. I personally think that problems being guessable is not that big of issue. I have a few questions:
1) Were problems from before of higher quality in codeforces?
2) Any examples of good problems that apeared recently in cf rounds?
3) What is a bigger issue: lack of originality or problems being guessable?
4) Dont you think if someone is a big guesser he takes too much risk and this might not be optimal to maximize rating in long run?
5) ICPC or CF or IOI or Atcoder has higher quality of problems?
6) Doesnt IMO skill and ability to prove stuff correlate a lot positively with CF rating?
I think that I'll answer this in a separate blog. A short version of my opinion is that there are too many problems getting low spots in rounds solely due to how easy they're to guess, without considering at all how hard they're to come up step by step or to prove. That makes it a "guess it or lose it" situation for most people. I've seen people getting molded by these problems, their usual solving method is guessing a solution without thinking about the problem and trying to disprove it by drawing cases, then they submit it based on "lack of counterexample". I'm sorry to have doubted the complaints of people saying that cf rounds aren't pleasing due to many problems not being approachable.
where's this separate blog?
??
During the contest I noticed a similar problem existed before, but didn't comment on it. It's not because I don't care repeated techniques. The reason is that the problem is not hard. This time it was Div1.E but it was fairly easy for its position even if you don't know the similar problem. Therefore, to me the situation seemed like that a medium problem used a similar technique that appeared a few years ago. (Actually, I've forgotten it until I see this blog.)
I agree that the problem not being hard makes it easier to accept it having some similar past problem but if we're to use that reasoning for this problem then the same must be done for usual div1A-C and maybe even D problems. I'm not against it, as I think I'd benefit from it ofc. I completely support that being the standard for div2 only rounds.
Ok