Добрый день!
Спешу поделиться своими мыслями о недавно прошедшем раунде 382.
Конечно, получилось так себе и расстроен не только я, но и координатор раунда Глеб GlebsHP Евстропов.
В данном раунде основной негатив вызвали две задачи: задача 735D - Налоги и задача 735C - Теннисный Чемпионат.
Касательно 735D - Налоги я не вполне разделяю критического отношения к этой задаче. В самом деле, для ее решения неплохо было иметь представление о проблеме Гольдбаха, да и вообще о распределении простых чисел. Эти факты являются средне-популярными в среде спортивного программирования (нельзя сказать, что все-все их знают и умеют применять). Знакомство с ними полезно, дает полезное представление о простых чисел. Что важно: в этой задаче необходимо было выполнить несложное, но всё-таки, сведение к известной формулировке о представлении числа в минимальным количеством простых. Этот комментарий, например, подтверждает это. Мне кажется, что это нормально использовать задачи, которые имеют сведение к каким-то популярным и полу-популярным темам. Иначе, стоит выкинуть на свалку огромный пласт задач.
Как резюме по этой задаче. Я согласен, что задача 735D - Налоги не является образцом кристальной свежести, но имеет право на существование в качестве одной из задач. Каким-либо аргументом в пользу нерейтинговости раунда она являться не может. Лично я, такую задачу в проводимое мной соревнование не взял бы, но факт использования гипотезы Гольдбаха (а чаще теоремы о распределении простых чисел) для меня не является причиной клеймить и разворачивать задачу.
С задачей 735C - Теннисный Чемпионат ситуация значительно сложнее. Здесь не стоит смешивать две принципиально различные причины возможного возникновения совпадения задач:
- Задачи могут совпасть случайно, непреднамеренно. Конечно, и координатор и тестеры всегда критически смотрят на задачи и на этапе подготовки контеста немедленно реагируют, если такую задачу где-то видели. Стоит понимать, что задач за годы существования спортивного программированию появилось огромное количество различных задач и быть знакомым даже со значительной частью их не представляется возможным. Каким бы опытным не был коллектив жюри, подобные совпадения, к сожалению, будут случаться. Отмечу, что если раунд не является этапом чемпионата и по его результатам не разыгрываются призы, то основными причинами участия в нем должны быть саморазвитие и желание получить фан от соревнования. Ни одна из этих целей не включает в себя поиск похожих задач в Гугле.
- Преднамеренное совпадение или переиспользование задачи — это совсем другая история. И здесь произошло именно это. Такая ситуация является абсолютно недопустимой (образовательные раунды не в счет), с ней надо бороться и резко реагировать на инциденты.
Как только я узнал о произошедшем, то немедленно созвонился с автором и обсудил (и осудил) ситуацию. Я объяснил недопустимость таких случаев и их последствия. Мне кажется, Альберт сделал правильные выводы и впредь будет аккуратнее. К сожалению, об этом инциденте я узнал только после подведения рейтинга.
Учитывая, что большое количество участников проскочили мимо этого инцидента, решали абсолютно самостоятельно, порадовались или огорчились изменению рейтинга, поделились своими результатами в соцсетях мне не кажется уважительным по отношению к ним сделать этот раунд нерейтинговым. Я разделяю мнение, что лучше бы ему таким не быть, но история уже состоялась. Отмечу, что если бы о ситуации я узнал во время соревнования или сразу после него, то исход мог бы быть и другим. Думаю это неплохая идея сообщать о подозрении на подобные случаи через систему вопросов-ответов, чтобы координатор или я могли оперативно прореагировать.
В качестве вывода, я предлагаю не разводить трагедию, а сделать выводы, координаторам не впадать в отчаяние. Авторам, конечно, надо понимать всю ответственность и важность взятой на себя роли. Тысячи участников приходят порешать ваши задачи и, конечно, ожидают что-то интересное и новое.
Сообщество я призываю не забывать об уважении к труду авторов — подготовить контест это большая и сложная работа. В неё вовлечено большое количество людей — автор, координатор, тестеры и моя техническая помощь. Автор берет на себя непростую роль и раз раунд состоялся, то проделал непростой путь от идей до конечной реализации. Пожалуйста, будьте благодарны за это, говорите авторам, координаторам и тестерам спасибо! Какие бы усилия не прикладывала команда Codeforces, мы не можем сами без авторов подготавливать и проводить раунды. Поэтому мы ждем ваших задач и пусть у нас будет больше хороших и ярких раундов!
Спасибо за внимание,
MikeMirzayanov
Гугление задачи для CF раунда это вообще какая-то глупость и делается только чтобы потешить свое ЧСВ рейтингом больше, чем человек заслуживает.
Что не очень понравилось в этом контесте — 4 задачи были очень простыми, а пятую решил только один человек. Захотелось сразу узнать, как она решается. Так вот, где разбор-то этой пятой задачи? Сутки уже прошли, ну.
http://codeforces.com/blog/entry/48659
736E?держи
736С = div2E
Сделаем динамику по дереву.
Назовем вершину покрытой если есть покрашенная вершина на расстоянии не более k.
запустим dfs и будем считать 2 динамики
up[i][j] — кол-во способов покрасить вершины поддерева i так, что все вершины поддерева покрыты и все вершины выше i на расстоянии не более j будут покрыты. (это эквивалентно нахождению самой неглубокой покрашенной вершины, но представленная динамика проще в реализации)
down[i][j] — кол-во способов покрасить вершины поддерева i так, что самая глубокая непокрытая вершина находится в поддереве на расстоянии ровно j от i.
Далее несложно придумать пересчет (за O(nk^2)).
(Мое решение: http://codeforces.com/contest/736/submission/22551523)
Ответ на задачу является сумма up[0][i], где 0 — это корень.
Что уж там. Это — не первый случай, когда дали очень популярную задачу. Но, возможно, первый случай, когда автор заведомо знал о том, что это так. Очень важно отметить, что ему, повертевшему на чём-то там всё сообщество Codeforces, погрозили пальчиком.
Ну а в целом, уже много раз было такое, что люди тихонько копировали чьё-то решение задачи с TopCoder или SPOJ и никому ничего не сообщали. И их не дисквалифицировали, хотя об этом писали в комментариях, и раунд не делали unrated, хотя задача бывала совсем идентичной.
В данном случае, многим остается только не согласиться с членами команды Codeforces, которые в который раз оказывают непонятно кому медвежью услугу, оставляя раунд рейтинговым. Ну и будем знать, что организаторы предпочитают не читать комментарии участников после раунда. А зря! Там много всякого полезного можно прочитать: указывают на читеров, на баяны, на ошибки авторов.
Объясни мне, почему раунд должен быть нерейтенговым? Были ошибки в задачах, которые превращали их в неверные? Вроде нет. Были ошибки в тестах? Вроде нет. Была паленая задача D1A, которую по-моему гуглить было дольше, чем решать! Вроде бы все (или почти все) до 400 места сдали первые две в пределах часа.
Я не оправдываю автора — так делать нельзя. Но делать анрейтом этот раунд по-моему не верное решение.
Я бы хотел немного добавить к сказанному MikeMirzayanov. Мы вместе с winger как всегда прорешивали раунд перед официальным стартом, поэтому в произошедшем есть немного и нашей ответственности. В частности, я прорешивал обе задачи, о которых идет речь.
Во-первых, задача Налоги на мой взгляд абсолютно нормальная. Я не знал этот факт перед решением этой задачи. Однако, сразу после прочтения стало ясно, что надо раскладывать число на простые. Пара примеров убедила меня, что нужно не очень много простых. Тогда я воспользовался Гуглом, что насколько я знаю не запрещено участником соревнования. Первая же статья дала мне именно то, что я искал. Итог — задача сдана за 8 минут с момента прочтения. Допустим, вы знали этот факт. Тогда возможно преимущество в минут 5. Но это не страшно, это "погрешность придумывания" между участниками. Итог, я знаю чуть больше, чем до решения этой задачи.
Задача Теннисный чемпионат. Я видел много задач, но ее не видел, к сожалению. Не сработал "детектор" в этот раз. Гуглить задачи не привычно, вот я и не гуглил, особенно учитывая, что задача очень не сложная. Тут опять же, преимущество "видел" было не критичным, однако это другой случай. Будущим авторам надо сделать вывод из произошедшего и не допускать такого.
Готовить раунд — трудно, это факт. Это труд многих людей. Особенно хочется отметить Глеба GlebsHP, который потратил, без преувеличения, титанические усилия, для того, чтобы раунд состоялся, а также, конечно, Славу winger. Глеб в который раз поражает меня своей работоспособностью и ответственностью! В конечном итоге, раунд состоялся, задачи были без багов и итоговая таблица выглядит довольно живой, значит народ порешал задачки, а это главное.
http://acm.timus.ru/status.aspx?space=1&num=1356&author=40804 классный акк, палиндромный! Твой? :)
Ага :) нифига себе! Я только сейчас заметил! UPD: блин, решать новые не хочется теперь, 767 решенных тоже палиндром :) droptable должен оценить! :)
Саша, давай я тебе поясню. Тебя потроллили тем, что ты сдал задачу, о которой сказал "я не знал этот факт". Никому на самом деле не интересно, палиндромен ли твой ID на тимусе и, тем более, количество решенных задач.
ммм... Не думал, что dalex такой шутник. Думал, что он искренне так заинтересовался палиндромностью аккаунта и подкинул еще один замечательный палиндром ему в подарок. Вот так и верь после этого людям. Слава Богу у нас есть ты, Паша, который может открыть глаза на этот суровый мир троллинга.
Ну да ладно, давай внимательно глянем на время АС... Ух ты! 2 марта 2006! То есть больше 10 лет назад. Я еще тогда на паскакале писал. Блин, какой я оказывается старик уже... Сейчас поглядел на код... вообще хз, что там написано, какая-то филькина грамота.
Если ты думаешь, что я намеренно пытался ввести людей в заблуждение (соврал), что "я не знал этот факт", то поверь мне с 2006 если я тогда его и знал, то в ноябре 2016 уже давно забыл. И я по шагам рассказал как я сдавал эту задачу на прорешке. Не совсем понимаю зачем мне врать, но если уж ты и многоуважаемый товарищ dalex мне совсем не верите, то мой запрос до сих пор есть в моей истории браузера (суббота, 26 ноября в 4:30PM).
Да вы в моих глазах вообще такие супер-герои в черных плащах. Вы приходите в сложный момент и помогаете — читаете условия, пишите решения, оставляете фидбек. Спасибо большое!
After all, this was a good contest.
Also it adds to my knowledge. :D
Thanks for the response, it was an educational experience.
We respect your decision. :)
As writer of several rounds and many tasks in last time, man who finally succeded to reach div 1 on this contest and the most important man who loves codeforces I want to share my opinion and thoughts about all this things.
For me contest wasn't too bad, I do not believe that tasks like fourth is accepted from coordinator side, but still other tasks were new and interesting for me. The fourth wasn't bad at all too, but I think his place is more on educational round. Anyway as always I done everything alone and I am really happy that I got such good place on fair way !
Matching is happening, it happened to me at least 4-5 times (normally I didn't publish all such tasks), nobody can expect to know all tasks on the world, but situations with same tasks twice or even three times on the Codoforces are not good ! Coordinator must know 90% tasks from platform. Even with reading them one-two times he will remember the most texts... We are talking about red coder who is enough smart to do it, not about IQ sufficiant person!
Maybe one suggestion which can make Codeforces better in future contests, maybe you can use tasks from different authors like other platforms sometimes at the round. For example find three-four guys which will prepare many tasks for you and everytime when current setter don't have one or two proper problems just put task from well-known setter on that place. Also you can merge three authors and make two rounds from their tasks...
At the end I must say that all things are not so bad, for me and for some my friends level of last Codedorces rounds is again higher than before 3-4 months and there is much smaller amount of mistakes :)
На самом деле, куда важнее вопрос, почему организация контеста от заявки с готовым набором задач до собственно раунда занимает почти год? Я бы на месте albertg послал бы вас к черту. И т.к. я не один тут такой умный, становится досадно, что хорошие контесты потенциально проходят мимо меня на более расторопных площадках-помойках, вроде codechef.
Возможно, следует сделать информацию о пуле контестов публичной, набрать несколько координаторов, ввести сроки рассмотрения заявок?
Да, странно, по моему опыту это не больше месяца. Но может быть, какая-то задача была год назад забракована, а на новую пришлось целый год потратить.
Я первый ответ получил только в августе. 8 месяцев задачи просто так лежали.
Codechef — расторопная площадка — помойка? Аргументируй свой ответ, а то как-то некрасиво такие выводы бросать без пояснения.
Не могу ничего сказать на счёт их расторопности, но в том, что codechef та ещё помойка, легко убедиться, написав там контест.
Как убедиться? Вот никак не могу понять.
Написав там контест.
Блин,я вот много написал контестов, но не понял что это помойка. Помоги
Thank you for taking the time to write this so nicely.
Ну че, когда следующий раунд? :)
Perhaps it's also important to raise this issue from albertg's post:
Did albertg get informed that contest begins in two weeks, and he must change new problems in that short time? Or, he got informed about problems quality and was given as much time as he wants to prepare some new problems?
If it was the former case, I can understand why albertg (or any other problemsetter) might do it. Even for Div. 1 A, (good) problem ideas do not come from the snap of a finger, and sometimes I can come up with many good problem ideas in a day, sometimes I can think a week and I get not any good ideas. Still, in this case, he should tell GlebsHP (problem coordinator) that he cannot think any good idea, so maybe GlebsHP can contribute his own reserve problem, or he can request for more time. Better to have a delayed but good contest than a rushed but bad one.
If it is the second case, then this is just absolutely unacceptable, and albertg absolutely have no excuse for this situation. This is just a sign of laziness, and problem writers should absolutely never compromise the quality of a contest just because they are too lazy to come up with new problems. This is cheating the community from a good experience.
I also sent a proposal around this time (early this January), until now my problems quality have not been checked yet. At least, I know waiting game is being played by everyone else as well ;). Hopefully, problemsetters can learn from this event and take steps to avoid this tragedy from happening again in the future.
I personally do not like to share any information about the internal processes, especially with people who are unfamiliar with how they usually look like. However, I consider it would be reasonable to step in now as the sentence being cited is really misleading and might cause the wrong understanding of how the preparation process looks like.
The problem "Tennis" was proposed by Albert long ago the round was put in the schedule (in August to be more precise). Moreover, he wasn't asked to propose any new problems after the contest date was finalized.
Some more internal details, not directly related to the issue. Usually, the problemset is finalized before the round is put in the schedule. It might not be the case only for very experienced authors which we are sure can deal with changes in a short period. If I request changes in the problemset with a few days to go before the round (that also happens) I always help authors to make these changes or even prepare something myself (for example, that happened with the problem div1C of Albert's round — I replaced it with the problem "Ostap and Tree" and took care of tests, sols, etc.).
As for your proposal being waiting in the queue — sorry for that, one year is indeed too much. If you are still interested in conducting a round I'll take care of it in the nearest future.
"that happened with the problem div1C of Albert's round"
Yesterday, I was telling myself although people criticize, his div2E/div1C problem is quite interesting and challenging.
Anyway, thank you for the problem and the solution you explained.
I think there are three different reasons:
Accident. No writers or testers know the existence of the same problem. This is sad but is nobody's fault as Mike says.
Mistake. For example, someone have read the same problem but forgot it, the writer accidentally published the problem but didn't notice that, the writer has used the same problem but forgot it, etc. This case is similar to the case where the writer's solution is wrong — this is clearly a fault, the writer should apologize and try hard not to do the same in the future, but everyone can make mistakes. We shouldn't blame the writer too much. Personally I did this once: I tested both SRM 527 hard and SRM 669 hard.
Deliberate coincidence. For example, the writer intentionally uses his own problem twice, or steals someone else's old problem, in order to get paid with small amount of work (or for whatever reasons). I'd call it cheating and when this happens the writer is worth getting banned from the community.
And this case was the second but not the third, judging from http://codeforces.com/blog/entry/48663.
I was just wondering what was the process of publishing the problem on SPOJ. Was it hidden from the beginning or was it available for a moment and then became hidden, because of some inconsistency in a statement?
I just wonder if it was hidden, how did people find out about it? Do they just type spoj urls and different task names?
While I agree with your classification of reasons and the way you judge them, I'm not sure if you are right considering the current case to be just a mistake. If the author knows the problem was used at some other judge but believes it is hidden, he must notify the coordinator about this.
Carelessness is still a mistake, not intentionally trying to screw people over.
We all do mistakes. I think we should not make this such a big issue and continue doing what we must .
I am still very new in programming and from my perspective programming is like a game to me.
It gives me pleasure when i solve a problem . We all love it . We are problem solvers :p , we just want to solve more and more good problems and improve our skills . So thinking too much about this kind of issues will only ruin our focus .. :) .
We all know it very well that preparing a contest requires a lot of effort and is not an easy task at all . So Those who work behind the scenes require our support and motivation . We can at-least give them that ? Can't we ? :)
We all do mistakes. I think we should not make this such a big issue and continue doing what we must .
I am still very new in programming and from my perspective programming is like a game to me.
It gives me pleasure when i solve a problem . We all love it . We are problem solvers :p , we just want to solve more and more good problems and improve our skills . So thinking too much about this kind of issues will only ruin our focus .. :) .
We all know it very well that preparing a contest requires a lot of effort and is not an easy task at all . So Those who work behind the scenes require our support and motivation .We can at-least give them that . :)
I think the real problem here is that it takes 1 year so that your problems become a contest (the problem setter said he waited for a very long time and meanwhile he uploaded his problem to SPOJ). I know making a contest is a complicated process, but there is a lot of room for improvement in this area. It should take less time to make a contest, and this will result in more frequent contests :)
He uploaded the problem in January of 2014.
After all, Codeforces is my favorite contest platform. Thank MikeMirzayanov for great Codeforces.
А дайте ссылку на дубликат http://codeforces.com/contest/735/problem/C
Хочется сравнить.
TENNIS1
To look at this from a different and positive point of view, I am very glad to see that issues like this are discussed in such a great detail and consideration. Shows what a great learning community codeforces is!
How many people were affected, anyway? If it was up to me, I'd lean heavily towards unrated, unless the affected set of people was really small or the problem was really hard to look up.
Thank you Mike for the explanation.
Speaking of hard work, the issue in a big contest website, such as Codeforces is much more complicated than "one small" contest.
Assume this situation: if the contest manager can ask writers to make problems (+ solutions, test data, editorial, etc...), how can you be sure that the writers will devote themselves not to make any mistakes?
Preparing Codeforces problem set is not a non-profit work, but the payment for writers here is much less than that of TopCoder. (I don't say about that of AtCoder, but you can guess some from Japanese competitive programmers' tweets.)
If you have a problem set that can be used for both TopCoder and Codeforces, which contest will you writer for? You may answer Codeforces because it has several times larger number of participants, but what if there'd be another contest website that pays a lot and has many contestants?
I'm anxious that when there'd be more contest websites which pay good writers more money than Codeforces, only less skilled writers who cannot write for high quality contests would remain here. I think so many Div2 only contests compared to the number of Div1+Div2 contests these months can explain some.
Of course there will be mistakes even with high payments, but you can start with high quality problems with much originality, and writers will check problems more carefully for keeping good terms with the company. That determines the quality of this website, and also, the amenity of entire competitive programming community.
I don't disagree with any this, but it is still incredible to me that Codeforces as a product that is free can afford to pay writers at all, on a site that has no advertising or anything else. As a contestant I feel like I get a really great deal, complete use of site for free, all while Codeforces is paying to acquire problems :)
What's the payment for AtCoder?
There are large, fundamental differences between TC and CF. TC is a company, for-profit, which means it can give out more; CF is, afaik, dependent on sponsorship and maybe some university funding? Also, the living costs / salaries in post-USSR countries are different from the West.
The key point of CF should be quality rather than money (especially once the bubble fails). When I was preparing a round here, there was no problem and everything was tested very thoroughly; dunno if it's changed somewhat, since I haven't been competing lately.
We can try to reduce the number of incidents by making sure that the staff of codeforces googles the problem name and problem statements and make sure that the problem isn't taken form somewhere else.
Я один думаю что альберт тупой?
По-моему, у Вас нет возможности думать вообще.
к соревнованиям по шахматной композиции не придумывают новые задачи а берут малоизвестные старые
У нас соревнования по спортивному программированию, а не по шахматной композиции
div2 D isn't a junk problem. it's math. oh right man,I know some people don't know about Goldbach's conjecture but you mean CF can only have questions that you know about? don't joke,bro.
PS: I remembered that there was several question in CF,using math theories I never used,like how many primes < n are there,n<=1e11.that can be a question ,so why this can't? by the way,I agree the difficulty of D is little low.I think it can be a div2C,but for div2D,it's a little easy.