Доброе утро, Codeforces!
Разбираясь с задачей C(Div1), E(div2) я пришел к выводу, что авторское решение неверное, за что приношу вам всем огромные извинения.
Однако, как выяснилось, все претесты были верными, а некорректных взломов было очень мало (всего 3). Обсудив все с MikeMirzayanov, мы приняли такое решение:
Для Div2 задача E почти никак не влияет на результаты соревнования (взломов по ней не было, да и сабмитов было мало), поэтому для Div2 раунд будет рейтинговым.
Для Div1, контест можно будет считать рейтинговым, только если у этой задачи найдется какое-либо правильное приемлемое (в смысле времени его работы) решение. Я потратил всю ночь на поиски этого решения, но увы ничего хорошего у меня не вышло, поэтому предлагается силами сообщества побороть эту задачу (если это вообще возможно). Если в течение дня, то есть спустя 24 часа после публикации этого поста, не найдется правильное решение, Div1 контест будет нерейтинговым.
Еще раз приношу вам свои извинения за ошибку. Надеюсь, что нам удастся осилить эту задачу вместе. Не стесняйтесь, пишите все свои идеи в этот пост, даже какая-нибудь неправильная идея может намекнуть на верное решение. Мы будем очень благодарны всем, кто проявит активность в решении данной задачи.
Обратите внимание, что задача появилась в архиве задач. Сейчас все тесты к ней корректные, так что вы можете попробовать сдать решение в архив.
UPD: 24 часа прошло. К сожалению, никто не написал правильного решения или близкого к нему. Div1 раунд объявляется нерейтинговым. Огромное спасибо всем тем, кто приложил свои усилия и попробовал решить эту задачу.
С уважением, Агапов Геральд.
Just curious: Is searching + cut-case, or a probabilistic solution be considered an acceptable solution?
I think they should consider the number of correct hacks too. It can be incorrect actually.
Did 1663307 solved the problem?
Oh, no. This code have wrong "if" in the end of program. (if n != 20 print something)
Why don't you add a test to make this solution fail? Or else this solution seems to be right :)
Cause it's "if war". You can add all tests in archive to your solution.
Как скоро обновится рейтинг для див. 2?
UPD. Вроде обновляет.
Ура!!!!!Жду нового рейтинга!!!!!
Well, that's not so bad. It will be OK whether this round is rated or not. Personally I think the main point in involving programing contests is to enjoy the process of solving not the result whether you solved it or not. Maybe it will be easy to solve if you change the original problem a little? Hope you find the solution soon!
Если нормального решения не существует (пока), как вы можете утверждать, что все тесты корректны? Они все настолько маленькие, что брутфорс их берет?
Ну уж за ночь-то проверть брутфорсом можно.
Где-то руками понятно, что тест правильный, где-то брутфорс работает. Все тесты, где ответ получается непонятным голове образом, я провалидировал перебором локально.
Я прошу прощения, но кто-нибудь может пояснить, по какой причине не работает динамика, считающая, какое максимальное количество еды может свалиться на весы i,j с отрезка l..r?
Пример. Общий смысл — то, что не пересекаются отрезки, не обозначает то, что не пересекаются пути, по которым еда падает.
А, дошло, спасибо.
А вот вам и решение 1664332
Знаю, знаю, неверное, но всё-таки АС :)
I wonder how it is possible so many coders came up with the same, wrong solution ;). I was upset after the contest, because I had no idea for C and so many participants submitted it.
The situation is somewhat similar to the one after the SRM 539 at TopCoder. Model solution for 500 points problem was wrong, although 112 submissions passed system test with wrong test data.
As for me, I just sat down and wrote it because I had seen how many coders solved it and the first idea exatly fitted into TL. Also, I had a thought that it is entirely wrong but it was quicker to code and sumbit rather to think. It passed and it was enough.
I agree with DamianS comment. How is it possible that the people who usually do very well in codeforces wrote the same expected "wrong" solution all of them? I think the solution was clearly wrong. Thus, seeing so many very smart people doing the same simple mistake is surprising.
I think it's the ability to get solutions accepted. Actually it is common practice to get OK on an unproven program, with only some speculations on correctness. To get a high succes rate with such strategy, I guess one has to have extraordinary intuition. Besides, there are also hints on the scoreboard: how fast the problem was solved by the majority, how much time and memory did other solution take, and so on. Just some Jedi tricks...
The same thing happened in a TopCoder SRM a few weeks ago. The community couldn't find a solution in 24 hours so Div I was unrated.
Oh... I did participate that very contest!
I solved no problems there and they supposed that my rating would be subtracted by about 200 points. Then, it turned to be unrated and I was saved!
To make sure: You mean this contest, don't you?
yeap; I think # people solved demonstrates the difficulty of the problem; since many coders' solution passed the system test, probably people on the top of the rankings thought that probably the solution is correct.
when I looked at this problem, I immediately thought that it's reducible to one of the NP problem, upon which I figured that the constraint is too large to tackle -- I thought about it for > 1 hr during the contest, to see if there could be feasible solution otherwise, but wasn't sure till the end if efficient solution exists. I am just glad that it is actually hard problem, as my intuition served me correctly :P
"I immediately thought that it’s reducible to one of the NP problem"
What NP problem do you mean?
Just wanted to say, a lot of problems, including easy ones are reducible to NP-complete problems. For example, you can use SAT to solve 2-SAT, that does not mean 2-SAT does not have a polynomial solution.
In order to show that a problem is NP-complete, you also need to show that it is NP-hard — We need to reduce a NP-complete problem to problem C. If we can use problem C to solve a NP problem, then C is NP-hard.
Whilst reducing problem C to a NP-complete problem shows that it is NP-easy , which means it is at most as hard as NP-complete
I must have thought about this in the opposite direction during the competition; thanks for the correct (it is correct, right?) clarification :)
I think it's been 24hours
Правильно ли я понимаю, что 24 часа прошло, решение придумано не было и раунд стал официально нерейтинговым?
I think there should be a notice that warning no correct solutions found in the problem statement.
all problems are very interesting