Привет, Codeforces!
13 ноября 2015 года в 18:00 MSK состоится первый учебный раунд Educational Codeforces Round #1 для участников из первого и второго дивизионов.
Учебные раунды Codefores — это новый формат соревнований основной целью, которого является помощь в развитии у участников базовых (и не только) навыков и знаний, которые необходимы при решении олимпиадных задач по программированию. В учебных раундах вы встретите не только старые добрые идеи и алгоритмы, которые многие знают, но также и некоторые расширенные темы, которые неизвестны многим участникам, в том числе и из первого дивизиона. Сложность задач будет сравнима с обычными раундами для участников из второго дивизиона, хотя многое может пригодиться и участникам из первого дивизиона. На мой взгляд первый раунд получился несколько проще того на что мы ориентировались.
Учебные раунды будут нерейтинговыми (мы продолжаем обсуждать этот вопрос). Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест. Подробнее об учебных раундах написано здесь.
Подготовкой учебных раундов занимаюсь я, Эдвард Давтян из команды Saratov SU Daemons. Идеи задач были придуманы совместно с MikeMirzayanov. Спасибо моему сокоманднику danilka.pro за тестирование и вычитывание условий и MikeMirzayanov за системы Codeforces, Polygon и идею учебных раундов.
На сегодняшнем раунде вам будет предложено пять задач. Надеюсь они вам понравятся. Если же они вам покажутся простыми приходите на второй учебный раунд там будет посложнее.
Good luck and have fun!
UPD: Первая часть раунда закончилась. Напоминаю, что результаты не являются окончательными и вы можете взламывать любые решения в течении суток.
UPD2: Пожалуйста не используйте недетерменированные генераторы. Например не стоит писать в языке С++ srand(time(NULL)) и потом использовать функцию rand(). Ваш генератор должен всегда генерировать один и тот же тест.
HAHA Edvard is wrote blog,but his blog till +1:)
This is what happens when people use a bad translator. or smoke too much pot.
Added problem F to the problemset. Now the contest will be interesting for nearly all Div 1 participants too. Let's have fun!
====
Добавил в контест задачу F — теперь даже Div 1 участникам будет интересно. Готовы?
Can we also hack during the contest after locking a problem?
No, only after the contest finished.
Are there any penalty for wrong hacks, and bonus for correct ones?
will there be rooms in contest ? i mean after contest we can hack anyone ?!?!?!
Only +x/-y in standings.
it seems even +x/-y not appearing
It will be round with ACM ICPC rules, so you can't lock problem.
Please don't delay it today. I have a tight schedule today. Please!
so memes were there 5 years ago as well!
yes
How to solve E with DP?
Screw hacking. Discuss solutions. Because of 24 hrs hacking, we can't even discuss solutions? -_-
Its ok. I will solve E on my own, because the test cases are also visible.
dp[i][j][k] = minimum cost to eat k squares of some i * j chocolate bar.
AAHHHH!!!! 2 idiotic errors ;_; . Codeforces makes me cry a lot.
There is a typo ... are (and would) be ... it should be ... are (and would be) ...
Damn, I wish this contest was a rated one :3
It would not be like that if it was rated :)
Again
what is unexpected verdict
Successful hacking attempt!
Now try to hack 14233270!ch_egor got it!Try 14242942.alexey.shchepin got it. Those were interesting puzzles — would make an okay problem I guess.I guess the real impossible one would be the first one with a bigger input. Less brute force would work probably. Any other ideas?
Sorry, but I don't understand what are you doing. Can you explain it?
I originally thought there would be hacking during the round, and knew I wanted to try hacking a in-contest solution afterwards. The reasonable solution would be to submit in the last second, but I had class and could only get only at small times.
I wanted to submit something that was hackable, but no one else would really be able to hack. The way I did this was by hashing the input, and if the hash is equal to a certain predefined value, the solution fails. For example this solution fails on "thisisahacktest".
It didn't end up mattering since there was no contest hacking, but it was fun.
you hacked your own solution :p that doesnt make any sense :/
But your handle makes perfect sense ;)
Easy. I made it with binary search.
I noticed. Nice job! Just random tries until it worked? (fix all but last couple)
Try this one: 14242942. Hopefully more constrained. :)
You know, that your MOD is 1016 + 60, not 1016 + 61?
Oh what. I saw before on CF that it worked to do it that way. I guess not above 1e9. Okay that's a useful find. x.x
Anyway probably doesn't make it much easier here.
It's not allowed to hack not the latest submission for the problem. Anyway, here is your hack.
Nice job! That's like the same as mine.
Maybe you just make them all the same and express the difference in base 3 I guess.
Okay that was fun; I'm done now :P
does unsuccessful hack reduce point????
no
No.
i am getting unexpected verdict over and over again
Fixed now.
I wonder why it takes the first accepted submission's time as penalty when you have more than one accepted submissions :O
А можно увидеть кто сколько взломов сделал?
Две одинаковых посылки: 14239039 и 14238862
При попытке взлома этих посылок обнаружил для себя интересную вещь. Тест http://ideone.com/7jFiGf в "запуске" работает 2427 мс, а при попытке взломать 858 мс. В связи с чем возникает вопрос: как узнать, сколько будет работать код при системном тестировании?
Вероятно, ты запустил не с тем компилятором, нужно выбрать MS C++ в запуске.
Да, ты прав, мой недосмотр. Спасибо.
The checker is evil. Check out the smileys.
Why is the source limit only 256 KB? I wanted to test a case for problem D, where n=1000,m=1000, and k=1. But, when I input my 1000*1000 grid, the file becomes 956 KB. Anything I can do to fit the memory?
You can submit code that will generate your test to standard output.
Thank you.
почему-то страница со взломом не грузится, точнее код не грузится. приходиться ломать с планшета. браузер — mozilla (linux)
Спасибо, буду смотреть.
I think all that solutions for well-known problems stuff is good but the "24 hours hacking" is just a waste of time.
Liked this round very much.
E was nice w.r.t the way in which DP table had to be filled :D
Are we allowed to discuss the problems? I am really interested in problem C
find every vectors angle with X axis and sort them and get the minimum value of distance(i , (i+1)% n)
our home;
your home;
Nice ads bro.
What is atan2 in c++ ?!
i used atan! it was hard because of checking some conditions! is atan2 easier?
THANKS!
atan returns a result in [-pi/2,+pi/2] while atan2 gives in [-pi,+pi]. You cannot determine the exact quadrant in atan. For example; given p1(1,0), p2(-1,0), atan gives 0 for both p1 and p2. You need to do extra work to see that they are not the same vectors. But atan2 gives 0 for p1 and PI for p2 which is what we are exactly looking for.
Why the resubmission after hack is not tested on the hack input?! I hacked the same person using the same case twice xD
I think, the system doesn't test the successful hacks because all of them will be added to the main tests and will be retested after the hacking phase. xD
When showing the scoreboard with Div.2 only participants, It shows only users with 1700- rating only.
Looks like it is still working with old limit for div2 before colors revolution.
I'll fix it soon. Thanks.
Можно показывать взломанные попытки другим цветом?(или просто добавить bold)
Wow, really learnt a lot from this round, especially problems E and F. Please keep more of these rounds in future. Very nice initiative :D
The checker for problem F seems incorrect. It is saying this case:
is 4.00, but manually drawing it out gives me 3.12. Can you double check your solution against this case?
Firstly, we cross LINE with polygon not SEGMENT.
So answer is 4 : 8-6 inside poly, 6-5 and 4-3 along side.
что значит "Неизвестный вердикт" при взломе?
Скажи номер взлома? Или уже нормально?
178630, 178629 и 178619. Сейчас на всех стоит "Игнорирован" (как я понял, из-за того, что до меня взломали)
Да так и есть решение уже взломано, поэтому твои взломы проигнорированы.
У меня тоже на 3 разных тестах неизвестный вердикт. Номера взломов 179603, 179610, 179614.
I am Curious about to ask you Guyz that " Will All the Submissions be Rejudged after adding the Hack Cases after 24 hours Hacking Phase . Let me Know .
Thanks in Advance .
Yes they will be rejudged with old tests + hacks.
i am got unexpected verdict when i hack problem F using n = 700, m = 100.
Give me please the hack id.
OK now! thx
Successfully challenged myself :) :(
I am a Div 2 participant but why isn't my handle shown on the Div 2 Standings?
Standings by divisions is not working correct. It will be fixed soon.
Problem C
Hard work, but finally I did it :|
i have the same problem (WA on test 116 ). i didn't understand why!? can u help me :D submission id 30388279
Hello Edvard and MikeMirzayanov . I love the idea of educational rounds. I have a request. I am very bad at finding corner cases, and debugging. Can we have an educational round where the focus is on corner cases and debugging. If we have such a round in rated contest, I'll be scared to take part, and I don't like missing rounds. Besides, losing ratings because of one missed test case hurts real bad. If I practice such problems, then its not the same as solving in an actual contest. So, I request, that you prepare a round focussed on problems with lots of scope for Wrong Answer because of test cases. It will help me improve my debugging skills, because some times, I make silly errors, but give up on my solution thinking something's wrong with my approach, and I need to come out of that mindset. When I face this problem in practice, I procrastinate thinking I'll debug it later. As a result, if I code something in 15 minutes, I take 1.5hrs+ just to debug silly errors. I need to practice in contest environment and virtual contests are not the same. So, Please! Also, maybe 24hrs for hacks is maybe too much... but that's a secondary concern to me. :)
Thank you and have a wonderful day!
I think it may be better if you can practice problems where there are a lot of hacks in virtual contests or mushups with your friends, which will make it much more interesting and motivational.Although I agree with your idea someway, frankly speaking, it’s hard for the organizers to meet the minority’s demond.
But I can still see the test cases, and virtual contests are not as serious as real contests. This makes all the difference. I can sure, get all cases covered after 20 attempts and a bit of peeking at the test cases, but that is what I don't want to do, because it doesn't help at all during real contests. Besides, I am a lone coder, my friends not interested :(
EDIT: If you don't make the whole contest case handling, then make the first three such, and the last two so hard, that I can't solve it :D . That way, I will be forced to try the first three.
These are educational contests. Please help me learn the art of debugging :)
and now the time when hackers are more scary than system tests became ....
I was wrong(
Почему все контесты не делать такими? Кому будет неинтересно, пусть не решает. Но тут хотя бы прочитал задачу и знаешь, что с ней делать. Т.е. контест проверяет умение кодить, а не умение придумывать идеи. Так отлично! Раньше так всегда и было! Почему теперь у нас везде (в том числе и на 1/4, 1/2 финала АСМ) задачи пошли на ИДЕИ, ну ёпрст... где обычные контесты на технику, как было раньше?
Получается уже не контесты по ПРОГРАММИРОВАНИЮ, а контесты по ИДЕЕПРИДУМЫВАНИЮ. А это бред, извините уж.
P.S. Вот на своем примере говорю — 2 раза проходил в финал ACM-ICPС (2009 г. и 2011 г.), но при этом оба раза процентов 85 задач на 1/4 и на 1/2 были исключительно на технику, там не надо было ломать голову над ИДЕЯМИ, там надо было накодить и всё. Так у меня вопрос — какого фига мы уходим от программирования в идеи?
Может, потому что умение думать полезнее умения программировать?
Как показывает практика, без соответствующих навыков написания правильно работающего и надежного кода, у нас в ИТ компаниях нельзя разрабатывать серьезный и важный проект. И ты понимаешь в чем фишка, вот приходишь ты на работу, вокруг куча умных ребят, которые могут, как ты говоришь, "думать", открываешь код, а там идет что-то типо того:
... doubla a,b; ... if (a == b) { } ...
После этого начинаешь объяснять им как сравниваются вещественные числа, что так делать нельзя и т.д. А откуда берутся навыки защищенного и правильного программирования? Из решения кучиииииищи чисто технических задач. А где набраться этого опыта, если сейчас решение задачи в первую очередь из придумывания идеи берется, а без идеи и неча садиться писать задачу?
При чем здесь вообще IT-компании и работа? Я слышал, на олимпиадах надо олимпиадные задачи решать, а не крупные проекты проектировать. А если работодатель принимает на работу того, кто не умеет писать работающий и надежный код, здесь что, олимпиады виноваты?
Хех, на олимпиадах вполне много техники бывает. На серьёзной олимпиаде никто же не будет делать задачу, где надо исключительно что-то придумать, а потом написать решение в две строчки. Олимпиады уже давно стали объединением умения думать, знания алгоритмов и техники написания кода. Часто встречается умение оптимизировать, люди, которые умеют писать хороший и простой код намного чаще добиваются успехов.
Технике программирования может научится любой, а вот думать, увы, способны не все. Олимпиады ставят перед собой выявить способных и трудолюбивых людей.
))
Что-то прошлогоднюю открытую олимпиаду вспомнил.
I'm not sure if this has been discussed yet, but since this is an educational round, the editorial will be much more detailed while teaching us the concepts right?
По-моему, идея открытой 24-часовой фазы взломов настолько прекрасна, что ее было бы полезно внедрить в обычные рейтинговые раунды. Разумеется, за взломы в течение этой фазы баллы не давать и не снимать, но успешные взломы добавить в "Системные тесты — 2".
В некотором смысле для этого и делается. Обкатаем подход здесь.
For anyone wondering: Hacking E is pointless, testcase 4 enumerates all possible inputs.
Yes you are right :-)
Как изменится мое штрафное время, если мое решение взломали?
Уменьшится. У вас исчезнет решенная задача, штраф теперь за нее вообще не будет учитываться.
Будет ли открыто дорешивание этого раунда? И если да, то будут ли решения, сдаваемые в дорешку, также тестироваться на взломах, совершённых за эти 24 часа?
А разве дорешка не открыта? Перетестируем все решения по этому контесту и все успешные взломы будут добавлены в официальный набор тестов.
А взломы дорешивания учитываются? Дорешивание будет перетестировано на официальном наборе тестов?
Да, добавляем все успешные взломы, перетестируем все решения.
Все-все. Просто различных значительно меньше.
Will the educational contest be rated?
No. Quote of the original post:
"The round will be unrated for all users and it will be held with extented ACM ICPC rules. "
Alright,thanks!
Тесты на С реально оказались неполными, судя по тому, сколько было успешных взломов по ней. Многие, наверное, заметили, как в несколько раз упало количество верных решений по этой задаче (было 600, по моему, а осталось лишь 27), а решивших 5 задач осталось всего-то около 14 человек. Одна из проблем многих участников — надо было учесть один случай и добавить в конец массива с углами угол
min_angle + 2 * PI, где min_angle обозначает минимальный угол. Контр-тест:Этот тест и был моим взломом (я им взломал 5 человек, мог бы больше, если бы больше потратил времени :-) ). Интересно, какие взломы применяли другие участники?
UPD Кстати, я обнаружил свой взлом в списке тестов. Это тест №61 :-)
Серьезно? А то, что решение с double не заходит по точности, вас не смущает? Вот один из трудных тестов:
разница между углами
Umm, both mine and Jury's answers are the same. Why does the code fail at #119?
They are not the same: the difference according to wolfram alpha
Okay, I didn't verify with wolfram;I had taken a look at the Checker Log. Thanks!
#define double long doubleAccepted. :/
any idea why so many codes including mine fails on testcase 119 for C?
That moment when your solution is 2ms away from time-limit :D
Was problem C so difficult to get right because it required to use long double? Changed mine solution from double to long double and got AC: http://mirror.codeforces.com/contest/598/submission/14258763
Can somebody explain what is wrong with #127 testcase ?
Two angles different by 2e-17 radians which is much smaller than double precision.
Edvard Is there an editorial for this round ?
Please share editorial for problem F.
Hi. Where I can find the tutorial for this educational round ?
Hi. Where I can find the tutorial for this educational round ??
can any one plz tell me how to solve problem E in less than O(n * m * k * k * (n+m)) time
Essentially, you can remove one
kfactor by observing that, when you make a cut horizontally or vertically, it is always less costly to use one of the portions in full if possible, than further cutting both portions. Hence, now instead of looping over how much of thekto distribute into the two portions, you take the best of two options.