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.
Is it unrated for both Div 2 and Div 1?
I guess since the problem was contained in both divisions.
Yes.
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.
Are you going to post the editorial to the solutions of the other problems?
Here it is!
No need for apologize
Yeah, there was nothing more to be done in that situation.
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).
Couldn't you wait with announcing the decision until you find a solution for A or prove that it is unsolvable?
If reds can't solve a div1 A in more than 2 hours something is wrong.
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.
Two consecutive unrated rounds? Sadly. Sadly. Sadly.
make it 3, edu is next.
Is the educational round unrated?
yes
The educational rounds are always unrated on purpose.
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.
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?
Can tourist help us :D XD
x2
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.
Understandable, have a nice day.
if you have no correct solution yet, why are you rejudging solutions?
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.
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?
Actually it does interfere, because hacks are tested against the jury solution.
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.
I see, thanks.
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.
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.
"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:
Parachutes took the first place in round 420 (Div 2) and 18th place in round 421 (Div 2), both unrated. :( Sad..
wow
i wrote both 420 and 421 rather badly
i am so lucky
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.
you'll do round 422 well enough to become purple, by induction :D
Can i get the link of Hackers profile .. ( he is the god of todays contest).
LLI_E_P_JI_O_K — found an issue. TearsFreeze — submitted a hack.
?????? What happened?
Nothing serious, just a bug in main jury solution which was found only after your tricky hack attempt to this problem :) good job!
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.
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.
The input is 3 1 4 10, and the answer is 4.
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: aaaaabcdeaaaaaaaaaaabcde
Edit: Actually, my counterexample is wrong.
One more rejudge then. Until there is nothing left :P
The computer adds
bcdefin this case since a = 5, doesn't it?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.)
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 :).
I have a noob question. How do I ask questions during a round? Thanks.
Mister B's game wasn't really boring afterall, I suppose.
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!
What is the solution for test case #64 (3 1 4 10)? Almost people can't pass this test.
s=abcbadeeabc...
http://codeforces.net/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.
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?
If you can prove, please do it — you can save the 421 round as nobody can find the proof.
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.
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.
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.
28130848 I submit the fixed version of code. Here is my idea: http://codeforces.net/blog/entry/52971
Enjoyed, Even just few second I got my best rank :)
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<a the suffix after Mister B's turn will have also letter(s) from the previous computer turn (or from the letters which where initially in S if they are in the first a chars in S), so what character to take from them to append b times in Mister B's turn ?
i chose the first letter of them which will appear in the chosen segment (because the first of them may not appear in the segment, then choosing it always may result in extra distinct characters in case it didn't appear in the segment), if non if them will appear or they all will appear in the segment then just choose the first of them.
the part of the segment length smaller than (a+b)*2 can be done by getting the 2*(a+b) part the contains this segment (by using remainders), and then looping through this part's elements to implement the logic.
link of submission: http://codeforces.net/contest/820/submission/28106255
two consequetive rounds becomes unrated.... soo sad...
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.
abcbadeeabcade and in 4 to 10 is badeeab. so answer is 4.
The string can be "abcbadeeab" for which the answer is 4.
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.
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.
Yes. A solution always goes with a proof, otherwise we can't call it a solution.
so what went wrong with the proof?
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
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.
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.
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"?
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.
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.
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.
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 :(
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.
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.
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!
Can anyone explain how the answer to the input 3 1 4 10 is 4..
abcbadeeabcade because this string has 4 different letters in 4 to 10
abcbadeeabcade and in 4 to 10 is badeeab. so answer is 4...
Got it thanks ... Got my mistake
KAN, I wrote a blog explaining my approach. You may check it to see if it can be proved valid.
No heat KAN :). What if there was a slight problem, we thoroughly enjoyed the problems. Cheers!
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).
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.
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
a>abc b>d a>def b>f a>def Resultant string>abcddeffdef String from L to R>ddeffde So the answer :-3
a->abc b->d then a will add aef because he sees the suffix as bcd.
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 contest_dhuye_pani_khai. Thank you
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.net/blog/entry/52951
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.
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.
it's a shame that this round is declared unrated, as the author tried to make this round better.
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.
I made my best performance ever, but not rated. What a day :)
Same here, and it feels really bad. Previous round I'd get +110 rating, now +170.
+67 and +134 missed here.
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 )
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 ?
abcdefghijkl llllllllllll abcdefghijkm llllllllllll
This 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 m
You can also have it like this:
abcdefghijkl mmmmmmmmmmmm abcdefghijkl mmmmmmmmmmmm
But still the answer remains 13
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 :)
This is the real problem of using heuristics without the habit of formally proving them afterwards.
KAN, these randomly chosen submissions produce different results on some cases (compared to blackEarth's submission 28106774):
4 3 3 928114739-YOUSIKI11 6 10074854 1007488828098573-Sakura8 4 10663755 1066376628090458-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!
blackEarth solution is incorrect.
8 9 2 25answer is9, but he answer is8.28088936 Maybe my solution is right..
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......'