Не забудьте, всего через пол часа, в 18:00 по Москве начнется второй раунд GCJ
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Зачем минусуете? Здесь же можно будет обсудить задачи после контеста!
А вот почему.
Вы вообще, я смотрю, красавцы! Сделали обсуждение здесь да ещё и заминусовали:D
Спасибо огромное за этот пост!
Без иронии, я умудрился забыть про контест.
Double post: http://codeforces.me/blog/entry/7842
Недостаточно глубоко прямой эфир просмотрел, да
Не плохой такой у bmerry last second save :)
Прям как у вас на полуфинале :-)
Сколько человек дальше идут? Сколько футболки получают?
Дальше 500, футболки 1000.
500 и 1000
Как решать A и C?
На А можно было сортонуть все рейсы, потом идти слева на право, хранить сколько человек должны выйти на каждой станции, и сколько есть каждых карточек. Когда нужно кому-то выходить, то жадно отдаем самые новые карточки.
Разбор доступен сразу после контеста в dashboard.
В A — тупая жадность.
Для начала посчитаем сколько будет потрачено, если никто не будет меняться карточками. Это делается тривиально, если использовать формулу суммы арифметической прогрессии.
Теперь найдем, сколько потратить можно, если оптимально передавать карточки. Заведем массив событий, в котором будем хранить для каждой станции метро (из тех, что есть во входных данных) сколько человек заходят и выходят на этой станции. Всего таких событий будет не более 2·M. Дальше будем идти по событиям. Когда люди где-то выходят, то им выгодно выйти с карточкой, которая в пути как можно меньше времени из тех, что еще не сданы при выходе. То есть надо использовать карточки, которые были взяты при входе на как можно более поздних станциях. Ну, а как обрабатывать добавление карточек — зависит от реализации.
Реализовать это можно на обычной бинарной куче (priority_queue в C++).
В задаче С надо было записать в граф все ограничения, которые мы имеем из массивов A и B, а именно:
В массиве A:
1. если i < j, A[i] >= A[j], то X[i] > X[j].
2. для каждого A[i] != 1, X[i] больше, чем X[j], где j — номер последнего A[j] == A[i] — 1.
Аналогично для массива B. потом просто осуществить топологическую сортировку в этом графе, при этом, понятное дело, из двух несравнимых вершин раньше идёт та, у которой меньше номер (чтобы последовательность получилась лексикографически минимальной).
Какая будет сортировка для графа из трех вершин с одним ребром 3->1?
Нам ведь надо лексикографически минимальную обратную к топологической сортировке перестановку
2 3 1
не, я имел в виду, что ребро идёт из i в j, если мы точно знаем, что x[j] > x[i].
Но сортировка 2 3 1 даст значения x = {3, 1, 2}, что больше, чем {2, 3, 1}
Ты прав.
На самом деле я делал так: перебирая числа от 1 до n, которые мы запишем массив, каждый раз выбирал самое раннее место, куда его можно поставить.
Стресс-тест показал, что на всех возможных перестановках длины до 10 такое заходит. Осталось понять, почему.
Достаточно было посмотреть scoreboard и убедиться, что у меня зашло, или ты не веришь в квалифицированность организаторов GCJ?
Очевидно, что при таком подходе на первом месте окажется самое маленькое возможное число.
Мне вот пока не удается понять почему это правильно. Я сдал такую же лажу в контесте, но потом понял, что можно нормально лексмин искать, но было уже поздно :)
Вообще есть и не рекурсивный алгоритм топологической сортировки. Он заключается в следующем: Выбирать любую вершину, из которой ничего не выходит. Добавить её в сортировку. Удалить из графа вместе со всеми рёбрами. Повторить. Этот алгоритм вполне подходит для того, чтобы находить лексмин топосрт
Я так и делал, но нам нужен, как заметил cerealguy, вовсе не лексмим топсорт, а какой-то другой.
Решение, которое я сдал по С. Кто-нибудь умеет доказывать? Вообще без понятия, почему работает, и еще больше без понятия, почему lex-min.
Будем ставить числа по возрастанию. Когда мы поставили какой-то набор чисел есть оценки снизу на ai, bi. Поставим очередное число в самую левую, в которой оценка уже достигла того, чего надо, и если поставить туда нигде оценка не превысит ограничения. Код. Он видимо понятнее чем описание.
Построение хоть какого-то легко доказать (мы каждый раз ничего из "пула" возможных не выкидываем, только добавляем)
Насчет лексикографической минимальности умею убедительно махать руками :)
А я кажется наоборот умею доказывать лекс. мин в предположении того, что ты сказал (именно твоего утверждения, а не построения хоть какого-то). Но не умею доказывать, что по второму условию ничего не может выкинуться.
Ровно потому, что "нигде оценка не превысит ограничения". У нас плохо то может стать только от того, что стало слишком много
Нет, смотри. Почему из-за того, что мы сделали A, мы не перестанем мочь B, потому что оно начнет мешать С, а раньше не мешало?
А как оно может начать мешать С? Если С правее, чем В, то оно может начать мешать, только если А увеличил путь для В, а он не мог
Посмотрел я на список людей с 37 очками, и понял что не один я недоволен тем что C-small < A-large...
Одного меня удивило, что ровно на 500-м месте находится чемпион Мира по программированию?
А так же на 610 и 665, причем двукратные
еще на 665 например. Кто найдет еще ниже?Надо учиться читать.Вижу двух золотых медалистов в 14той сотне.
В очередной раз доказывает, что в интеллектуальных соревнованиях такое понятие как "форма" тоже играет огромную роль.
В очередной раз доказывает, что в интеллектуальных соревнованиях такое понятие как "рандом" тоже играет огромную роль.
Извини, давно хотел спросить. Твои ник произошел от swinger? Ну, тех что подружками меняются
Форма конечно важна, но отыграть фэйл на A-large сегодня было довольно тяжело (задачу D выкидываем, C-small < A-large, нужен C-large). Поэтому отчасти это превратилось в контест одной задачи. Кстати, на чём большинство по А повалилось?
Вот я не понимаю — как можно зафэйлить A-large?
Не заметить, что нужно брать по модулю? Там вроде A-small без него проходит. Или потерять где-то 64-битный тип. Непонятно как еще.
А, про модуль я заметил, разумеется, а что касается типов, то питон рулит :)
Вот я тоже не понимаю. Моё рандомно выводит отрицательные числа. Конвертация int -> long long везде тоже не помогла. Уже полчаса безуспешно пытаюсь найти ошибку. Поможете?
UPD: Прикол про взять модуль у произведения 2х чисел при вычислении произведения 3 вроде учёл.
UPD2: Баг был в том, что вместо (a + b * c) % MOD было a + b * c % MOD. Спасибо winger.
Я скомпилировал твой код g++, запустил на своем A-large, и твой код сегфолтится на строчке
ev[evc] = make_pair(o, make_pair('i', p));
Скобки нужно добавить, т.к. a*(b*c)%MOD == (a*(b*c))%MOD
UPD. это я неправильно скобки посчитал
Что логично. Он туда 2*N кладет, а не N.
Сорри, MAXN = 2005. Всё равно отрицательно всё. Линк обновил. Исправлял в те самые 8 минут, при откате назад потерял это исправление.
У меня вроде же как раз a*((b*c) % MOD).
UPD: Понял, спасибо большое. Вот вечно мне говорят что я слишком много скобок ставлю и наконец-то я таки недоставил...
Вот здесь?
res2 = (int)((long long)(res2) + (long long)(p) * ((((long long)(st) * (long long)(st-1) — (long long)(st-trav) * (long long)(st-trav-1)) / 2LL) % MODLL) % MODLL)
Да (впрочем как и в ещё 2 скопипасченных местах), выкидываем вложенный MOD и получаем:
res2 = (int)( (long long)(res2) + (long long)(p) * (VALUE) % MODLL )
Кто-то не брал по модулю и честно выводил BigInteger
Мда... Контест сегодня был очень жестоким. Два двухкратных чемпиона Мира не прошли в следующий раунд.
Вот это уровень, достойный чемпиона мира по программированию — проходить с последнего проходного места.
Слабо?
После чистки читеров он скорее всего поднимется выше.
Не знаю, что касается чистки читеров, но сразу после окончания контеста у меня было 380 место, а сейчас — 381.
Не настолько, чтобы его выступление стало для него удовлетворительным)
Будь я чемпионом мира, я бы сильно не расстроился)
А я бы расстроился)
Як тому, что лучше быть чемпионом мира, и пройти с 500 места, чем зафейлить финал и пройти с топ 50.
Хотя, конечно, тебе виднее)
Или я чего-то не понимаю, или чемпионат мира немного другое соревнование...
Это как бы не очень зависимые события.
Какая тут логика? Человек, сливший контест, должен задуматься о том, чего он добился в этой жизни, и на основании этого решать, расстраиваться или нет?
Наоборот, если бы я был чемпионом мира, то я бы расстроился даже больше, потому что для чемпиона мира такой результат — более ощутимый слив, чем для какого-нибудь "неплохого АСМщика".
Можно для нубов идею по Б?
Если не смотреть в Dashboard'е разбор, то бинарим по ответу и жадно моделируем за количество раундов. Для деталей реализации просто посмотри чужие решения.
Научимся для каждой команды находить, какое максимальное место она может занять. Это означает, что эта команда сначала выигрывает все, что только может, а потом начинает проигрывать. Что означает, что команда выигрывает? Это означает, что среди тех команд, которые до сих пор выступали так же, как она, есть команда, с меньшим номером.
Оk, храним 4 значения: количество команд, которые на сей момент выступили лучше данной количество команд, которые на сей момент выступили хуже данной (с этими командами рассматриваемая команда не поменяется местами уже никогда). количество команд, которые на сей момент выступили так же, как данная, но их номер меньше (они сильнее) количество команд, которые на сей момент выступили хуже данной, но их номер больше (они слабее)
Первоначально эти значения равны 0, 0, k, N — k — 1 (где k — номер рассматриваемой команды)
Дальше прогоняем N раундов. Чтобы подняться как можно выше, команда должна выиграть очередной раунд. Она может это сделать, если последнее значение больше 0. Также желательно, чтобы как можно больше БОЛЕЕ СЛАБЫХ команд, чем рассматриваемая, выступили так же, как она (чтобы потом можно было выигрывать у этих команд). Значит, слабые команды играют друг с другом и выигрывают друг у друга, поэтому последняя величина сокращается в два раза, а проигравшие перемещаются вниз. Аналогично, команды, которые выступили так же, как текущая, но сильнее ее играют друг с другом, проигравшие спускаются вниз.
В итоге получаем лучшее место, которое может занять команда номер k. Похожим образом определяется худшее место, которое может занять команда номер k. Дальше перебираем все команды и для каждой определяем наихудшее и наилучшее место — вот и ответ. Для решения B-large нужно перебор заменить на двоичный поиск по ответу.
Вот мой код: http://pastebin.com/4vKtwdWG
Думаю, что он вполне понятный.
http://pastebin.com/z6iLRNcd
Какой-то у тебя длинный подсчет позиции в лучшем и худшем случае.
Длинное то, что внутри цикла? Может быть, это можно сократить, я не придумал. Еще я отдельно разбирал случай, когда сверху-снизу остается четное и нечетное число команд — конечно, это можно сделать одной формулой, но я для надежности написал if
А, ну у тебя рекурсия вместо цикла — я это не представлял себе рекурсивно. Рекурсия короче записывается, да.
Плюс с четностью-нечестностью я поосторожничал.
весь контест смотрел на ~(p-1), вроде как маска игр последнего призера, а для участников пытался составить лучшую и худшую маску, но не смог понять принцип построения. Видимо только моделирование.. Спасибо.
А почему Вы считаете, что команда должна выигрывать все, что может. Может быть, она поочередно то выигр., то проигр.?
потому что если она выиграет после какой-то череды поражений, то ничего не мешало выиграть у той же самой команды до случившихся поражений и обеспечить себе нужное место раньше
Ну вот я как раз не очень понимаю это. Если мы выиграли у нее, то возможно, мы не успеем сыграть с другими соперниками, просто потому что они проиграют другим командам, а не нам.
Попробуйте понять следующую вещь: если мы выиграем на данном шаге, а не проиграем, то гарантированно займем место выше, вне зависимости от того, что будет дальше. Поэтому такая жадность работает.
Место команды определяется лексикографическим порядком строки из побед и поражений этой команды, поэтому для того, чтобы занять как можно более высокое место нужно выигрывать, если это возможно.
Решение за O(1) на тест: http://pastebin.com/aufkpZjV
Использует встроенную в GCC функцию __builtin_clzll, которая (как минимум) на x86 выполняется за константное время. В остальном идеальный C99.
(Решение придумал сам и только сейчас сравнил с официальным. То же самое, хотя в официальном есть недочёт, из-за которого при P = 2N оно первым числом выводит несуществующий номер команды 2N + 1 - 2 вместо 2N - 1. Замечу, что во время контеста я отправил более медленную версию, работающую за O(N), — это я уже поотимизировал.)
Между прочим, Chortos-2 использовал 18 разных языков для решений на GCJ!
Screencast