Добро пожаловать на Алгоритм-2014 — открытый чемпионат Яндекса по программированию с оригинальными правилами, подарками, денежными призами и финалом в Берлине.
Если вы хотите побороться с лучшими программистами мира за призовой фонд в 540 тысяч рублей, ещё не поздно зарегистрироваться на чемпионат.
Регистрация открыта до конца квалификационного раунда.
Разминочный раунд пройдёт 16 мая в 21:00 по московскому времени, квалификационный — 25 мая. Подробную информацию о сроках проведения вы найдёте в расписании чемпионата.
Вот как проходил финальный раунд в прошлом году.
Желаем удачи!
PS: чтобы зарегистрироваться, аккаунт на Яндексе должен быть полным -- воспользуйтесь ссылкой
Start time links are broken, as the links contain month=M.
Thank you very much for the note, fixed this.
Is the contest rated?
It's not a CodeForces contest at all.
In the registration page I saw the word "affiliation". What information I need to provide in this content?
I think it is the school/college/university/workplace you're in.
Я правильно понимаю, что решив одну задачу в Разминочном раунде, пропускаешь Квалификационный?
По крайней мере стрелочка нарисована: http://contest2.yandex.ru/algorithm2014/schedule/
"Разминочный раунд начнётся 16 мая в 21:00 и продлится 100 минут. Все участники стартуют и финишируют одновременно. Те из них, кто сдал хотя бы одну задачу, сразу попадают в отборочный этап."
Да, все верно, именно так. Однако если хотите, то вы можете принять участие и в разминочном и в квалификационном раунде
The contest will take place, here on CodeForces?
No, Yandex has their own platform. Follow the links.
Thanks.
In the registration page when I click on changing Date of Birth: It takes me to some page which is in completely different language(different from english) after which I am unable to proceed. Kindly look into this matter.
Why are you so stupid? Please click onto the Russian flag and change the language to English. BTW, your comment was posted into Russian version of CF.
Actions that you offered are not so obvious. Let's do not offend each other. Everybody can make mistake or do stupid things, it does not mean that this person is stupid.
When I click on edit button of date of birth of registration page, I am redirected to this page where I am not able to follow anything since the language is not in english. Kindly look into this.
При попытке зарегистриоваться необходимо ввести дату рождения. Пройдя по ссылке, чтобы ввести дату рождения (что уже забавно), я попадаю на страницу, где можно поменять только "Ваше имя" и "Фамилия". В итоге, зарегистрироваться не получается.
Спасибо за замечание.
Да, для того чтобы принять правила конкурса нужно сообщить возраст (несовершеннолетним, к сожалению, нельзя участвовать в финальном раунде). Чтобы зарегистрироваться нужно зайти на
https://passport.yandex.ru/passport?mode=light2full
и конвертировать аккаунт. Тогда все получится =)
Спасибо, получилось. Ох уж эти секретные ссылки :)
I have two questions for you:
What I need to do with your passport link? I have already registered an Yandex account and when I open your link, I only saw my personal information.
The contest rules said that: "Contestants submit their solutions into the contest system with the help of the software provided. Before submitting a solution, the contestant chooses the compiler that will be used by the contest system, which runs on Linux, to compile the solution." -> What is the required program? Where can I download it?
Thank you.
The passport link is necessary for the owners of light accounts (i.e. authorised using social networks). As soon as you are registered, there is no need to do anything with the passport link.
Rules refer to the contest environment as a provided software. You won't need to download or install anything, just use the online submission form. It should work well on Linux. =)
In the Registration form, there is a section which we must fill in ---->>> "Affiliation", I don't know what does it mean, can you help me?
already answered
As somebody said — some participant join to compete, other — to help with testing the server load. I am going to help with testing the server load at this competition :) At last RCC round help of people like me was invaluable :)
Link to the contest for those how is lazy as me
Успел словить Internal Server error. Ай-Ай Яндекс! :)
Ещё пару раз видел эту надпись ближе к концу — это уже было менее приятно :(
Всё — у меня лежит. Не скажу, что эти сильно повлияло на мои результаты, но уже минут пять обновляю страничку.
А только у меня иногда версия таблички старая за рандомную минуту показывается? То есть ф5, показывается табличка старая с рандомной минуты, ф5 и всё ок.
При обновлении Standings они периодически уходят назад во времени (при этом довольно существенно, минут на 30). Какой-то баг кеширования?..
Значит не только у меня :)
Да, такая проблема проявляется и у меня. Мы уже локализуем ошибку, спасибо большое за сообщение
У меня такое бывало во время SNWS, но буквально 3 или 4 раза суммарно за все контесты, а сегодня едва ли не на каждом втором обновлении.
А я последние 5 минут не могу отправить решение из-за ISE UPD: смог за 11 сек до конца
а я так и не смог отправить(
При попытке отправить решение на последней минуте: "Internal Server Error" после 30 сек задержки
UPD: особенно неприятен тот факт, что решение было правильное
Столкнулся с аналогичной проблемой, вследствие чего не смог отправить решение.
Конечно, понимаю, что данный раунд разминочный, но хотелось бы, чтобы в последующих раундах с отправкой решений во время контеста (в том числе и в конце) проблем не было.
Расскажите, как решать F?
Если встретил 1, то ее нужно объединить со следующим числом и все. Если встретил x > 1, то нужно разбить на 1 и x — 1 и все.
Коварный случай: 1 0 2
Тогда разложение эквивалентно 2 0 1 1
Но по условию второе не разрешается.
Так рассказать решение можно, если я решил и хочу убедиться, что у меня такое же решение. А я не решил. Можешь поподробнее рассказать, пожалуйста?
Ну я не знаю, там вроде формально записываешь первую дробь, вычитаешь ее из 1, приводишь в нужный вид на бумажке и все...
1/p + 1/q = 1 => q = p / (p — 1) = 1 + 1 / (p — 1)
Далее надо проверить, если данное в условии число — p и {a_n} — разложение для него, то если a_1 > 1, то разложение для q — {0, 1, a_1 — 1, a_2, ....}, иначе — {0, 1 + a_2, a_3, a_4, ...}
Можно с начала и чуть поподробнее? =)
Рассмотрим данную нам дробь — она имеет вид 1/p, где p — это какая-то цепная дробь. Нам надо разложить число 1/q, где 1/q+1/p=1. Отсюда следует, что q = p/(p-1) = 1+1/(p-1). Таким образом, из определения цепной дроби, получаем, что если a1 > 1, то 1/q = 1/(1 + 1/((a1 — 1) + 1/(a2 + 1/(a3+... Ну и надо правильно обработать случай, когда a1=1.
Many thanks to all participants! We know and already working on issues of old monitor content and the internal server errors in the beginning and at the very end of the contest. If you faced any other problems, please, report them to the http://feedback.yandex.com/contest/
Если послать задачу не туда(Е в А, например), а потом этот же код послать туда куда надо, система ругается, что вы уже посылали этот код.
У меня было ещё более странно — я (в последние минуты) заменил все int на long long, система меня тоже отругала, что я засылаю тоже самое решение. Может, конечно, система знала, что это не поможет, но я такого поведения не ожидал — побайтово код был другой. Неужели какая-то эвристика?
Как решать факториалы без длинки?
Две задачи сдавались методом "Зачем думать, если можно написать на джаве" :)
А какая ещё, кроме В?
Е. Там выходит что в 100! примерно 200 цифр, в третьей степени примерно 800, значит в сумме примерно 1000. Заходит за 120 мс
Точнее метод называется "долгой надо самый минимум, даже на плюсах пару строк". По поводу Е — можно предположить, что хранить последние несколько цифр будет вполне достаточно. Я проверять не стал)
Я еще долго думал что мне больше лень — писать на джаве или написать свою длинку :)
или выводишь первые 10 элементов для каждого k, видишь закономерность, пишешь 13 if'ов
А зачем там длинка? Кроме случая k = 0, нужны максимум две последние цифры.
Нет, максимум одна)
n = 3, k = 1: 1 + 1 + 2 + 6 = 10.
Да, вот поэтому она у меня и упала =(
Объясни начинающим, почему две?
Заметим, что факториалы, начиная с 10!, делятся на 100, поэтому, начиная с n = 10, последние две цифры меняться не будут. С меньшими n можно явно проверить, что все суммы не делятся на 100.
eatmore, спасибо — мы говорили про разные вещи, но в итоге я понял, где у меня была ошибка :)
А с этим вообще весело получилось: на контесте пробовал брать 30, и даже 36, цифр не заходило, попробовал 2 и все окей... И попробуй пойми в чем же баг... Может __int128 кривой?
Переполнение?
В факториалах я работал только с последним числом — но где-то всё равно не доглядел :( По идее при умножении на последнее число влияют только последние цифры сомножителей, поэтому все нули в конце и всё, что впереди можно отбрасывать на каждом шаге.
При сложении там получается немного — 9**3 = 729 * 100 = 72900.
Но что-то у меня не сработало.
Надеюсь 0! = 1 ? Пока не придумал, где ещё мог пролететь.
в условии сказано, что 0! = 1
Каждую степень факториала (слагаемое) представим в виде произведения простых делителей. Найдем максимальную степень десятки, на которую делятся все слагаемые и поделим на нее (достаточно смотреть на степени двойки и пятерки в слагаемом). Теперь есть слагаемые, которые не делятся на 10. Однако сумма все еще может. Поэтому просто считаем эту сумму по модулю 10^15. Выводим первую ненулевую цифру. На контесте получил WA31, в дорешке ОК через 3 минуты после конца.
достаточно смотреть на степени пятерки
А, ну да. Степень пятерки всегда меньше.
Я написал вычисление по модулю 109 и прогнал через все множество тестов. Везде получился ответ не 0, значит 9 последних цифр хватает. Заслал вслепую.
Достаточно решить два случая:
1) k = 0
2) n <= 4, k > 0
если n > 4, то ответ такой же, как и у n = 4.
Задача D какая-то хитрая? Там работает обычная Дейкстра с приоритетом сначала по сумме длины, потом по количеству ребер? Или Левит?
Работает обычная Дейкстра.
И обычный Форд-Беллман. Проделываем обязательно N - 1 итерацию и запоминаем, при каком i оптимальное расстояние до N по i рёбрам было минимальным в последний раз.
Написал и Дейкстру, и Левита, и Форда... Где может быть подвох, ВА 2? Там есть подвох?
У меня тоже не получилось — не прошёл тест 2, хотя минут 40 эту задачу "вылизывал", трейсил и по примерам прогонял. Даже условие раза три перечитывал.
тоже самое
Показали бы код, мы бы посмотрели...
Буду благодарен. Я сам ещё не разбирался, но буду. И в любом случае добью эту задачу. Так что посмотрите только если есть время.
Три комметария: 1) Этой мой второй контест на C++, до этого был только Python. Последний раз до этого C++ видел в 2001 и без STL. 2) Дейкстру на C++ ни разу не писал. 3) То что везде long long — это я в последнюю минуту пробовал на авось.
Буду рад комментариям по стилю/использованию типов данных. Спасибо!
http://pastebin.com/iKKRPBiF
По ссылке какой-то странный код: очередь должна быть с приоритетами, и каждую вершину нужно только один раз рассматривать...
Ну там не Дейкстра, а Форд-Беллман с очередью получился)
не спорю, должна быть с приоритетами. Отказался о приоритетов, когда ловил баги. Не помогло.
Я вообще, если честно, не понимаю, что происходит у Вас в коде. Я сомневаюсь в целесообразности использования мапа для хранения списков рёбер. Естественней смотрелся бы простой массив векторов.
Для Дейкстры Вам надо хранить множество ещё не финализированных вершин. Я не совсем понимаю, какое условие проверяется в 60 строчке. И ещё я не совсем понимаю, что за тройки чисел у Вас хранятся в очереди Queue и как эти значения связаны с N_length и N_numroads.
В целом, будь даже Ваш код правильным, он, на мой вкус слишком сложен. Вот, что сдалось у меня: http://pastebin.com/mjf0p8mT
То, что происходит в коде — это одна из модификаций SPFA. Хоть и написана не лучшим образом)
Авторский баг — в считывании, там цикл по n, а надо по m.
Если это исправить, то TL11. Если поменять типы на нормальные и немного соптимизировать код, то TL13 или TL14. Чтобы зашло — надо, обходить DFS'ом, а не BFS'ом, и не пихать в очередь лишнего. Когда поменял push_back на push_front и стал добавлять в очередь только те вершины, которые улучшаются, а не всех соседей сразу — АС за 0.45.
Спасибо большое за комментарии. Буду работать над собой. :)
Результат работы над собой:
http://pastebin.com/Dmkuj9xC
Теперь больше похоже на нормальный код? По тестам заходит, правда пробовал уже на Codeforces — 0.124.
Ещё раз спасибо за комментарии!
Дейкстру проще писать, потому что можно хранить рёбра в виде матрицы смежности.
Я подумал, что если сделать дейкстру по паре (длина, рёбра), то может быть плохой случай. Так что написал обычную дейкстру по длине, а потом шёл от последней вершины рекурсивно и делал переход к предыдущей, если
g[i][j] + d[i] == d[j]
. По каждой вершине пройдёмся один раз, если сделаем кэширование.Вот код без кэша:
А можно будет увидеть тесты?
И сколько будет открыто дорешивание?
2014 Яндекс.Алгоритм - Разминочный раунд
Can someone find the mistake in this code for A? I am puzzled :(
There are two:
1) rook can't attack through white king.
Test: a3 a5 a1. Right answer: normal. Your: check.
2) black can capture white rook.
Test a3 b1 a1. Right answer: check. Your: checkmate.
Thanks a lot, I realize my answer was far from correct and now, I feel stupid :P I guess this problem requires careful implementation, something which I suck at.
c1 a1 h1
a5 a1 a8
Can I participate in the qualification round If I did not write the warm-up round?
Yes, sure!
10x :)
:|:|:|:|
У кого-нибудь есть в B меньше чем 10 строк кода?
А у тебя решение на 10 строк?
http://pastie.org/9182703
Ужала свое решение до 9 строк, можно и еще ужать, но и так уже достаточно некрасиво :)
how to solve problem E that factorial??
For k = 0, answer will be the last non-zero digit the number n+1. Let d[n][k] is the answer. Then for n > 3 , d[n][k] = d[4][k].
Bruteforce in Python, just keep the last 10M digits for chosen reasonable M (feel free to use M = 10). No thinking required.
Actually M = 3 is enough :P
PS: I just noticed, you mentioned last 10M digits, you mean the last M digits :D
Yeah, last M digits. But the more you choose, the more confident you can be.
You can use BigInteger in java.
I don't have any clue why this code is giving wrong answer. Can anyone please find out the bug in it?
http://pastebin.com/jB6H3b7W
A small request to Yandex Algorithm organizers. It will be very helpful if you can provide the test cases or editorials. Thanks in advance.
For Problem A I am unable to find any errors with my code. Can anyone please find out the mistake in it?
http://pastebin.com/jB6H3b7W
A small request to Yandex organisers. Kindly provide the test cases or editorials for the problems. Thanks in advance.
try f2 h2 h5 upd: try f5 h2 h5
It's showing "Check".
Also if the just the white king is attacking black king at its current position and not the rook then what should be the answer "Check" or "Strange". I tried it both ways still it's giving wrong answer. Thanks for the test case but I think the code is giving right answer for this.
No, in this test answer is "Checkmate".
Thanks for pointing out the test case. I wasn't checking for the piece going off the board. my bad.
The answer is "Check" for this test case. But it helped me notice the stupid mistake I have been doing. Thanks.
Queen? King, no? If the kings are mutually attacking, then the position's Strange (it shouldn't be possible within chess rules!), wherever the rook is. The rules in the problem statement are listed in order of priority and make sense to anyone who knows the rules of chess.
Sorry for the typo there. Yaa got that. Sorry for such a naive question. Thanks.
try f5 h2 h5
I'd recommend you never, ever write code like this again. One little mistake while copy-pasting will throw all your work away. If the most primitive concept in the problem is the point, you most probably need a
pair<int, int>
or a struct with two fields. If you need to copy your code 8 times with small corrections, you most probably should think about looping over a constant array of 8 elements, rather than copy-pasting and adjusting indices by hand. (I'm trying to help, sorry if it sounds offensive.)@udalov Thanks for pointing it out. I will take care of it in future.
Doesn't sound offensive at all. I am open to all kind of suggestions.
Thanks again.
While this way eliminates the risk of missing just one element to rewrite, it has other risks. Sometimes, there are problems which do a lot of operations on one 2D array in each direction; this can be solved by rotating/flipping that array and only doing a lot of operations on another array, but you need to pay attention to the order in which you use the elements of that other array; the more complex the operations are, the harder this is, and it gets harder much faster than copy-pasting and naming your 16 variables differently, because it requires heavy thinking about every line of code (and you need to think in indices instead of words). It's easy to be off by 1 in some formula, and these mistakes are harder to find than copy-pasting ones (find and replace).
If the algorithm's doing something simple multiple times with small variations (or it's not too many times, it's not good to copy-paste. If it's something complex, it's debatable.
Archive of contest (test cases, statements, model solutions)
Following that link now, I got "nothing found" error. If you downloaded it,Can you upload it please?
Link on the site is correct.
Did B really have tests for large integer arithmetic? This seems totally unfair because solutions in Java will be like 3 times shorter than ones in C++, which is probably why such problems are avoided in other contests.
As a Python lover I can equally say that giving computation intensive problems with short TL is totally unfair, because same solution in C++ is 10 times faster. My point is that every language has its weak sides, even C++.
I don't see any rule limiting you from developing your own small class for working with BigIngeters. To have it just in case. To be honest this is what I am doing now :)
@zholnin: Isn't it required in every online contest to start from scratch and to not use any previous code?
Why do you think so?
ACM ICPC rules
But this is not ACM ICPC competition
NO, it isn't!
Дорешивание перестало работать — в выпадающем списке с языками пустота, соответственно решение больше отправить не получается. Конечно, тесты и решения выложены, но хотелось бы в том же интерфейсе всё делать, в котором проводятся соревнования.
Добавил в тренировки 2014 Яндекс.Алгоритм - Разминочный раунд. Конечно, слепые попытки учитываются как просто попытки в ACM-ICPC-режиме.
Ох уж мне эти собранные вручную архивы:
wrong answer expected '4', found '3'
.Еще мне кажется, что такие архивы должны содержать olymp.sty, а еще лучше готовые скрипты для сборки PDF-условий.
А еще задача C даже в английском интерфейсе имеет название "Окружности-2" (http://contest2.yandex.ru/algorithm2014/contest/502/problems/C/).
Что характерно, tex-файлик с условием содержит правильное название, что скорее всего говорит о каком-то копи-пейсте в при настройке.
Ссылка не кликабельна
Еще некруто, что не внесли клары в условия. Например, этот:
Еще мне кажется, что так себе идея показывать чисто русскоязычные клары в английском интерфейсе. Я всегда чувствую себя дискомфортно, когда в английском интерфейсе китайского сайта появляются иероглифы.Тем более здесь — участник может подумать, что это что-то важное (ведь сообщение от жюри), но написано почему-то кириллицей.
Те, которые с консолью, содержат в названии подстроку "_cc".
Проблема стандартизации поддержки нескольких форматов задачи в одном архиве (graders / file / console input-output, ioi / acm scoring), к сожалению, до сих пор не решена :( ... Есть идеи по этому поводу?
Can I participate in the qualification round if I didn't participate in the warm-up round?
Already answered... and the answer is also written in the rules page.
can someone explain to problem E on factorial. I see the solution but somewhat unable to get why for N > 4 , we take N = 4
Solve the small cases by hand and think about it :D
I am unable to open the yandex links. Does this happen only with me?
I am unable to open the yandex links. Does this happen only with me?
I can't find any working link for the contest, for hours. I guess the qualification round is running now, but I can't find a link for the contest.
http://contest2.yandex.com/algorithm2014/contest/503
It's available from first post at the main page of the competition: