Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

KAN's blog

By KAN, history, 18 months ago, translation, ,

During the discussion after the Round 421 it turned out that the author's solution was wrong. Yes, we had several testers, we had a bruteforce solution that worked correctly, we had a stress testing between the bruteforce and the main solutions. However, all these measures haven't prevented the mistake: the testers haven't noted the issue, the stress haven't found any counter-tests. The solutions also produced the same answers all small tests we had in the testset, so we only found the issue when a test used for a hack was added.

We are terribly sorry about the mistake. We did our best to ensure the problems are ok, I don't know any available method that we haven't used to check the problem.

We've spent the last few hours trying to come up with a new, correct solution to the problem, but right now I don't see any solution that seems undoubtedly correct to me. There are a few that work better than the author's, but yet unproved, you can try to prove this one, for example. I think this problem should be solvable with careful case analysis, and I'm trying to do this right now. I'll post the results here. I'd also be glad if someone post the solution with proof.

Thus, I apologize that the round should be declared unrated. Hope for your understanding.

•
• +611
•

 » 18 months ago, # |   -37 Is it unrated for both Div 2 and Div 1?
•  » » 18 months ago, # ^ |   +25 I guess since the problem was contained in both divisions.
•  » » 18 months ago, # ^ |   +22 Yes.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +39 Ok, thanks! I really enjoyed the round, btw. I think it was an honest mistake and÷ a difficult one to spot. I hope you won't get too much hate from the CF community.
•  » » » 18 months ago, # ^ |   0 Are you going to post the editorial to the solutions of the other problems?
•  » » » » 18 months ago, # ^ |   +6 Here it is!
 » 18 months ago, # |   -6 No need for apologize
 » 18 months ago, # |   +77 Yeah, there was nothing more to be done in that situation.
•  » » 17 months ago, # ^ |   +16
 » 18 months ago, # |   +27 In fact, if this round was rated, and if author's solution was right, I would have my best result in cf rounds today. But things happen. So I just hope for good (and rated!) rounds in the nearest future. And thanks to the author -- I really liked other problems today (and I'm waiting for an editorial).
 » 18 months ago, # |   +21 Couldn't you wait with announcing the decision until you find a solution for A or prove that it is unsolvable?
•  » » 18 months ago, # ^ |   +28 If reds can't solve a div1 A in more than 2 hours something is wrong.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +8 Yes, but so far it looks like the only wrong thing was the point value for div1 A/div2 C. It should be probably around 2500-2750 in div 1 A and 3500-3750 in div 2 C. If there is a formal proof of the solution, nothing else should make this round unrated.
•  » » 18 months ago, # ^ |   +67 make it 3, edu is next.
•  » » » 18 months ago, # ^ |   -14 Is the educational round unrated?
•  » » » » 18 months ago, # ^ |   0 yes
•  » » » » 18 months ago, # ^ |   +2 The educational rounds are always unrated on purpose.
 » 18 months ago, # |   +67 Sometimes, some things that are really out of our control and things that are least expected happen. This happes with each single person,and sadly cf is completely public facing, that makes people working there more vulnerable to criticism. Having said that, there are no 2 ways about the fact that CF is the best programming web-site out there.
 » 18 months ago, # |   +14 Thank you for all the work in the last few hours.I wondered If the round definitely unrated, or will there be a reasonable timeframe where if a proved solution is found will make the round rated?
 » 18 months ago, # |   0 Nevertheless thank you Author! Problemset very interesting! Good luck in the next rounds!
 » 18 months ago, # | ← Rev. 4 →   +98 Can tourist help us :D XD
•  » » 18 months ago, # ^ |   +8 x2
 » 18 months ago, # |   +112 I feel sorry to see Round #421 post with negative score.We all know that sometimes things does not go as expected, but as KAN said, all available measures were applied. I particularly liked Div 2 B and D, and even though the contest had to be made unrated I think is very unfair to adedalic and the testers to depreciate the contest like this.
 » 18 months ago, # |   +17 Understandable, have a nice day.
 » 18 months ago, # |   +1 if you have no correct solution yet, why are you rejudging solutions?
•  » » 18 months ago, # ^ | ← Rev. 2 →   +22 I believe that LLI_E_P_JI_O_K's solution is correct, so I think it's better now to have probably correct tests, that definitely incorrect.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   -9 if LLI_E_P_JI_O_K's solution is really correct, wouldnt be possible for you to correct the jury's answers and rejudge the contest's submissions and make it rated? I mean, if there are no problems with the pretests, it does not interfere with the contestants performance, or does it?
•  » » » » 18 months ago, # ^ |   0 Actually it does interfere, because hacks are tested against the jury solution.
•  » » » » » 18 months ago, # ^ | ← Rev. 3 →   0 Slightly.You should rejudge squee_spoon's solution as it was hacked and returned the correct answer.Edit: However it was done at the end of the contest. Around 1:58:30, so the effect was negligible.
•  » » » » » 18 months ago, # ^ |   0 I see, thanks.
•  » » » » 18 months ago, # ^ |   +56 Even if a correct solution is found and all submissions are rejudged, there is still a huge impact on performance. Some people would have wasted a lot of time on that problem thinking "there must be a simple solution, it's only A and 100+ people have solved it already", whereas people who decided to skip that problem or just went ahead with the wrong solution would have a big advantage. Thus the problem essentially penalizes the competitors who realized that the obvious solution doesn't work. The round is not supposed to be deceiving people into picking poor strategies, and that's why I think it must be unrated in any case.
•  » » » » » 18 months ago, # ^ | ← Rev. 5 →   +3 Incorrect point values should never be the reason to make the round unrated. It happens. You should never assume that the solutions passing pretests are correct.If you can't prove/solve the problem, you just skip it and solve the other problems.Edit: It's like saying — "E was much easier than D. I spent so much time on D and didn't manage to solve it within the contest time. If I'd tried E instead, I would have definitely solved it. Let's make this round unrated because point values were incorrect!"Everybody was given the same tasks and had the same issue of incorrect point value. It was fair and that argument is ridiculous. It has no rational basis and is supported only by people who would like to avoid rating lost, because of their poor performance.
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 "Div1 A is hard than usual" is not enough to make a round unrated. I think a round should be unrated if one of followings happens: there doesn't exist a correct solution something is wrong in pretest there exists a succeed hack: the defender's output is correct and the author's output is incorrect there exists a failed hack: both defender's and author's outputs are incorrect
 » 18 months ago, # |   +26 Parachutes took the first place in round 420 (Div 2) and 18th place in round 421 (Div 2), both unrated. :( Sad..
 » 18 months ago, # |   +7 wowi wrote both 420 and 421 rather badlyi am so lucky
•  » » 18 months ago, # ^ |   +4 I'm in the opposite situation. On both 420 and 421 I did well enough to become purple. Oh, well, at least I enjoyed the problems.
•  » » » 18 months ago, # ^ |   +42 you'll do round 422 well enough to become purple, by induction :D
 » 18 months ago, # |   +3 Can i get the link of Hackers profile .. ( he is the god of todays contest).
•  » » 18 months ago, # ^ | ← Rev. 2 →   +3 LLI_E_P_JI_O_K — found an issue. TearsFreeze — submitted a hack.
•  » » » 18 months ago, # ^ |   +8 ?????? What happened?
•  » » » » 18 months ago, # ^ |   +11 Nothing serious, just a bug in main jury solution which was found only after your tricky hack attempt to this problem :) good job!
•  » » » » » 18 months ago, # ^ |   0 Yes, but unfortunately that hacking attempt was incorrect, so the hacked solution will be rejudged and hacker will get -150 points. Fortunately it was in the end of the contest, so it should not have an overall impact on the round — provided that they will be able to prove the solution.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 Can you clarify what your hack input was, and what your solution says the output for it is? I'd be curious to run it against my solution.
•  » » » » » 18 months ago, # ^ |   +5 The input is 3 1 4 10, and the answer is 4.
 » 18 months ago, # | ← Rev. 5 →   +6 The solution of LLI_E_P_JI_O_K is (edit: probably not) incorrect. For test 20 (5 11 654321117 654321140, jury answer 6) there is in fact a solution that uses only 5 characters. Mister B can append only characters 'a'. The string between positions 654321117 654321140 will then be given by: aaaaabcdeaaaaaaaaaaabcdeEdit: Actually, my counterexample is wrong.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 One more rejudge then. Until there is nothing left :P
•  » » 18 months ago, # ^ |   +18 The computer adds bcdef in this case since a = 5, doesn't it?
•  » » » 18 months ago, # ^ |   0 You are right, my counter-example is wrong. I should have double-checked. (The assumption that the string repeats after two rounds is of course no longer correct with the updated strategy for Mister B.)
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 The queried string will be:ffff fghij fffffffffff fghi //My example is wrong ,i misunderstood suffix for prefix The output:5
 » 18 months ago, # |   +8 There is absolutely no need to apologize. I can only imagine how hard it is for problem setters to make sure that there are no mistakes in any of the problems. . Codeforces & problem setters for past rounds have done many incredible jobs, and I am sure they will do the same for upcoming rounds. Things like this happen in life, thus I hope that adedalic has not been too disappointed nor unsatisfied. I will look forward to solve your problems in the future :).
 » 18 months ago, # | ← Rev. 2 →   +6 I have a noob question. How do I ask questions during a round? Thanks.
 » 18 months ago, # |   +57 Mister B's game wasn't really boring afterall, I suppose.
 » 18 months ago, # |   +14 It's okay! We will always be forgiving. The only reason this contest was reviewed so negatively was because the last one was unrated as well. It is best to view these small blunders as independent events instead.On a positive note, the author adedalic came up with some great math-based problems, and we in turn got to practice some techniques that we rarely, if never, used before.Even though some of us did not get the rating we wanted, we carried away with us some far greater rewards: knowledge and experience!
 » 18 months ago, # |   +3 What is the solution for test case #64 (3 1 4 10)? Almost people can't pass this test.
•  » » 18 months ago, # ^ |   0 s=abcbadeeabc...
 » 18 months ago, # |   0 http://codeforces.com/contest/819/submission/28106247 I passed all tests, but I am wondering if it is correct. I try to think about all possible situations and solve them one by one.
•  » » 17 months ago, # ^ |   +3 I think my mathematical solution is correct. I can prove it if someone needs proof. BTW, why isn't there an official solution for div1 A till now?
•  » » » 17 months ago, # ^ |   +7 If you can prove, please do it — you can save the 421 round as nobody can find the proof.
•  » » » » 17 months ago, # ^ |   0 I don't think it can be saved now. Although I'd be really happy, if they made it rated, but after so long time, I don't even see a 0.1% chance.
•  » » 17 months ago, # ^ |   +47 Your solution is incorrect. Try this test : 10 8 7 40. Answer is 12. Also , 3 out of 5 AC solutions in Div1 is incorrect: 9 10 8 21, Answer is 4. But AC solution 28097355 answer is 3.7 2 70 86, Answer is 11. In 28096576,28090458 answer is 10.
•  » » » 17 months ago, # ^ |   0 Thank you! I find the bug as I didn't consider two very specific cases. This can be fixed by modifying one expresssion in my code. I'll submit fixed solution later.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 28130848 I submit the fixed version of code. Here is my idea: http://codeforces.com/blog/entry/52971
 » 18 months ago, # |   0 Enjoyed, Even just few second I got my best rank :)
 » 18 months ago, # | ← Rev. 2 →   +1 i have implemented an approach for div2 C and it is apparently working (it got accepted now)first, if the segment length is greater than or equal (a + b)*2 (the part which repeats), then if b >= a the answer is a + 1, else the answer is a + (a-b).but if the segment length is smaller than (a+b)*2, the issue here becomes what character to select in Mister B's turn, if b>=a then the suffix after Mister B's will have only letter(s) from his turn, so i just took the last letter currently in S and appended it b times (in Mister B's turn).but if b
 » 18 months ago, # |   0 two consequetive rounds becomes unrated.... soo sad...
 » 18 months ago, # | ← Rev. 4 →   0 on test 64 of div2-c which 3 1 4 10 jurys answer is 4 but mine is 5 the string is going to be abccadeeabccade and in 4 to 10 there are 5 letters can anyone tell the bug where i am missing? link to my solution. KAN IF you can answer that would be great update : i read the comment that there is string abcbadedabc sorry for trouble.
•  » » 18 months ago, # ^ |   0 The string can be "abcbadeeab" for which the answer is 4.
•  » » » 18 months ago, # ^ |   0 thanks my bad, i didn't searched thouroughly before commenting . thanks to both of you tokitsukaze bazsi700. just after commenting i read the comments of blog of round, there i got my answer.
 » 18 months ago, # |   +247 I understand that the CF admins are having a hard time now, so I feel sorry to ask this. But as nobody mentioned it, I will put it here : Did the problemsetter even bothered to make a formal proof of solution? Did anyone read the setter's proof and checked it? Having testers, brute force solutions, stress tests, is completely meaningless if there is no proof.
•  » » 18 months ago, # ^ |   +22 Yes. A solution always goes with a proof, otherwise we can't call it a solution.
•  » » » 18 months ago, # ^ |   +30 so what went wrong with the proof?
•  » » » 17 months ago, # ^ |   +55 I actually doubt that a problem to enter the problemset always goes with a proof. If that was the case, why so many editorials just show a small sketch of the solution instead of the proof? I belive, since it is already made, that the proof would be posted, but it isn't
•  » » » » 17 months ago, # ^ |   +7 I solve mathematical problems oftenly, and trust me, just because you can prove something, it doesn't mean you will write it down. It takes a lots of efforts sometimes, because the existing proof in your head is one thing, and writing down something other people can understand is another thing. It may take 1/2-2 hours, at a more complicated problem, and it's even harder, if you don't speak english perfectly.
•  » » » » » 17 months ago, # ^ |   +16 Oh, so when he says that a problem goes with a proof he means a proof is his head, okkk, then it's all cool. My bad.
•  » » » » » 17 months ago, # ^ |   +21 When you solve it for yourself, of course you don't need to write it down.But for creating problem on CF, I think problem setter must show proof to contest coordinator, otherwise how can KAN say "A solution always goes with a proof, otherwise we can't call it a solution"?
•  » » » » » » 17 months ago, # ^ |   0 I didn't say they shouldn't write it down. I just pointed out, just because they have a proof, it doesn't conclude, they will post it.I agree with the fact, that they should post it, I would be interested in some of them.
•  » » » » » » 17 months ago, # ^ |   +43 I think usually an author (if asked) writes a few sentences about the correctness and a coordinator thinks about it and either agrees that it's true and everything is fine, or there will be some more discussion. Please note there is no clear border from which a formal proof starts — you can explain almost anything in more basic steps.
•  » » 17 months ago, # ^ |   +154 There are various types of problems. In some problems, the correctness is perfectly clear from the algorithm itself. For example, consider a problem that can be reduced to maxflow. This value in the problem corresponds to the amount of flow in this edge, that value corresponds to that edge, ..., and so on. In this case the construction of the graph itself is the reason why it works.However, in some problems, we claim non-trivial things like "it is always optimal to do XXX". In this case we must prove the solution carefully. Especially, greedy problems require special attention because the claims are usually very intuitive and we tend to be persuaded by incorrect proofs. In AtCoder, I usually try to prove solutions from scratch, independently from writers.
 » 18 months ago, # |   -8 I am extremely disappointed with the CF platform. I am coming from some other platform and wanted to switch over to codeforces, but after two consecutive unrated rounds, I think otherwise :(
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 I can understand your disappointment because of the last 2 contests, but look at the past contests. I have been active here for 9 months now and I don't think there have been more than 4 (atmost 5) contests that have gotten unrated in all this time.That's around one every 2 months, which is not too bad. As someone mentioned above, mistakes happen.
•  » » 17 months ago, # ^ |   +15 Don't be disappointed. The point of online contests is mostly to learn something. That a single problem is wrong shouldn't matter — you could even skip it in your learning. If you participate in two or more platforms I believe it is even better because you see more ideas, you have more contests per month/week, so go on, don't give up on codeforces :). Also, as others have said, I'm pretty sure mistakes have happened and will continue to happen on other sites as well, so if you want a "perfect" platform you could simply stop doing CP.
•  » » » 17 months ago, # ^ |   +16 Did Atcoder contest ever ended by unrated?It's not sarcastic question,I'm just curious and relatively new on that platform but I'm so impressed with with site and rounds!Everything was perfect on 3 contest I participated,clear without bugs or delays and God I like pdf editorials so much!
 » 18 months ago, # |   0 Can anyone explain how the answer to the input 3 1 4 10 is 4..
•  » » 18 months ago, # ^ |   0 abcbadeeabcade because this string has 4 different letters in 4 to 10
•  » » 18 months ago, # ^ |   0 Got it thanks ... Got my mistake
 » 18 months ago, # |   -17 KAN, I wrote a blog explaining my approach. You may check it to see if it can be proved valid.
 » 18 months ago, # |   +4 No heat KAN :). What if there was a slight problem, we thoroughly enjoyed the problems. Cheers!
 » 18 months ago, # |   +6 To be honest, I performed way better than the previous contest so I was anticipating big increase of my rating but I got no ratings. However, I am not disappointed because the problems were interesting enough and I enjoyed solving them. Please cheer up and stop blame yourself(if you're doing).
 » 18 months ago, # | ← Rev. 2 →   0 Doubt related to problem — C.(Codeforces Round #421 (Div. 2)). test case — 3 1 4 10. Actual Answer — 4. My answer — 5. What I thought of is — a->"abc"|b->"c"|a->"ade"|b->"e"|a->"abc"|b->"c"..so on. thus string is "abccadeeabcc"..as for which there are 5 distinct characters between positions 4 and 10. Thank you..KAN Have a nice day.
•  » » 18 months ago, # ^ |   0 if you think it like this....a->"abc"|b->"b"|a->"ade"|b->"e"|a->"abc"|b->"c".......then there are 4 distinct characters between position 4 and 10
•  » » » 18 months ago, # ^ |   0 a>abc b>d a>def b>f a>def Resultant string>abcddeffdef String from L to R>ddeffde So the answer :-3
•  » » » » 17 months ago, # ^ |   0 a->abc b->d then a will add aef because he sees the suffix as bcd.
•  » » » » » 17 months ago, # ^ |   0 Ya i misunderstood suffix for prefix. Thanks for replying back. After understanding the question ,my solution was AC for all test case. http://codeforces.com/contest/820/submission/28138209.Link to my solution
•  » » » 17 months ago, # ^ |   0 I got it. Say l=3,r=4, in which case my approach works. Keeping such cases in mind I've followed that procedure. Now it seems like we have to be careful about many such cases if we follow my approach(even though it worked for first 64 testcases). So is there any other approach from_bd_with_alu_potol. Thank you
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 I used a complete search technique that avoids checking everything case by case. I wrote a blog about it. You can take a look at this http://codeforces.com/blog/entry/52951
 » 18 months ago, # |   -18 I totally understand mistakes can go into contests. We are humans afterall, we all make mistakes. But I don't think making 2 rounds unrated is a good idea.If the pretests were good (AFAIK they were), and a solution has been found already, then I see no reason to make the contest unrated. People passed pretests, fail system test, it's a thing, the problem was harder than a div1A but it happens like every third contest, that the order of the problems isn't good, but the contest is still rated.There were unsuccesful hacks, whose should be successful, but I don't think they affect so many people to make the round unrated. These hacks should be accepted, and that few people who got hacked this way, would fail on system tests anyway.On the other hand, there should be a system for these cases, because as we could see, these things happen. They could give more time for the corrected problem, or accept it for everyone, or don't accept it for anyone. I know these ideas aren't too balanced and fair, but taking away +100 rating from hundreds of users isn't fair also. There must be a good solution to this problem, and I hope, people smarter than me, can find it.
•  » » 18 months ago, # ^ |   0 Agree 100%.Misplacing problems is not rare,and yeah this is the epic one.If we have solution with proof (i.e problem is solvable) there is no clear reason for making it unrated,specially considering that last round was unrated too.I don't blame authors or KAN,but they should have in mind that there is a lot of people who got their best place in last 2 rounds and they missed over +200 deserved rating.
 » 18 months ago, # |   +1 it's a shame that this round is declared unrated, as the author tried to make this round better.
 » 18 months ago, # |   +4 Thank you for your explanations and no need for apologize. We enjoyed the problems and hope there will be more rated rounds soon.All my respect to your efforts.
 » 17 months ago, # |   0 I think every on can make mistakes...That does not make the contest unpleasant....but that make us feel a little bit angry..... but we must say thank you KAN And thank you for everyone who worked in this competition and we hope that the same mistakes will not happen again
 » 17 months ago, # |   +5 I made my best performance ever, but not rated. What a day :)
•  » » 17 months ago, # ^ |   +5 Same here, and it feels really bad. Previous round I'd get +110 rating, now +170.
•  » » 17 months ago, # ^ |   0 +67 and +134 missed here.
•  » » 17 months ago, # ^ |   0 I missed -121 and -179 in the past two contests :v I might be the luckiest person in codeforces right now :v(On the other hand, these two round has given me a valuable lesson. From next round I am going to start from A instead of C/D :v )
 » 17 months ago, # |   -8 for input 12 12 1 1000 output should be 12 : e.g. abcdefghijkl llllllllllll kkkkkkkkkkkk llllllllllll .......but the answer is 13. where am I wrong ?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +2 abcdefghijkl llllllllllll abcdefghijkm llllllllllllThis should be the string formed.The machine (player A) will output the first 12 letters which do not occur in the suffix of length 12 so, it will skip l and go to mYou can also have it like this:abcdefghijkl mmmmmmmmmmmm abcdefghijkl mmmmmmmmmmmm But still the answer remains 13
 » 17 months ago, # | ← Rev. 2 →   +7 It's really great of you KAN to answer the doubts of the participants here in the comments. Never before have I seen so many doubts being answered by the admin in the comments. Thanks on behalf of everyone :)
 » 17 months ago, # |   +4 This is the real problem of using heuristics without the habit of formally proving them afterwards.
 » 17 months ago, # |   +3 KAN, these randomly chosen submissions produce different results on some cases (compared to RNS_RMH's submission 28106774):4 3 3 9 28114739-YOUSIKI11 6 10074854 10074888 28098573-Kattana8 4 10663755 10663766 28090458-watersideThis problem has only 122 = 144 different inputs without the [l, r] part. I think that asking to answer multiple queries for the same a, b in one test file would make it much easier to prepare good tests for the problem!
•  » » 17 months ago, # ^ |   +20 RNS_RMH solution is incorrect. 8 9 2 25 answer is 9, but he answer is 8.
 » 17 months ago, # |   0 28088936 Maybe my solution is right..
•  » » 17 months ago, # ^ |   0 When adding an character,I choose the last one of the current string. example:a=4 b=3 the string is 'abcd ddd abce eee abcd ddd......'