По многочисленным просьбам, делаем отдельный тред для объявления\обсуждения очередного раунда Алгоритма, который пройдет 30 мая в 05:00 (UTC +3). Раунд пройдет по системе TCM/Time и продлится 100 минут.
Пока ждете начала раунда можно потренироваться решая задачи предыдущих соревнований.
Не пропустите!
Обсуждение квалификационного и первого отборочного раунда.
UPD Третий отборочный раунд начнется по расписанию 6 июня в 13:00 и продлится 100 минут.
Время и дата раунда 2.2 уточняется, следите за обновлениями в расписании
I understand that you wanted to make Yandex available for people all around the world, but since score from eliminations is summed and vast majority of people competing are from Europe and Asia (mainly Russia) then it's just sadism to schedule round on 4 AM :P (5AM for Russia). I guess that moving it 4 hours forward or 4 hours backward will make it much more available to many people and it won't make a significant difference for people which live in timezones where this hour is comfortable.
Nowadays, following TopCoder usually brings nothing good ( ͡° ͜ʖ ͡°)
Sadism is part of Russian culture :)
Indeed. Especially when you have "Internal Server Error" instead of the contest...
5AM in Moscow it's noon in Vladivostok.
Or 3AM in Dublin. Just no :) Sorry for top participants who will have to participate in this absurd.
Well, some top participants don't have to anymore :)
OK, you got me there :). Though I know that China despite its size is in one timezone :P.
By the way, are there many top competitive programmers in Russia outside bigger cities in west like Saint Petersburg, Moscow or Saratov?
Novosibirsk (UTC+06:00, CF) is the third most populous city in Russia.
Internal Server Error
And why i dont wonder why i waked up?
Internal Server Error
Is it really so difficult to handle 2,000 people online?
Видать, организаторы умнее меня и в 5 утра спят :)
В добрых традициях Yandex — с первого раза не получилось )
codechef working smooth .. yandex site down .. parallel universe!
and UVa is down from yesterday !!! why ???
I don't know why but, it's a pretty regular thing for UVa.
Ok, guys. Let's go back to sleep.
Internal Server Error ) 5 am is very nice time for jury :)
Не спишь тут до 5 утра, и такое :)
может жюри продлят контест на 10-15 минут из-за недоступности задач?
сначала надо сервер поднять)
Он поднимается, иногда, но задачи не доступны.
Это если они будут доступны через 10 минут...
How to solve "Internal server error" problem (Spoilers):
Reduce it to external server error and then it is dynamic programming on servers
Can juri just paste problem statements here?
May be they will decide to change date of round, there is no reason to spoiler problems.
Yeah, and have us PM them our solutions.
You probably shouldn't (unfair advantage to ppl who don't visit CF frequently), but you probably can (as in: it probably won't be removed immediately). Mathematical answer! :D
Bad solution.
Many have read problem statements..
Several people managed to submit their solutions and got OK for them.
I think we have to sleep :(
I recommend open an incognito window/cleaning cookies for those getting ISE.
This didn't work (at least for me).
doesn't help
Doesn't help.
P.S. Post-mortem would be highly appreciated.
Maybe we should also restart PC/reinstall Windows?
Definitely. Also maybe restart our routers?
But if you have Windows, the PC restarts automatically :D
Doesn't help
Now it is saying "Problemset is not available" and "Submit form is not available now"
Doesn't help
It seems that some people have already seen some problems statements...
Yes, I already coded my solution for A, but can't submit. :(
Me too. :(
"The only thing that limits her is that she is unable to cover a height difference of more than m in a single step". Coundn't understand that part, because max(H_i) <= m, so we can go from i to j for any arbitrary i, j?
I suggest not to discuss now.
Yes, I've seen A
Come on!
It has been 20 minutes. Will you postpone it or what?
Are you waiting for gaining more hate of contestants who wake up in the middle of the night?
"Населена роботами."
Am I need to register for this contest? I have participate in Round 1?
As far as I know, you don't need to register again.
Ну сообщите хоть, что анрейт, чтобы я со спокойной душой ушёл спать
А то точно сейчас хочется цитировать nk.karpov "Sadism is part of Russian culture :)"
А мне уже Лида сказала, что я могу идти спать, часа пол назад.
Its 4:24 AM in the morning here, i slept only 2 hours and woke to participate this contest and now its Internal Server Error, give us some update lperovskaya :P
You should go back to sleep, you'll only have an unfair disadvantage, since some people have seen the problem statements.
At least you're not in a bus with laptop battery charged barely enough for the contest in the original time frame (okay, even less than that).
Ну это нормально вообще? Я встал в 4:30 утра перед GCJ Round 2 ради этого!?
Единственная страница, которая у меня иногда открывается, это таблица результатов. Вполне себе садизм, да.
А сабмиты там есть? :)
Ага, я видел, что 37 человек что-то отправили
я пытался что-то отправить, но получил ISE...
есть даже OK
I thought previously that Bayan did really bad...but here you go...
Codechef is more stable than Yandex, what a time to be alive!
Может уважаемые организаторы уже скажут что-нибудь хорошее, например, что можно с чистой совестью идти спать, а не нажимать F5.
Странно, задачи висят в очереди, одна тестируется уже десяток минут, другая даже не начала проверяться.
Очень странно =)
У меня задача C загрузилась...
А D у вас нету? :). А то её сдают XD
https://contest.yandex.ru/algorithm2015/contest/1240/problems/D/
Была, но я обновил страницу, чтобы сдать её) Сейчас висит Internal Server Error. -_-
Если что у меня есть A
(http://picpaste.com/pics/Screenshot_from_2015-05-30_05_26_07-4higepnx.1432953331.png)
А если серьезно, то для заданного k найти мин. d : 10 ^ k % d == 0
задача D
http://s01.geekpic.net/di-E8LXLM.png
Задача E
Ограничение времени 3 секунды
Ограничение памяти 256Mb
задача A:
дана лестница с N ступеньками высоты H[i]. За шаг мы можем подняться на высоту не больше M. Требуется посчитать число способов подняться на N-ю ступеньку по модулю 109 + 7
N ≤ 500000
задача Е
I wonder if somebody is working on that or they just sleep at this late night/early morning time :)
Yet another F5-style contest :(
Предлагаю отправлять решения по почте. Форма отправки не работает никогда.
I think this contest should be postponed.
I just get off from the bed to participate in this contest while my girlfriend is waiting for me and doubting of my motive in the midnight. Now, I don't understand should I wait for the contest or go back to my girlfriend.
I would prefer a girlfriend to this contest.
what is the problem???
I have exam an hour later and can't submit anything!!
PS: now I can not see problems either!
I have exam in 3 minutes(
Как все же отправить решения на задачу если у меня через раз либо Internal Server Error либо Список задач недоступен... ?
По 20 раз отправляют... Впрочем, они всё равно не тестируются.
30 май 2015, 05:15:24 696743 D GNU c++ 11 4.9 ожидание в открытую — — — — отчет
Иногда появляется тестирование, вместо ожидание))
Вопреки здравому смыслу, у меня при Internal Server Error посылка попадает в очередь...И там задумывается о вечном.
У меня попала через несколько минут. За это время я успел подумать "о, не попало" и послать еще раз. Что за хрень...
В итоге тестятся уже 2 решения, вместо одного((
либо "форма отправки решения недоступна"
I wonder why they don't use Codeforces as the contest platform when Yandex 2012 went well on Codeforces. Now it's like a joke.
I believe its "Not Invented Here" problem.
I guess Codeforces doesn't yet support whatever minor unimportant modifications they want (like the blind/open thing). Make Codeforces more versatile and you avoid these problems.
They should have canceled the contest after 20 minutes of this, tops. Very unprofessional. Not canceling it at all is even more disastrous (whoever f5s the hardest qualifies for onsite).
Maybe they tried to cancel it but got internal server error.
EDIT: After 1 hour, they finally got sane. Good night.
Ура, у меня открылись все задачи! Задача 1 — прочитать условия — успешно решена.
They said in QR such a problem won't happen in future rounds... hmmm
All problems: https://dl.dropboxusercontent.com/u/48283862/AYandex.pdf https://dl.dropboxusercontent.com/u/48283862/BYandex.pdf https://dl.dropboxusercontent.com/u/48283862/CYandex.pdf https://dl.dropboxusercontent.com/u/48283862/DYandex.pdf https://dl.dropboxusercontent.com/u/48283862/EYandex.pdf https://dl.dropboxusercontent.com/u/48283862/FYandex.pdf
what's the use of seeing the questions when the status of submission is waiting for like forever!
Хочу сказать добрые слова организаторам из Яндекс, но сейчас не могу ни одного вспомнить...
То чувство, когда написал задачу и отправил только через полчаса...
...а она ещё и не тестится.
то чувство, когда отправил на 15-ой минуте, вердикт выдало за 15 минут до конца))
Из-за технических проблем с серверами системы Яндекс.Контест результаты второго раунда НЕ будут учитываться в результатах отборочного этапа. Время и дата второго отборочного раунда будут сообщены дополнительно. Приносим свои извинения за доставленные неудобства.
Это всё из-за того, что я много порешал.
Technical issues
Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience
Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience
Wow! How lucky am I! I have to be in class during the contest, and can't participate. Now I have chance to join it again :D Hope the additional round won't be held on this time again :(
Idea of different times for contests was so that everybody could take at least one with convenient timing. So replacement round should be at the same time.
But we already wake up at 5AM. It's so scary :(
And I am just going to sleep — 23:00 here, tomorrow morning is GCJ Round 2. So nice timing for me ;) I will have to wake up early for one of the rounds too.
Please do not schedule it at 4 AM..... x_0
Lets be fair it's 4 AM not in all timezones and I think 3 rounds are trying to cover all timezones. =)
And the next round 2 is going to be scheduled on the same time?(
Хочу передать большой привет организаторам, и поставить для них песню.
я обычно редко ругаюсь публично, но на «Из-за технических проблем с серверами системы Яндекс.Контест результаты второго раунда НЕ будут учитываться в результатах отборочного этапа. Время и дата второго отборочного раунда будут сообщены дополнительно. Приносим свои извинения за доставленные неудобства» я могу спросить только что за хуйня блеадь, пиздец нахуй. Я конечно понимаю, место в таблице — не самая важная вещь в жизни, это не входит даже в десяток самых важных вещей, но блеадь, как-то печально сегодня. Збс ваще. спокойно порешал бы в удобное для меня время когда-нибудь потом.
Задачи очень интересные, показались отлично сбалансироваными по сложности и отлично подготовлеными. Хочется поблагодарить авторов контеста. очень грустно, что так получилось. Решение контеста доставило кучу положительных эмоций несмотря на возникшие технические проблемы.
А какой бы вы ответ хотели?
Прошу отметить, что я не попал в топ-30, не получил ни одного очка гран-при и даже не рассчитываю попасть хоть однажды в топ-30 в 2015 году для прохождения на следующий этап соревнования.
Как приемлимый вариант ответа — написать те же слова, но через 10-30 минут после начала раунда, а не под его конец.
Второй вариант — расширить количество проходящих по системе yeputons
tourist'у ничего не помешало сдать 6 задач, более чем десятку людей сдать 4 задачи, а мне сдать 2. И я сомневаюсь, что сдал бы больше, если б не было падений сервера.
Я согласен, что при проведении раунда возникли проблемы и предполагаю, что решение о неучитывании результатов раунда может быть лучшим решением, но это не отменяет моего отношения к ответу. Нет ответа, который я хочу, но конкретно эти слова в этот день вызвали неприятие в голове.
Я ж правильно надеюсь, что разбор второго раунда все таки будет не смотря на все возникшие ситуации?
I want to have some words of support for contest staff here. Bad things happens on all platforms. Some people here asked "Why not Codeforces?", but aren't they very same people who would gladly complain about Codeforces server being down only if Codeforces would be available. TopCoder rounds got cancelled once in a while, etc. I think people would be much more forgiving if it would not happen in this particular round that scheduled at early morning/night for Europe
Да ладно всем ругаться. Вот Гене же ничего не помешало все сдать в слепую )
Предлагаю немного снаркомании: берём две таблицы (с результатами этого раунда и без), берём по системе гран-при сколько надо, объединяем множества, получаем список финалистов.
How to solve D?!
If d = 2^p2 * 5^p5 then answer is max(p2, p5) Else impossible
Can you prove this solution?
Take a worst case like a number = VeryBigPrimeNumber * 10^k + b, where b = h * d, where h = const. VeryBigPrimeNumber >>>> d, so you need that d = 5^p1 * 2^p2, beacuse 10^k have only two prime divisors(2 and 5) and you need that 10^k mod d == 0. So, if(d != 5^p1 * 2^p2) then ans := -1, else ans := max(p1, p2)! You can found p1 and p2 in O(logN). (My Internet is SlowPoke :) )
Let's assume that the answer for some d is k. It means that we can decompose any integer n into a sum n = a × 10k + b and all we need to check divisibility of n by d is to look at b, i. e. a doesn't affect divisibility by d. Thus, 10k is divisible by d. If d = 2i * 5j the answer is max(i, j). Otherwise there is no such k, the answer is "impossible".
Как решить задачу A? Сам получаю TL код
Это за квадрат, а надо за n log n. Будем хранить динамику dp[i] — количество способов добраться до i-ой ступеньки и массив префиксных сумм этой динамики pre[i]. Для каждого i можно бинпоиском найти максимальный номер j, такой что для всех ступенек с номером меньше j нельзя попасть в i. Тогда dp[i]=pre[i]-pre[j-1]
И вместо бинпоиска поддерживать указатель на этот j, он будет двигаться только вверх. O(n)
О, действительно, всё намного проще. Спасибо.
Код можете показать?
http://pastebin.com/vz6gURmZ
Не очень понимаю решение -- можете объяснит по подробнее ? Зачем нам массив sumdp и dp&
Допустим, вы находитесь на i — ой ступеньке, вы знаете что вы можете попасть в нее со всех ступенек j, j + 1, j + 2 .. i — 1 , т.е. вам нужно знать сумму dp[x], j <= x < i : sumdp[i] — как раз сумма всех dp[x], 1 <= x <= i, тогда эта сумма равна dp[i] = sumdp[i — 1] — sumdp[j — 1], sumdp[i] = sumdp[i — 1] + dp[i]
How to solve E? I used such dp — f[len_prefix][wasC1][wasC2][wasC3][ost][flag] I fixed the three biggest numbers and then calculate dp. But it gets TLE. Who can help me? Code Link Here
I had even one more field in dp [did we have only zeroes before] but wasC1..C3 were compressed to one bitmask 0..7 and I got AC in 2.8s.
i had a dp with state[len][0..7][mod][flag][zero][C1][C2][C3]. It worked nearly in 198ms.
Before the round starts, this blog was +53. Now it's +16, and still decreasing. What a sad story :(( I think all contests should be encouraged, as all managers have tried their best.
I'm interested how to solve C without coding brute force for small numbers and looking for a pattern?
Read Wikipedia.
Cannot see anything about giveaway nim there (:
It is called misère in there
Excuse my necroposting. Can anyone help me find the error (http://pastebin.com/SmScmC1B) or share their C++ solution? Thanks!
Как и два года назад, задача C — адский боян. Причем из серии "если знаешь идею, пишется за минуту".
How to solve A ? I am getting a WA on test 5. Submission.
You need to compute the answer modulo 109 + 7.
Wouldn't it get TLE anyway? It's O(n2). What's a better solution?
two pointers maybe? (Lol i was typing "two painters" by mistake)
May not be the best solution, but you can solve using seg-tree with lazy propagation. For a height 'X' the number of ways is sum of number of ways of reaching height 'X-i' where 1<=i<=MaxJump . You can view this in a slightly different way that ways[X] will be added to ways[X+i] for i in the same range. Consider this as a range update (you can find the range indices using binary search) . Finally find the value of the last leaf of segtree, which is the answer.
If there is a solution better than O(n*logn), please do post your solution.
Code : http://ideone.com/gnBviP
two pointers :| http://paste.ubuntu.com/11446865/
I didn't understand solition, please explain in simple words. I know about two pointer
we know that dp[i] gets updated from dp[j] and dp[j+1] and ... dp[i-1] let's name this j az up[i] we know that if i < k -> up[i] <= up[k] so up[i-1] <= up[i] so we just need to move forward from up[i-1] to find the place that has less than m distance from i and that's that
Another linear solution:
Suppose dp[i] stores the number of ways to reach the ith step, and sum[i] stores sum of dp[0] to dp[i]. Also, you can store the cumulative sum of all the stairs uptil ith position in, say y[i]. now, you just need to search for lower_bound(y[i]-m) in the array y, and dp[i]=sum[i-1]-dp[lower_bound-1].
http://ideone.com/jnj6zv
Note: instead of calling lower_bound each time, you can preprocess the lower_bound indices in O(n) and calculate the dp and sum arrays in O(n).
Your solution is actually the same with Reyna's.
i only realized that after posting my comment. I hadn't refreshed my page since a few minutes :)
Кто сдал F, у вас O(nlogn)?
Я O(nlog2n) ногами упихал, но кажется, что это не то, чего хотели авторы.
У меня O(n log^2 n) на java без упихивания прошел
any updates on the new time of rescheduled round??
OK, so I will try to elaborate a bit more why organizing event at this hour is wrong and how it could be improved.
Firstly, we will use quantity argument. Look at the standings table. Keep in mind that this was middle of the night for Europe/West Asia. Scheduling hour of contest as such does good only for people from America (Northern and Southern). I just counted and there were about 14 people competing from those countries (USA, Argentina, Canada, Brazil, Dominicana and Cuba counted :P). And best of them was on 41st place. Does this really has any sense scheduling contest on that hour, making favor for that incredibly small amount of people and forcing about 200-300 not to sleep before 6/7AM? Moreover many people won't compete, so this competition kinda changes from "who is better programmer?" to "who can stay woken up longer?" and make results not reliable. Btw people competing at that hour have much smaller abilities, normally I would treat being unable to solve D as serious mental disability, but I managed to fail this either way :P (it was 5 AM >_>).
Considering people from America — isn't hour as one first contest was held at comfortable for them? If I'm not mistaken it's 1PM, so it superfine. 8PM in Poland/9PM in Moscow seems to be very good hour for people all around the world. Maybe for East Easia it is not that comfortable, so we can shift it 3 hours earlier. It is 9 AM in San Francisco and 1AM in Tokyo, so I think it's really fine. Given this — choosing hours 3 PM, 6PM, 9PM in Moscow would be the best option, because in that form everyone in whole world has at least 2 chances to compete in fine hours and amount of competitors such that they cannot compete 3 times not in the middle of night is much smaller than it is now.
winger lives in USA, and he is on the third place.
Возможно это уже спрашивали, но Раунд 2.2 будет после 3 — го или же нет?