Блог пользователя Gerald

Автор Gerald, 13 лет назад, По-русски

Всем привет! Меня зовут Геральд Агапов. Я учусь в Саратовском государственном университете. Сегодня я предоставляю вам набор, надеюсь, интересных задач. Желаю всем удачи!

Хочу поблагодарить RADMikeMirzayanov и всю команду Codeforces за отличную систему и возможность провести раунд! (с) dolphinigle

UPD. 

Раунд завершен. Всем спасибо за участие, надеюсь вам понравилось!

Top 5 Coders:
5. kelvin

Еще один разбор от пользователя Sereja.
  • Проголосовать: нравится
  • +208
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
А это 1-й или 2-ой дивизион ?
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Наконец-то общий раунд, давненько их не было...
  • 13 лет назад, # ^ |
      Проголосовать: нравится -39 Проголосовать: не нравится
    И что плохого в том, что их не было? Было совсем не прикольно, когда многие участники div-2 не сдавали даже двух задач. 
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Anticipating hacker-rush round
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Although I like math a lot ( really, a lot! ), I'm just not that good at it. I hope problems won't be very mathy. ( This may get me many "thumbs down" :) )
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
CF одержали... (из пары варинтов действий, я решил всё же буду писать CF =) ).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Wow i love codeforces.com.Almost 1 contest a week and that contests are great. :)
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
С нетерпением жду твоих задачек :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Record number of regirstrants?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, будет более 2000 участников? Сейчас почти есть.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    регистрация уже закрыта
  • 13 лет назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится
    1900+ - зарегистрировавшихся. Участвует на порядок меньше людей, чем регистрируется 
13 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
А. НЕНАВИСТЬ
  • 13 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    Нормальная задача. Хотя мне, конечно же, после 10 минут работы над А пришло в голову написать сначала В - так баллов явно больше)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Согласен, задача нормальная) Просто немножко понервничать заставила
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Can you please send the notification mail with more time of anticipation?. I received the mail with 4 hours befrore the contest started and  i didn't see it.

I think 18 hours before would be suitable for everyone.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
контест сложнее чем div 1 обычно по-моему
13 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится
вопрос, возможно, некорректен во время раунда, но все же, проходит ли на кф 25млн за 2.5 сек?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Организаторы, обратите внимание, в этом контесте у меня решение задачи C за n*n падало по времени на претестах при использовании g++, но прошло при использовании Microsoft Visual C++.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Как решать C?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    Прошло:
    зафиксил вершину , разбил остальные на две группы: те что идут в нее и те что из нее.
    Посчитал кол-во ребер которые выходят из вершин первой группы и кол-во вершин которые в нее идут, ну и еще я знаю кол-во ребер между группами, теперь нахожу сколько ребер идут из второй группы в первую (по этим данным система выходит), а потом если оно положительное то ищу ответ за Н*Н, он гарантированно есть.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    Поищем какой-то цикл. пусть не нашли, выводим -1.
    пусть нашли. Покажем как уменьшить его до трех.

    пусть цикл 1... n-1 n

    пусть ребро идет из 1 в n-1 тогда 1 n-1 n ответ, иначе цикл уменьшился на 1 вершину
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Кто как делал С?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    найдем любой цикл, рассмотрим например предпоследнюю, последнюю и первую вершину в цикле, пусть это a, b, c , если есть ребро c->a то это ответ, иначе есть ребро a->c и цикл уменьшился на 1, повторяем рекурсивно.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я сначала искал цикл. если его нет - ответ -1.
    иначе возьмем цикл. если 3 его вершины подряд образуют цикл длины 3 - выводим его. иначе мы можем наш цикл уменьшить на 1 (ну там ребро так идет для этих 3х вершин).
    ну и так далее пока или не найдем сразу длины 3 или пока не сожмем большой цикл до длины 3. думаю, нигде не накосячил и это пройдет.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я через топологическую сортировку.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится
    У меня неожиданно прошло вот что. Не могу ни доказать, ни завалить. Находим любые две вершины с одинаковым количеством исходящих ребер. Берем любую из них и говорим, что это одна из вершин ответа, остальные две перебираем.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится
      Более того, можно взять обе из них. Доказывается очевидно, это самое красивое решение, ИМХО
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А если мы выбрали две вершины, у обеих нет ни одного исходящего ребра? Количество равно, но ни одна из них не может оказаться в ответе.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        между ними есть ребро, так что нуль быть никак не может....
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      мне кажется, или ваше решение валит тест 
      6
      010000
      001010
      000001
      010000
      000100
      000100
      по крайней мере, ваш код выдал на него 6 4 2, что как я вижу (если конечно не ошибаюсь), неправильно
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    не туда
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ДФС. В качестве параметров передается текущая вершина, ее номер в цикле (если он вообще будет), первая вершина этого возможного цикла.

    Пробегался по всем ребрам, выходящим из данной вершины. 
    Если номер вершины в возможном цикле 1, то просто идем дфсом дальше.
    Если номер 2, то : 
    если рассматриваемое ребро ведет из данной вершины в вершину T, такую, что из Т есть ребро в вершину F (которая является первой в возможном цикле), то ОК, выводим цикл.
    если не ведет, то запускаем дфс, но теперь номер у данной вершины - 1, у рассматриваемой - 2, первая вершина - данная.

    Кажется, что я непонятно рассказал. Вот код : http://pastebin.com/fkSaWJVR
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Найдём какой-то цикл. Если его нет, то ответ -1. Иначе мы проверим все три подряд идущие вершины цикла. Если ни одна тройка не подходит для ответа, то выкинем каждую вторую вершину и повторим процесс.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня алгоритм тоже находит цикл ДФСом. Потом смотрим если обратное ребро указывает на предок предка рассматриваемой вершины , ну то есть
      if(pi[v]!=-1 && pi[pi[v]]!=-1 && pi[pi[v]]==i)
      то все, цикл длиной три найден. Мое решение валится на 34 тесте, не могу понять почему. http://pastebin.com/VKPbmHsW
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Надеюсь этот тест поможет понять, почему твой алгоритм нужно чуть чуть исправить. По крайней мере на этом тесте твоё решение выдаёт неправильный ответ
        4
        0000
        1001
        1100
        1010

        Правильный ответ 2 4 3
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня dfs(int cur, int prev), а внутри просто смотрю на ребро a[next][prev].
    Зашло, а как доказать, не знаю. Может это вообще неверно.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня такая штука зашла. Считаем все степени исхода s[ ]. Затем за квадрат ищем 2 вершины i и j такие, что Аij = 1 и s[i] - s[j] < 1. Очевидно, что эти вершины можно включить в цикл, и для них за O(n) ищется третья. Почему это решение всегда находит цикл (если он есть), я пока не понял.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      ну понятно, предположим что есть цикл i -> j -> k, и наш алгоритм не нашел такой пары, значит s[i] > s[j], s[j] > s[k], s[k] > s[i], чего быть не может
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      игнор
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Выделял сильно связные компоненты, если есть хоть одна хотя бы из трех вершин, то брал любую вершину из компоненты и перебирал оставшиеся две. Если нет нужных компонент (т.е. нет циклов), то нет ответа.
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Very tough set of questions
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кто-нибудь может дать претест 3 по C?

У меня какая-то тупая бага и я её не могу найти.

13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

По С у кого-нибудь что-то вроде n^3/60 прошло претесты?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня в "Запуске" кубическое решение на худшем тесте работало чуть больше полутора секунд. Но там да, там куб посжимать надо.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На Java не проходило.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    прошло финтесты за ~1600 мс. so sad.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
че то я не понял прикола, у меня в задаче С, даже считаться не успевает, вот сдавал такой вот код - ТЛЕ11, так же пытался сдать считывая сканфом посимвольно, не пихая в вектор, а заводя матрицу смежности, и все равно ТЛЕ11... это нормально, что даже считать не успевает???
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Fast system judging is coming back.
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Не могу не отметить полёт фантазии автора задачи A:

"10^5 участников финала RCC". Это круто!

13 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

my solution is going to fail. prob. B.
Because I am printing only two type of answers :: "2" and "1 000000001"
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Задача А. Тест "10^5 2 / 1 2 10^8 / 1 2 10^8"

Этим тестом валил чужие решения.

Мое решение на таком тесте отработало секунд 20, но на финальных тестах прошло.

Скажите, это нормально?

13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Задача D очень понравилась. Спасибо за контест.
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
for the problem A
 f4 3 - 9 -
 f3 2 4 8 10
 f2 1 5 7 11
 f1 0 6 - 12

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
я тупой >_<
локально решение C на жаве падает со stack overflow.
а на вкладке "запуск" генератор теста вбить не дают.
то, что его можно вшить в само решение, я догадался уже после ресабмита на плюсах и одного неудачного взлома...

кстати, чем именно обусловлена такая разница?
ключи запуска совпадают с указанными тут, java1.6.0_23, win7 x86.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Один забытый модуль стоил победы. И, скорее всего, серьезной потери в рейтинге :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, исправленное решение прошло в дорешивании. Хорошо хоть мой прогноз на число 4-задачников не оправдался
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну что это за контест, где C в 100500 раз проще, чем A и B?
почему я ее прочитал в начале второго часа?! идиот
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Видимо обновили сервера. Тестирование идёт очень быстро, что не может не радовать!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо автору за контест.
Понравилось все, кроме задачи А. Писал ее полчаса и получившаяся фигня в конце концов упала. Наверно там есть простое решение, но оно мне как то не очевидно.
Чуток не успел дописать D. Ждем дорешивания.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я в ней не придумал ничего проще за разбор случаев.

    Возможны такие случаи:

    начальная совпадает с конечной - ответ понятен
    начальная ниже конечной - считаем, когда лифт впервые будет подниматься через этаж, на который приходит участник, после того, как он уже туда пришел (удобней всего считать номер цикла "вверх-вниз"). В этом же цикле он и выйдет на нужном ему этаже.
    начальная выше конечной - аналогично со вторым случаем, только надо искать номер цикла, в котором лифт будет опускаться вниз.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Мне очень не хотелось разбирать случаи.

      Поэтому я написал 2 бинпоиска. Первый - для времени за которое лифт доедет до 1го этажа, второй - для времени за которое он доедет от 1го этажа до 2го. Наверно у меня кривые руки, но это получает ТЛ 19 =_=.

      UPD. Как оказалось, руки не при чем, это все тормозной stl. vector -> массив дает AC =_=.

13 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
Amazing system testing speed.
13 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
the problem A's test data is too weak !
I saw a lot of people just solve it by violence, the time complexity is O(t*n) , but the code pass the system test, I want to know , the system test data is contain data like this:
50000 2
1 2 100000000
1 2 100000000
1 2 100000000
1 2 100000000
.....

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, подскажите плз, за посылки, не прошедшие претесты, какие-то штрафы есть?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Если тест не первый, то да, -50 очков(если в итоге задача сдана)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо. Из-за баги в g++ я потерял я потерял очков 250. Всем на будущее - на g++ решение не проходит по времени, а должно, пробовать отослать под Microsoft C++.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    -50 очков, если задача пройдет систесты, кажется.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Скажите, а почему в B при тесте
10 7 8

ответ 2? Не могу допереть ;(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Потому что второй игрок может как угодно изменить число по модулю 8, а именно на [0..7], то покрывает все элементы Z8
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
спасибо, автору, задачи кайфовые, несмотря на недоразумение с С, раунд мне очень даже понарвился, до сих пор не верю, что как-то сказочно прошла задача А, которую я даже не тестил(она как то магически сразу заработала)  ))
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
I really like C :)

I only wished it has a larger memory limit though.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
мое решение по задаче А которое не проходит мой взлом:
cout<< "100000 10\n";
    for (int i=1; i<=100000; i++)
    {
        cout<< rand() % 10 + 1<<' '<< rand() % 10<<' '<< rand() % 1000000 + 90000000<<'\n';
    }
прошло все тесты!((( как так? вроде же простой тест....
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Спасибо за претесты в С где N >= 1000 ;)
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Задача B, на мой взгляд, гораздо легче задачи А, в которой надо внимательно учесть все возможные случаи. В задаче B надо написать один дебильный цикл и в нем пару операторов.
В задаче C мое решение с использованием тупого бфса поймало ВА71, но как только я написал решение за куб для случаев n <= 750, решение прошло. Как я понял, решения, которые должны хватать TL в задаче A так же заходили. Геральд, тебе надо просить кого-то помогать тебе с составлением тестов. Тест, который завалит мое решение более, чем очевиден. Почему его нет в наборе - загадка.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Ну на мой взгляд количество решивших задачу хорошо показывает сложность задач.

    Что касается тестов, по задаче A действительно фейл и моя недоработка, хотя тупые альтернативные решения по ней были и они падали по TL. 

    Что касается задачи С. Здесь очень сложно придумать тесты покрывающие все возможные эвристики, поскольку в циклических графах турнирах достаточно много циклов длины три. У нас были тесты, в которых от одного до трех циклов длины три и граф размера 5000. Но понятно, что их можно обойти рандомшафлом или каким другим обходом ребер. Мы завалили несколько различных вариантов, учесть все просто нереально. Конкретных тестов валящих эвристики под каждое решение можно придумать целую кучу. 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В A необязательно было рассматривать случаи. Лифт бывает на этаже i в моменты времени
    (i-1) + 2*(m-1)*k, где k >= 0 и
    -(i-1) + 2*(m-1)*(k+1), где k >= 0
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
ну и наошибил я... спасибо автору за хороший сет задач и полученный мною урок...
13 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится
Порадовала скорость работы системных тестов.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему в В на тест 1 2 13 ответ 2?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Первый игрок пишет 000000000 - Второй пишет 000000000
    2. Первый игрок пишет 000000001 - Второй пишет 000000001.
    Второй всегда выигрывает
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Потому что если первый игрок выберет 0, то второй выберет 0 и победит.
    0 + 0 = 0
    Если первый игрок выберет 1, то второй игрок выберет 1 и победит.
    1000000000 + 1 = 0 (mod 13)
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
I have a question, suppose somebody enter into the contest, read problems and don't submit any solution, will the contest be rated for him or not ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    not rated
    • 13 лет назад, # ^ |
        Проголосовать: нравится -27 Проголосовать: не нравится
      so there is a bug , and I suggest that it should be rated if he/she register the contest? do you agree with me?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится
        No, I don't
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        It were like you said some time ago. Now it's better, because if you have an issue and can't come back home, then you don't need to unregister (this happened to me)

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Contest should not be rated only by registering for that contest, but it should be rated for anybody who read at least one problem.(Similar to Topcoder)
                   
      • 13 лет назад, # ^ |
          Проголосовать: нравится -14 Проголосовать: не нравится
        in fact, my meaning is that who registered and read problem should be rated!
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          It's hard to check now, who reads problem. Because It's possible to read it without authentication
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    No, you will get rated only when you submit your code (or try to hack others according to the rules, but I don't know how...)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      You can hack other solutions only after your solution for this problem passes pretests.

      So, only if you try to submit code, this contest for you will be rated.
13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
I am hoping rating increase even though I have not solved anything :)
Because the rating system is flawd sorry.
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Так вроде всё нормально было, только с задачей C, по-моему, не очень хорошо получилось. Вот люди, я смотрю, сдавали самые разнообразные недоказанные квадраты (а некоторые и TL на них ловили). У меня же, напротив, решение - очевидный куб, и это проходит. То есть сразу два косяка: и сильная завязка на оптимальность реализации, и большие шансы угадать решение без доказательства.

Не, мне, конечно, грех жаловаться, ведь рейтинг-то в итоге вырос, но, скажем, на полуфинале я бы такой задаче не обрадовался.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Прошёл тупой перебор троек? Фигасе!)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Эм... нет, ну не настолько очевидный, конечно :) Просто посмотри мой код.
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

I liked problems C and D. But I fear this round might have been too hard for the division2 participants.

Thanks a lot for the round :)

13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Isn't it unfair that if somebody read problems and couldn't submit any solution then that round will be unrated for him.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А в чём фишка теста №23 в D?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Там количество чисел в одном "куске" больше mod
    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Мда, действительно.. вместо p1 % mod * p2 % mod надо было написать p1 % mod * (p2 % mod) % mod
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
It's been a very good contest, I really enjoyed taking part in it. Unfortunately I had to resubmit problem B because of a stupid bug. I did like problem C although I failed to solve it in time.
Big thanks to the author for the contest.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice Experience , Want to see more combined division contests.
Nice problems too. :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится
    To be honest I think that it was div 1 contest, not combined division contest. More than 300 coders finished with 0 pts. And of course I like the problems.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    I notice that combined division contests will easily give more rating .
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Tests of problem A are just unfair. I think this problem should be rejudged with 1-2 strong test case so that solution of O(n*t) (~10^13) cannot get passed. Or this round may be made unrated.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Or in problem statement, there should be something like "the values of t[i] will be given with equal probability in given range".

    PS: Sorry for my bad English.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Понравились задачи B и С, спасибо!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Any ideas how to solve C?
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    1. Try to find any cycle. If there are no cycles prints -1.

    2. If we have any cycle with len>3 
    1 2 ... n-1 n
    let's check edge from 1 to n-1. If it exists 1 n-1 n is correct answer,
    else we have cycle 1 2 .. n-1(because of edge from n-1 to 1), that is shorter. Do it while len>3
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    A little modified DFS, you just should know not only current vertex but previous one too.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

    Here's my somewhat different approach:


    Start with a set containing all nodes. Recurse on that:
    1) If the set contains <= 2 nodes, no cycle is found here.
    2) Pick the first node (say, X). Now, separate the other nodes into two sets, depending on the direction of the edge from that node to the node we picked. That is, put all nodes A such that the edge is from A to X in a set, and put all other nodes in another set.

    Let's name the set with an edge from that set to node X with outward set, and the other set as inward set.
    3) Iterate over all members of inward set, say, I, Iterate over all members of outward set, say, O. If an edge is present from I to O (in that direction), return the triple (I, O, X).
    4) Otherwise, recurse on each of the outward set and inward set, separately.

    This works in O(N^2)
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      sorry, wrong branch

    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Could You explain more clearly point 3 ? If I iterate over all Inward set and for every element in Inward I check all edges to Outward I will definitely get |Inward| * |Onward|, so N^2, so the whole alogrithm will be working in N^3. I suppose point 3 should work in linear time, but I don't know how.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится
        No, we check them in |Inward| * |Onward|. However the overall complexity is still N^2. ;)

        Hint:
        Each edge in the graph will only be checked once in the entire algorithm.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          Now I understand. At the begining I thought that in 4th point You merge Outward  and Inward and then recurse (on n-1 set). But of course if there is no edge from Inward to Outward (which we know from point 3), it is impossible that  there exists some ohter cycle between Outward and Inward (and then the merge is pointless). Thanks for help.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        something like "divide and conquer"
    • 13 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится
      I tried this case 

      4
      0000
      1010
      0001
      0100

      on your code and its output was "1 4 2" which is obviously wrong, not sure if it is a problem in the case I provided or your idea or just a bug, in the last 2 cases that would mean system test was weak. If I am missing something please show it to me :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        It's incorrect test.

        No 1-4 edge and n 4-1 edge
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          "in which every pair of vertexes is connected by exactly one directed edge"
          I totally misread this part in the contest ! :( Sorry for that.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    Let count[v] be the number of outcoming edges of the vertex v. Then number of incoming edges is n - count[v] - 1. Suppose we take two first vertices of the cycle, name them v and u. And there is the edge vu in the graph. Proposal: (count[u] ≥ count[v]) then there exists w such that there is the cycle v → u → w. Let's prove it: suppose we have a vertex w, that there is the edges uw and wv, then we have a cycle. Let's look at the sets of incoming edges of v and outcoming edges of u, if they intersect, then there is such w. Suppose count[u] ≥ count[v] and suppose their sets of outcoming and incoming sets don't intersect. Then the cardinality of their union is n - count[v] - 1 + count[u]. This union doesn't contain v and u. So n - count[v] - 1 + count[u] ≤ n - 2,  count[u] ≤ count[v] - 1 and count[u] < count[v], so there is contradiction.

    Suppose we have a cycle, and there is no edge vu, such that count[u] ≥ count[v]. Let's look at cycle, name their vertices v1, v2, v3. As we supposed count[v1] > count[v2] and count[v2] > count[v3] and count[v3] > count[v1], so count[v1] > count[v1], thats impossible. 
    So the algorithm is to get all the edges vu, and if count[u] ≥ count[v], then find the third vertex of the cycle.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    This is my opinion:

    See the graph as a real tournament, every pairs of different teams plays exactly 1 match. We use an array rank[], in which teams with lower rank always win teams with higher one.

    - Firstly, rank[1] = 1.

    - Consider team I.

    - Find the best team (smallest rank) that team I wins, call it W.

    - Find the worst team (highest rank) that team I loses, call it L.

    We easily observe that rank[L]+1>=rank[W].

    If team W wins team L, we have a cycle I wins W, W wins L and L wins I.

    Otherwise rank[I]=rank[L]+1, and rank[W→array end]+=1

    It works in O(n^2).
     

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      How to get the array rank[] ?
      initially rank[1] = 1 then rank[I] = rank[L] + 1 and rank[W->array end] += 1.
      Are rank[] initially filled with 0's ?
13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
I request rejudge over problem A. It took me (and as I see a lot other also) a bit much time to write O(n) solution where O(n*t) solution passed. By the ways, it helped me a lot to find my math weakness :p
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Any ideas on how to solve problem D?
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    If u know something about FFT(Fast Fourier Transform), it should be better to get in that. Here's my very complex solve, if u had better, plz tell me. : )


    So for F(A), each time, u divide A into two part, the first one of A contains all the elements that mod 2 equals 1, and the second one mod 2 equals 1+1=2(It should be 0 but it can be easier if u understand it as "2"). Then for each part, u do it again. This time, the first part contains the elements mod 2*2 equals 1 and second part contains the elements mod 2*2 equals 1+2, likely, the third part should be mod 2*2 = 2 and forth part mod 2*2 = 2+2.

    Knowing above, we can do something just similar to a binary search in O(log n)(maybe?) time. Assume a function query(l,r,nowmod,nowrest,startid,endid); it returns the available sum from b[l] to b[r]. The other four parameter represent a segment from array b, start from "startid", and end with "endid" and all of the elements in it obey that they mod "nowmod" = "mowrest". Then, if l == startid and r == endid, u just calculate a part of arithmetic progression contains all of the numbers from 1 to n and between u and v. For this step, u can use the formula of the sum of arithmetic progression in O(1), right? Else, u should calculate a position "mid", where the array divide into two parts. If l>=mid+1, all of the needed number is in the right of the progression, so u call query(l,r,nowmod*2,nowmod+nowrest,mid+1,endid). Similarly, if r<=mid, u call query(l,r,nowmod*2,nowmod,startid,mid). The other situation is l<=mid and r>=mid+1,u just break it into two parts, and return query(l,mid,nowmod*2,nowrest,startid,mid)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
When is the editorial coming???
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Virtual contests closed??? 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Any hints on Prob.B ?? thx...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    for each ma = (pa*10e9)%mod , 0<= pa <= min(a,mod-1);
    if(ma>0 && ma + b <mod) then whatever b is , (ma+b)%mod is != 0. 
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
     Хотелось бы узнать ответ на один вопрос : Почему абсолютно одно и то же решение задачи B на Delphi получает TL, а ровно оно же на Free Pascalе спокойно проходит с трехкратным запасом по времени?
До этого я довольно много экспериментировал - сдавал одно и то же и так и эдак и был убежден, что Delphi всегда работает как минимум не медленнее, а обычно и процентов на 20-30 быстрее.  Почему такая огромная разница? Лично меня это в данном случае никак не задело - в посылке на conteste был баг из-за невнимательности, но хотелось бы знать на будущее. 
   Конкретно - посылки 719273 и 719825.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В FPC лучше реализована(и оптимизирована) работа с 64-битными целыми (int64).
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
         Спасибо за ответ. Непонятно другое - в Delphi точно лучше работает double - проверял это на геометрических задачах а в FPC, получается int64 .  Как-то странно. И опять же, учитывая все это, почему бы не сделать разные Time limitы для разных языков. Такое практически везде практикуется - для C и для Java. 
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Вот совсем недавняя история про int64 в DELPHI.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
          Спасибо за ссылку.  Буду теперь знать.
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
I got TLE on B using Python and AC it with C++ and this happened many time in the past. Just wonder if the time limit for python can be lifted up a bit since python is much slower than Java/C
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
My code got passed when I changed std::cin to fgets in problem C. Lesson learned...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
for the problem it seems there are lot of cases regarding where starting , finishing and the current position of elevator is ,,,,How a   lot of coders managed to do it n just a few lines could not get their idea .Can anybody help me please  in finding out that ,,,,,,,
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать E?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    сейчас, через пару секунд появится разбор =)