Приглашаем вас в квалификационный раунд Яндекс.Алгоритма, который начнется 25 мая в полночь. Присоединиться к нему можно в течение 24 часов с момента начала. Квалификация продлится 100 минут.
Все участники, решившие в этом раунде хотя бы одну задачу, пройдут в отборочный этап соревнования.
Если вы уже прошли в отборочный этап из разминочного раунда, но хотите потренироваться -- добро пожаловать!
Удачи!
Квалификация началась! Успехов!
I have a question:
From the Rule, "If a problem is solved with a “blind” submission, the total penalty time is decreased by n seconds, where n = ((number_of_contestants_who_did_not_solve_this_problem) × (contest_length_in_seconds)) ÷ (total_number_of_contestants)."
Who will be counted as "number_of_contestants_who_did_not_solve_this_problem" and "total_number_of_contestants"? I wonder those who are eligible for the round but not participate in the round at all will be counted or not.
It includes all people who have made a submission (even get 0 point in the end).
You can confirm this by calculate on this standing.
thanks!
can someone explain how to solve the problems ?
I hope there are editorial after contest has ended
This webpage has a redirect loop :(
Try opening the page in an incognito window if you r using google chrome
thanks Shawkat
Разбросанные по всему списку компиляторы одного языка и
OpenJDK Java ...— это дикий ужас. Вам точно не хватает сколько-нибудь годного фронтендщика...P.S. Жду дисквалификации (или отказа в приеме на стажировку?).
Да уж, самое забавное, что если зайти на страницу сабмитов со смартфона, то названия компиляторов не сокращаются.
И, что характерно, со смартфона не получается прокрутить список.
А на меня, по-моему, ополчились обиженные мной синезеленые. Т.к. проблема с юзабилити на самом деле имеет место быть...
Will the coming rounds be held and rated on Codeforces? I mean there was a previous round on CF in 2011...
Решить первую задачу с 6-ой попытки....встретимся на финале!
Не решил задачу F с пяти попыток, так что принимаю вызов! :)
Ещё не пофиксили багу, которая может немного сбивать с толку.
sadly I missed it :( :(
Actually, you have about 5 hours to start it
BIG Thanks I thought it's saturday not sunday ,Thanks again
Ah! it needs further registration, I thought codeforce handles are enough. Too bad!
Is there any way to see other participants solution after the contest?
Why cant we resubmit blind submissions?
Because it is no more blind. You have already been told that what you initially thought was incorrect, and you have been provided a chance to correct it.
Who told me?:D
What?
It does not say after the submission if it has passed the tests or not (only sample tests are checked).
What's the point of blind submission now?
Do you want to check that your submission passes the tests from the problem statement? That is something you can do manually.
while regular submissions are being tested immediately.
No and this is why the result of blind submission is useless.I think I didn't got you correctly. Were you asking why yo can resubmit blindly during the contest? I was thinking about upsolving due to some reason. If your question is about the contest then I think the reason is to add more drama, you should be sure about first time you submit it.
После того как все решил, в Положении участников часто показывается состояние на какой-нибудь рандомный момент времени (00:15, 00:36 и т.д.), а не конечные результаты.
Про это уже написали выше :).
In the final standings, the + indicates normal submission, while a tick indicates blind?
Yes.
Is there any editorial for the contest ??
Of course not, its not even over yet.
I don't understand, the qualification round is not finished ??
It's a "virtual" contest. You can start your participation in any moment between it's start and finish time. At the end, results of the participation of all participants will be merged and we will have final standings.
got it now, thank you :D
Contest already finished.
Actually, no. What's over is the time window when one can start a virtual contest. A participant can start at 23:59 MSK and still have 100 full minutes to compete.
The real end time is 01:40 MSK.
)
I put together a short editorial in case someone needs it: http://www.rivsoft.net/blog/yandex-algorithm-2014-qualification-round/
tourist solved all problems in 41 minutes! That is insane!!
They were mostly implementation problems, though.
Задача С
Помогите Юре, напишите программу, которая находит порядок листов в стопке, удовлетворяющий всем указанным условиям, либо выводит сообщение о том, что этого достигнуть нельзя.
Задача D
После того, как Юра сложил все бумаги в стопку (смотрите задачу C), он задумался: как же проверить, действительно ли каждый лист бумаги виден? Сходу он справиться с этим не смог, поэтому обратился к вам за помощью.
Какого черта, Юра!?
Ничего не знаю, меня подставили.
Как решать Е ?
Подотрезок с максимальной по модулю суммой. У элементов на четной позиции необходимо поменять знак.
Поменяем каждое второе число на противоположное. Теперь нас интересует максимальная по модулю сумма на подотрезке. Её можно найти так. Пусть
s[i]— сумма первыхiчисел. Тогда сумма на отрезке[l,r]равна|s[r] - s[l-1]|. А эта величина, очевидно, достигнет максимального значения, если мы найдём максимальное и минимальное изs[i]и вычтем одно из другого (неважно, кто из них справа, а кто слева, потому что сумма рассматривается по модулю).Damn, why no any reminding email :(!? I missed such a good contest, because I missed qualification round :(.
Did you participate in Warm Up round?
No, I didn't have time to (lot of work to studies) and since it was "Warm Up" I assumed that problems presumably won't be amusing. Were reminding e-mails sent to Warm Up participants only? If so, that isn't a very clever idea.
It is pity, because Warm Up round was also an opportunity to qualify for main rounds (in the same way as qualification round — by solving at least one problem).
Oh, I didn't know :P.
Ошибочно решал вместо С задачу, где условие не только на бумажки сверху, но и на бумажки снизу (т.е. у каждого листа должна быть точка, над которой и под которой нету других листов). Как такое делать?
Тогда от расположения ничего не зависит. Можно расположить любым образом, потом положить сверху ещё одну такую же стопку и решить задачу D.
Я что-то не понял перехода к задаче D:(
От взаимного расположения сверху/снизу тогда ничего не зависит, но вопрос в том, как крутить? Если есть, например, 2 листа со сторонами 3 5 и 4 6 — надо один из них повернуть, и все будет ок. Как узнать, какие поворачивать в общем случае?
Пусть А и В — длина и ширина первого листа. Пусть C и D — длина и ширина второго листа.
Тогда второй лист можно положить на первый, если (C < A or C < B or D < A or D < B).
Соответственно, очевидно, куда крутить.
Вы не поняли вопроса. Нам надо понять, какие из листов повернуть, а какие — нет.
А действительно, я об этом не подумал. Это резко усложняет задачу...
Пусть мы расположили их нужным образом. Тогда для каждых двух листов у одного из них больше высота, а у другого — ширина. То есть, все высоты (и все ширины) различны и если расположить листы по убыванию широт, получится возрастающая последовательность высот.
Давайте для начала расположим все листы так, чтобы они были "высокими" (
h[i] >= w[i]). Нам надо развернуть некоторые из них так, чтобы развёрнутые листы лежали правильно и оставшиеся — тоже правильно. То есть, если рассмотреть последовательность высот листов, расположенных по убыванию ширины, полученную последовательность высот надо разбить на две возрастающие подпоследовательности (причём так, что если две ширины равны, то соответствующие высоты обязательно попадают в разные подпоследовательности).Это можно сделать, например, так. Пусть мы разбивает последовательность
x[]на две возрастающие подпоследовательности. Давайте посчитаем динамикой величинуmin[k]. Что такоеmin[k]? Если разбить первые k числе последовательности на две возрастающие подпоследовательности, то одна из них будет оканчиваться наx[k]. Тогдаmin[k]— это минимальное число, на которое может оканчиваться вторая подпоследовательность. Тогдаmin[k+1]легко вычислить, знаяx[k],x[k + 1]иmin[k], с учётом того, что одно из них — максимальное число среди первыхk+1.В такой формулировке напоминает задачу F с Гран При Саратова: http://codeforces.me/blog/entry/10614#comment-159703 (оно же с тимуса: http://acm.timus.ru/problem.aspx?space=1&num=1743).
Спасибо. Да, это оно.
Запишу себе напоминание — наконец-то пересмотреть пропущенные этапы опенкапа в ближайшее время:)
Seriously, why no email reminder? I missed it too, it was a really good contest and I wanted to participate :( :(
I believe the statement of problem F was incorrect.
Currently the statement says: "The sequence starts with an opening round bracket “(”, ends with a closing round bracket “)” and holds only English letters (one or more) in between the brackets. Examples: (blush), (facepalm), (SmileSmileSmile)."
However, there was no "(one or more)" in the beginning of the contest. Without "(one or more)", I think "()" satisfies this condition (and I guess this is the reason of so many failures).
We considered to retest all failed on test 4 submissions before fix with "one or more" was added with understanding when () is a smiley. Retesting will be done soon.
Update: Retesting complete; all solutions failed on test 4 before statement fix were rejudged.
But anyway, i am not sure if there is no difference between "holds only English letters" and "does not contain any characters, other than English letters" (something like that must be used for set of English words + empty set). For the first version of statement more likely string must be non-empty
Thank you!
C# solution for F:
In java:
out.println(in.readLine().replaceAll("(\\([a-zA-Z]+\\)|[^a-zA-Z0-9 ()]\\))", "<S>$1</S>"));in perl:
s/(([a-zA-Z]+)|[^ a-zA-Z0-9()]))/<S>$1<\/S>/g, print while (<>)
What was the approach to solve problem E?
Change the sign of all elements in odd positions. Now you need to find the segment with the largest sum (in absolute value). If you calculate partial sums (from the start of the array to the current position), then the sum of any segment is the difference of two partial sums (corresponding to the segment's start and end). So all you need to do is go through the array once, keeping track of the current sum, and the minimum/maximum value of this sum so far.
А почему нельзя посмотреть решения участников? А то я больше получаса потратил на D, хотел посмотреть, почему другим участникам (некоторым) хватило 10 минут.
А сколько времени нужно писать ДО/корневую для поиска максимума на отрезке?
Хотя я бы тоже не отказался от возможности смотреть решения остальных участников.
№152-ФЗ, статья 7. Думаю, достаточная причина для того, чтобы не публиковать исходники участников.
Хм, но вот администрации сайтов codeforces.ru, topcoder.com и code.google.com/codejam/ так не кажется.
В правилах Code Jam явно прописано: "Contestants also agree that all submitted source code will be made available for anyone to view and download at the end of the contest. Contestants further grant a worldwide, royalty-free right to use, copy, and modify all submitted source code to members of the public after the Contest ends."
На Топкодере аналогично: "By posting, uploading or otherwise sending any source code to us or our Web site, you grant (or warrant that the owner of such rights has expressly granted) us a perpetual, royalty-free, irrevocable, non-exclusive right and license to use, reproduce and publish such code into any form, medium or technology, including the right, at TopCoder's sole discretion, to distribute such code to be published by third parties."
А вот MikeMirzayanov, судя по всему, пока сильно не заботился о юридических аспектах.
Ну так я о том, что можно просто написать такую же ремарку, никого бы это нисколько не озаботило, а удобно было бы.
Не силен в законодательстве, тем более — в законодательстве других стран, но разве исходный код — это персональные данные?
В любом случае — в будущем можно добавить какой-то пунктик при регистрации, я согласен на публикацию исходных кодов моих решений, тогда ведь все будет ОК? Будет согласие и можно распространять.
Почему бы и нет? В статье 3 есть определение понятия персональных данных, и исходный код с ним вполне соотносится.
Я тоже не особо юрист, но, видимо, в таком случае все уже будет по закону.
13 минут
Ок, спасибо. У меня то же самое, но я не пользуюсь prewritten code. А ещё я потратил много времени на то, чтобы поверить, что эта задача действительно не пишется в две строчки, в отличие от всех остальных.
У меня предварительно был написан только код, отвечающий за быстрый ввод-вывод. Дерево Фенвика я писал на контесте.
Ладно. Куда мне до Вас, я ведь всего лишь жёлтый)
Но всё это не отменяет изначального вопроса.
Ну, между прочим, когда я в первый раз употребил слово "синезеленые", у меня был только фиолетовый рейтинг :).
Вас минусуют каждый раз, когда Вы упоминаете это слово? =) Иной причины в данном случае не вижу...
А меня заплюсовали, видимо, те, кто таки разглядел в моих словах иронию над Вашим пренебрежительным отношением ко всем, кто ниже рейтингом ;)
8 минут, там ведь и не сильно больше двух строчек, образно говоря.
Спасибо.
Тем более можно было забыть о правиле сначала пишу, потом думаю, немного подумать и решать в другую сторону, как у AlexanderBolshakov — искать минимум на префиксе, а не максимум на суффиксе. С фенвиком код на С++ будет еще короче.
upd. или искать все тот же максимум на суффиксе, но написав фенвика для суффиксов — тогда его даже не нужно инициализировать.
upd2. Код
Будет какое-то официальное сообщение тем, кто прошёл в первый раунд? Понятно, что если решил задачу, то прошёл, но хотелось бы какое-то ещё подтверждение — обычно (RCC, Codejam) присылают письмо с подтверждением.
Думаю, что да. После разминочного раунда пришло подобное письмо,при этом разминочный даёт проход также как и квал.
Вообще говоря, никакого уведомления не получал в этом году. В прошлом году — было. Но, может быть, это единичный случай :)
Вы уверены что проверяете ту электронную почту, которая указана у вас на странице регистрации?
После этого сообщения открыл для себя, что у меня есть почта на яндексе) На нее действительно приходят письма с оповещениями)
[email protected] и [email protected] — это один и тот же адрес? Если да, то уверен. Если нет, то меня перенаправляет на .com при попытке входа. И в этом ящике последнее письмо датировано 22.07.2013. Подскажите, если я в чем-то не прав. Причем письма такие же, как и были в прошлом году на .by.
Сергей, мне точно пришло. Ещё до начала отборочного.
Я рад за тебя, Антон. У меня по-прежнему нет.
The rules say that the participants with the highest cumulative scores will advance to the finals. Does this mean that we have to participate in all 3 rounds? They are scheduled in such a way that in any time zone at least one contest will be in the middle of a night.
It doesn't — you can participate however you want. Still, the more you participate, the better your chances, since once excellent result gives you much more than 3 good ones.
That's good to know. The rules say it uses total points, number of solved problems and total penalty, but doesn't say which formula is used, so I can't tell how important it is to participate in all 3 rounds. Also, I thought the first round was yesterday, guess I'll wait for it today then as its the only one that happens at night for me.
А я правильно понимаю что окончательные результаты состоят из суммы за ТРИ раунда, или есть какое то правило по которому худший не считается?
Из суммы за три раунда, все верно
Везде одинаковый testcase это сильно :) Круче только везде одинаковые ответы.
Как решать задачу D? dp[sum][n] дает TL на 5 тесте =)))
Там не нужно хранить еще одну размерность, потому что можно сразу умножать на 2.
Можно чуть поподробней?
Храните только dp[xor], тогда ответ можно пересчитывать так dp1[j] = (dp[j] + 2 * dp[j ^ x]) — первое слагаемое это случай когда мы ничего не добавляем второе это когда добавляем текущее x.
p.s. Хотя может я не правильно понял что у вас во второй размерности, и если это просто обрабатываемый индекс то можно же делать только двумя массивами.
У меня dp[n][sum] (сколько банкнот рассмотрели, какой xor), АС за 1.552.
AC, если хранить только последнюю строчку в dp.
Нет, просто я идиот.
не в тот топик