Друзья, всем привет!
Буквально через пару часов состоится очередное соревнование - Codeforces Round 101 для участников Div. 2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Полина Бондаренко (Polichka) и Геральд Агапов (Gerald). Как всегда с нами были Артем Рахов (RAD), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).
Немного об авторах: все мы учимся в Саратовском Государственном Университете на факультете Компьютерных Наук и Информационных Технологий на 4-ом курсе. Сейчас в свободное от соревнований и задач время сдаем зимнюю сессию :) Я составляю 1/3 от команды Saratov SU#2, а Гера с Полиной - 2/3 от Saratov SU#1. Мы бы хотели, чтобы наши раунды стали доброй традицией на Codeforces, и скоро вы вновь увидели нас в числе авторов.
Мы надеемся, что сегодняшние задачи понравятся всем участникам, и каждый займет заслуженное высокое место в итоговой таблице. Сегодня Вы будете помогать Деду Морозу, Снегурочке, Васе и другим персонажам. Все совпадения с реальными людьми случайны :)
Баллы по задачам сегодня распределены следующим образом: 500-1000-2000-2000-2500
UPD: Вы уже можете прочитать разбор задач
UPD: Спасибо всем за участие! Раунд выдался достаточно сложным, только один человек среди всех участников (включая Div. 1) решил все предложенные задачи - это akim239. С чем мы его и поздравляем!!
UPD: поздравляем Top-10 участников в конкурсе:
1. shentianxiao
2. unknown79
3. frp
4. BelleBrezing
5. pokorski
6. hex539
7. not
8. Ilya_MSU
10. ggbuaa
"обычно", не значит "всегда", Учите теорию вероятностей :-)
Не пора ли опубликовать данный пост на главной странице?
UPD. Хотелось бы узнать разбалловку задач.
Почему я в Праге!? Опять я пропускаю контест! А во всем виноваты временные пояса...
Понравилась задача D. Это должен был быть ответ на оригинальный пост.
я один как лох битый час в задаче B думал, что поле ограничено?
вечно не читаю условия нормально
И пять человек из топ20 - серые (по крайней мере до системного тестирования). Я-то контест, конечно, слил, но все равно неприятно.
Третий пример:
Камень летит параллельно оси Y, минует 3 строки, после чего успешно падает на квадрат с номером 5 (критерием успешности, как указано в задаче, считается нахождение камня строго внутри квадрата, не касаясь его рамок). Таким образом, ответ: 5.
Четвёртый пример:
Камень опять летит параллельно оси Y, минует 2 строки, падает ровно на границу квадратов 3 и 4, таким образом не давая нам разрешения утверждать, что попал в квадрат (по условию задачи). Следовательно, ответ: -1, как и во всех случаях, когда камень не попал в квадрат.
Так где ошибка в примерах-то?
можете еще раз объяснит 4 пример: A=3 X=0 Y=7.По условию классики представлены являются квадратами тогда должен быть, если камень лежит на границе и X=0, остаток от деления Y на A равен 0.Объясните пожалуйста в чем я не прав!)
Я понял прошу прощения)
(именно так в условии написано)
Зачем такие сильные претесты во второй задаче?
по ходу, результаты контеста были сфальсифицированы
UPD ура, ЕдРо исключили из избирательных списков!
да нет, ЕдРо в списках, сейчас под номером 16
я надеюсь хоть здесь оно не победит
После системного тестирования узнаем =)
UPD Ну в общем я дурак :D
че то какой то сложный раунд
Ничего
Голод обостряет чувства, а сытость - притупляет. Возможно большое количество тренировок и соревнований притупили в вас азарт. Может стоит на время совсем перестать программировать, и заняться чем-то отвлеченным? Вступить в кружек любителей фиалок, попереводить бабушек через дороги, на добровольных началах начать разгребать навозные кучи в свободное от работы время, изучать звезды, или по кабанам пострелять...
Если не говорить о проблемах, можно подумать что всё нормально...
Thank you
Или мне мозгов не хватает или....? НО Я НЕ МОГУ ПОНЯТЬ КАК ПОЛУЧИЛСЯ ЭТО РЕЗУЛЬТАТ ХОТЬ УБЕЙ. Так, что эта олимпиада даже очень хоршая по пониманию условий. Кому интересно почитайте.
Вот именно. Ответ [1,5,4,2,3] не получается ни как.
And if you want to hack them, you need to understand their codes totally.
code "[ [ submission:1021473 ] ]" without space.
3 3
1 2 S
1 2 M
2 3 S
After sorting:
First, let h1 = n (or what number you like as long as it is not less than n).
At step i, assign n - ai to hi and decrease hj by 1 if hj ≤ hi (obviously, these changes do not affect previous order). Therefore, after step i, we can maintain a list of numbers from n - i + 1 to n.
can you tell why your solution works ? idea behind it.
Now, instead of choosing values, let's think about choosing ranks for these elements (from 1 to n, 1 is the biggest). Then, we can easily choose value for an element if we know its rank.
First, there's only 1 element, of course its rank is 1.
With element i, we know it must be smaller than ai elements, so its rank is ai+1. Inserting this element into the list we created so far will increase the ranks of elements whose current ranks are greater than ai.
For ex: let the a[] after sorting is {0,1,1,2,2,3}
Array rank[] after each step (bold numbers are whose ranks are increased after each step)
Step 0: 1
Step 1: 1,2
Step 2: 1,3,2
Step 3: 1,4,2,3
Step 4: 1,5,2,4,3
Step 5: 1,6,2,5,3,4
count differences between these two codes!
http://www.codeforces.com/contest/141/submission/1024571
http://www.codeforces.com/contest/141/submission/1022993
Codeforces was so slow today and I think your code deserves to be rejudged.
I think the reason is judging a lot of submissions at the same time in system testing might cause a little difference in execution time (1920ms is pretty close to time limit).
the order of my code is n^2logn which is should pass when n = 3,000. u r right it is very close to 2 secs, but my code passes in less than 2 secs.
Process time is not a constant on any operation system, but it could vary a little. Typically 3-10% is acceptable accuracy. In particular on this all author solutions are 2-3 times faster than a time limit. Actually each contest we have some solutions which work around a time limit. Some of them pass system tests, some of them not. But anyway, writing such solution is a risk, because you can't get will it pass tests or not.
We do not rejudge such solutions, it would be unfair to other participants. We apologize for the inconvenience.
can you please tell us how you get such number of operations? what if we replace set with sort? the number of operations will be the same? I think you just have not strong enough test data. Codeforces servers are very fast as i know.
upd: with sort your program works only 340 ms, but it is still O(n^2 * log(n)). The constant factor is very important. BTW dont't you forget about N^2/2 calls of "operator new" when you use set? There is more optimal - O(n^2) solution, so there is no any problem.
as I know that the set implementation in the c++ is a red-black tree, which takes log(n) in the insertion. so my code is O(N^2Log(N)) and N = 30000, So N^2Log(N) = 3000^2Log(3000) = 31,294,091.292476962.
There's an even more optimal O(N) solution too.
Спасибо за интересные задачи!