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

Автор piloop, 12 лет назад, перевод, По-русски

Привет всем, Мы рады пригласить вас принять участие в сегодняшнем раунде.

Задачи были подготовлены poopi, Mohammad_JRS, Gerald и мной. Героя сегодняшнего контеста зовут "PMP". Это основной состав нашей команды по программированию вот уже пять лет. Все легенды в задачах метафоричны, но некоторые из них имеют пересечения с реальной жизнью.

Этот Codeforces раунд последний раунд перед надвигающимся финалом чемпионата мира ACM ICPC. Мы желаем всего самого лучшего участникам этого соревнования.

Я хочу поблагодарить Gerald за его помощь и советы по подготовке задач, Delinur за перевод условий на русский и MikeMirzayanov за его замечательную систему.

Мы немного изменили фразу сказанную Burunduk1: "Чтобы раунд был более интересным для нас, прочитайте пожалуйста условия ВСЕХ задач." :)

Надеюсь вам понравятся задачи, высокого рейтинга!

Это перевод оригинального поста с английского. Английский в комментариях приветствуется.

  • Проголосовать: нравится
  • +211
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

интересным для нас

Только о себе и думаете:)

»
12 лет назад, # |
  Проголосовать: нравится -85 Проголосовать: не нравится

"PMP"? Why not "PIMP"? Sounds cool

(waiting for lots of minuses)

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

.

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

Please let us know about the point distribution and difficulty ordering of problems also.

»
12 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

How is the main character (PMP) supposed to be pronounced? The closest I got was "pimp".

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I thought about same thing but got lots of negative votes. Does it mean people pronounce it another way?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Hah, your comment was hidden, but now I saw you said the same. Nah, I suppose they just didn't like the joke =/

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        You should pronounce it same as "ACM", "ICPC", "MST", "MSC" and all other abbreviations. Thanks for your point.

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

      (waiting for lots of minuses)

      You got what you wanted.

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

hope it's not three consecutive unrated rounds

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I hope it will be very interesting!!!;)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I Like PMP!!!

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

Good luck

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

I hope every one will solve at least 1st problem!!! xD

»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

I've heard that Iranians are especially strong in Maths. Should we expect some maths problems?

Anyway, hope everyone enjoys this round.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I read the notes of Div1.E Heaven Tour.

»
12 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Алкогонки... кто придумал это название??

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +62 Проголосовать: не нравится

    Видимо, Вы, так как оригинальное название другое :)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      Черт. Только после прочтения Вашего комментария посмотрел и заметил, что название другое:)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Боюсь представить, что бы про тебя сказал Фрейд =)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    мне тоже так показалось.

»
12 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

The problems were great, thanks!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решалась А div 1

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Ну заметим, что еси уж мы цифру перекладываем, то так, как нам нужно.

    Посмотрим, сколько можно не перекладывать: это кол-во чисел от начала a, которые содержаться в правильно порядке(возможно с чем-то между) в b

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

Несколько вопросов:

А) Почему такое решение — неправда? Применим к первой перестановке перестановку, обратную ко второй перестановке, тогда ответом будет n-l, где l — длина наибольшего возрастающего префикса первой перестановки (WA на претесте 6)

B) Она решалась четырехмерной динамикой? d[s][t][k][m] — наименьшее время для проезда из s в t, сделав ровно k пересадок и начиная с машины m (вроде переход можно делать за О(N), N^4 состояний — 60^5 операций, что около 800*10^6, должно уложиться в 2 секунды).

З.Ы. Клевые задачки, я лох >.<

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно убрать в какой машине едешь. Если прекомпьютишь кратчайшие пути на любой одной машине, то это измерение не нужно. Получается N^4.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В я урезал степень на единицу, чтоб было все же не 800 миллионов операций, а в 60 раз меньше. 800 миллионов у меня без считывания и вывода в запуске корячились полторы секунды.

    Можно посчитать длину оптимального пути между двумя вершинами "без пересадок", а потом клеить путь из "кусков без пересадок", не перебирая, на какой машине проезжать конкретно этот кусок, а просто выбирая "лучшее значенее", которое мы посчитали заранее.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    60^5 (правда еще с логом каким-то) я выломал.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ===Она решалась четырехмерной динамикой? d[s][t][k][m]

    Мне кажеться трехмерной. F[s][t][k]

    нам не важно с какой машины стартовать. Мы делаем предпосчет MinD[i][j] какой машиной оптимально ехать из i в j.

    F[s][t][k] = Min( Min( MinD[s][i] + F[i][t][k-1] ) , — едем с пересадкой в городе i F[s][t][k-1] та же задача но с к-1 пересадкой }

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    По поводу А — у меня такое же решение зашло, проверь, может где в реализации косяк?

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Thank. Very interesting contest.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve problem C?

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    I don't know yet if this solution is correct. Binary search by q. Lets Check if we can get to t from s using q steps: Starting bfs, from all marked verticies,storing DSU, go to the no more than q step from each. If we get to vertex, where we was, check, if dist[current]+dist[vertex where we was]+1<=q, than join their sets in DSU. Finally, if set[s]==set[t], than we can use current q.
    P.P.S. Correct, simple bug..

»
12 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Awesome and interesting problems, thank you very much!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может кто-нибудь, пожалуйста, подобрать тест, на котором валится вот это 1677854 ? Ну или сразу объяснить, почему это не работает. Я просто для каждой цифры из первой строки смотрел, сколько нужно ходов, чтобы она попала на свое место и среди таких значений брал максимум.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It was fun : )

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

Am I the only one who doesn't understand the second problem for the Div 2?

With this input: 4 4 I see 9 rhombus who has coordinates like (x,y) (x+1,y+1) (x-1,y+1) (x,y+2) and 1 rhombus who has coordinate (0,2) (2,4) (4,2) (2,0)

Where am I wrong?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It seems that you are only counting the ones with equal diagonals. Those with unequal diagonals are also possible.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes you're right, I was so stupid thinking during the contest that "sides equals <=> diagonals equals"... Thanks!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    (x,y) (x+1,y) (x-1,y) (x,y+2) is not a rhombus: 3 vertex on one line.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему работает такое решение, кто-нибудь может объяснить? `int cnt=0;

for(int i=0;i<n;i++)

{

    scanf("%d",&x);

    if (x!=a[i-cnt])

        cnt++;

}

printf("%d",cnt);`
»
12 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Did anybody open club of losers?

Last 15 minutes I've tried to debug my B (div 1), and I can't find a mistake. But 3 minutes after end of the contest I've realised that there was j < i instead of j < 3...

If noone open such club, I will open it. I invite everybody, who was unlucky today.)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It reopens every contest by someone

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

    Let's open! I've created array of 100010 elements instead of 200010 (thx Edvard (**fixed**) for hack =) )

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let me in: I tried to hack really wrong solution A div 2, but failed to find 3 numbers a,b,n: n-a % b != 0, n-b % a != 0, n % (a+b) == 0.

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

      Try using a code ;)

      for(int c=1;c<1000;c++)
              for(int c2=1;c2<1000;c2++)
                  for(int c3=1;c3<1000;c3++)
                      if((c-c2)%c3!=0&&(c-c3)%c2!=0&&c%(c2+c3)==0)
                          std::cout<<c<<" "<<c2<<" "<<c3<<std::endl;
      
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Me too, too! Since I'm naive, I believed k ≤ 1000 is important, and iterated 1000 times instead of 60 in B. Never again will doubt myself on these things. >_<

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I made a tiny silly mistake in problem D (div2), but it was accepted the pretest. In stead of f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[1][k][v]), it was f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[i — 1][k][v])... It was too late when I realised the mistake 5 minutes after the contest finished. It was failed the system test.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I tried to hack this code 2 times during contest but it passed somehow! (Div2 A)

    http://codeforces.com/contest/189/submission/1673396

    It ran for 18sec in my PC to produce output of this case: 4000 2 2 2

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Compiled with right keys? It works for 13 seconds on my PC without optimisation, and 1.7 with O2.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо авторам.

Было очень интересно решать Div1 A. }{отя не знаю пройдет или нет.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В D надо было брать все времена выездов по модулю (G+R) и смотреть по отрезкам, кто на каком первом красном остановится (а после этого оставшееся время в пути можно было узнать заранее)? Количество сабмитов подсказывают что где-то может быть подводный камень. Хотя аккуратно это имплементировать тоже надо.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Да, в общем так и надо было.

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

    Мне тоже эта идея в голову пришла, но я не придумал как быстро решать вторую часть.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, действительно, я эту часть неправильно придумал. Оттуда тоже просится найти следующую остановку на красном...

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да получается практически такая же подзадача.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Её можно с конца решать. По очереди добавляя вершины в дерево.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Я тоже так думал и думал что это просто. Но это как то очень просто не делается.

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

      Пусть мы стоим в светофоре с номером i в момент начала зеленого света и мы хотим найти первый светофор после него, который будет красным во время нашего приезда. Для этого будем поддерживать бинарное дерево поиска, в котором ключами будут времена нашего приезда к светофорам с номерами j > i, а значениями будут номера светофоров. Также будем хранить минимальный номер светофора в поддереве.

      Тогда чтобы найти первый красный светофор, можно сделать сплит по g и из правого поддерева взять минимум. А чтобы обновить дерево для светофора i — 1 на величину len, мы просплитим дерево по mod - len, ко всем ключам правой части прибавим len - mod, а ко всем ключам левой прибавим len. Затем склеим поддеревья в обратном порядке. Легко видеть, что от этого структура дерева не нарушится.

      Отвечать на запросы при помощи этой штуки тоже просто и можно это делать в онлайне.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Сдал в дорешивание что-то похожее правда у меня декартово дерево, но ты видимо его и имел в виду. Хотя эту задачу в оффлайн можно обычным деревом отрезков сдать.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Да, у меня тоже декартово дерево в решении. Просто я не уточнял, потому что подойдет любое BST.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem D in div2?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    First, precalc time(i,j) = min time for moving from i to j without changing car. Second, use dynamic: time2(i,j,k) = min time for moving from i to j with changing car <= k times. Base: time2(i,j,0) = time(i,j). Step: time2(i,j,k+1) = min(time2(i, j, k), min_l(time2(i,l,k) + time2(l, k, 0)) (not sure, that first argument in external min is necessary). When you go from i to j, you change car last time in city l, and move from i to l with changing car <= k times, and from l to k without changing car.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Можно пожаловаться на читера?

Переписка:

Отправитель Получатель Сообщение supercooluku

Vlad_Yermak0v

This time I couldnt solve any prob as i joined late... I will loose even the pupil rank.

can u plss send me the code of the problem c and a?

and plss tell me the formula for b....

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +54 Проголосовать: не нравится

    Напоминает анекдоты про албанский вирус.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Самое интересное — я не сдал С, а меня просят кинуть код на нее.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А я тоже такое получил. Он похоже всем подряд рассылал.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem C div.2?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used binary search.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    смотри выше

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Number of fixed points = max {i| b[:i] is subsequence of a}

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

    for the every element a[i] in first array:

    Consider all numbers that are to the left in first array... = set A
    Consider all numbers that are to the right in second array...= set B (after a[i])

    if(A ^ B != {empty}) this is bad for our element (i.e a[i])

    That yields that starting from a[i] to the a[n] all elements must be affected, giving us the answer n-i

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

На какой я бин поиск написал в С?
Я один такой?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    У меня прошло с бинпоиском, хоть я и не до конца понимаю, чего оно не за квадрат одну итерацию бинпоиска делает.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я думал что у меня Н*лог(Н), так-как думал что дисжоин сет работает за О(1), теперь я действительно понял, что это не так.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Сережа, как видно по тегам авторское решение такое как у тебя. Надо было аккуратно писать. Я писал на Java и после того как заменил стандартную очередь на собственую у меня задача пройшла.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ну или на плюсах писать

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Кстати,

            1679392 10.05.2012 22:35:05 LeBron 187C — Скверная Память GNU C++ Превышено ограничение времени на тесте 22 2000 мс 12500 КБ

            Убрал один оптимайз — я прекращал bfs не только если очередь опустошалась, но и если нашел хоть какой-то подходящий путь к конечной вершине. И без этого оптимайза ТЛ 22.

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

          Думаю в авторском бин. поиск + простой дфс. Или есть что-то за O(n)?

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            А как доказать что дфс посетит O(N) вершин?

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

              У меня следующее решение.

              Поставим в вершину с автобусами волонтера. Для каждой вершины найдем Di — минимальное расстояние до любого волонтера. Тогда пишем бин. поиск по ответу (пусть это k). При этом посещать вершины с Di > k/2 мы не можем. Тогда простой дфс, но по ребру можно идти только если обе вершины имеют Di <= k/2. Можно даже доказать почему это верно.

              Только надо аккуратно с парными k.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                Да, действительно. Довольно просто.

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

            У меня волна:
            На каждом ребре поставлю по вершине, что-бы путь из любой в любую был парной длины. Дальше закидываю все вершины с людьми в очередь(и еще вершину финиш) и иду, добавляя вершины, пока старт и финиш не вместе. Если говорить про сложность дисжоин сета как О(1) или что-то близкое, то это решение О(Н+М). Видимо руки не с того места растут, что я еще и бин поиск прилепил к этому.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            В авторском даже немного сложнее. Бинпоиск + обход в ширину с dsu.

            Но видимо есть линейное решение, но конечно не задачу С гробить линейными ограничениями.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Там нужно было одно из двух оставить: либо бин поиск убрать(что я в дорешке сделал), либо проверять на связность компоненты с помощью ДФС.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Видимо у меня точно такое же решение. И я тоже пока не понимаю. Видимо поэтому рейтинги еще не обновили. Наверное авторы пытаются взломать это решение.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Даже если взломают, то уже ничего не изменят. Тесты после контеста не меняются. А то так и решения с хешами можно валить и пропихи рандомизированные разные.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Я тоже думаю что это не очень честно.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не один. АС 0.86 секунды.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не один. 390мс.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Нет. У меня, в теории n^2 log^2 n, но AC за 1750мс.

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Как можно оценить сложность решений вроде 1677747?

Оно заходит со временем 860 мс; при этом я только интуитивно понимаю, что там не квадрат, а что-то более быстрое.

Идея такова — будем обходить BFS наш граф со стартовой позиции, просчитывая для каждой вершины расстояние от ближайшего гида; если пришли в вершину-гида, то запускаем из нее "новый" ВFS, закидывая в очередь ее соседей с расстоянием 1, дальше, если у кого-то из их соседей расстояние больше 2, то поменять на 2 и тоже закинуть в очередь...

Главная проблема — мне кажется, что перерисовок может быть очень много... Как показать, что это не так?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Мне перестала нравиться эта задача...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня вроде такое же решение.

    Идея -- бинпоиск по ответу, а в проверке Форд-Беллман с очередью (как предлагает Burunduk1 здесь)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я хотел написать такое решение, но почему-то был на 100% уверен, что оно получит TL и не стал его писать.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there something special in Test 11 of problem B-div1? It's too large to understand what's wrong. I noticed that I wasn't the only participant who failed on that test.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I think your Floyd algo is wrong

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    replace

                        timer[i][j][k] = min(timer[i][j][k], timer[i][j][f] + timer[i][f][k]);      
    

    to

                        timer[i][k][f] = min(timer[i][k][f], timer[i][k][j] + timer[i][j][f]);      
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you for your help! For some reason I was sure that there are two possible places for the cycle through intermediate vertex: inside and outside other two cycles.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you. My implementation of Floyd was wrong also, and got the same error. I really shouldn't try to save memory:(

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    My code was wrong on test 11 because of this line: f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[i — 1][k][v]... I resubmitted the code after replacing it by f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[1][k][v] and got accepted.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ждём официальный разбор )

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может я покажусь занудой, но мне одному кажется, что пропущены запятые при "пожалуйста"? :)

»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Thanks poopi & piloop for your great and hard contest!

It was an honor for me to participate in a contest whose Problems were prepared by Rivals of my brother in ACM of Tehran Regional!

Hope you the best in World final! ;)

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Div1-C Weak Memory : I was going in the right direction and thought a BFS with Distance array and pushing a vertex again into the Q when visited with smaller distance will TLE. But it worked fast in practice now. What is the worst case complexity of each such BFS ?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Yeah! I spent some 20 minutes during the contest trying to analyze the time complexity, but didn't get anywhere :(

    Any help on how to do it?..

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

когда рейтинг пересчитают! :(

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

    нееееееееееееееееееееееееееееееет..........

    [спойлер]

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Спасибо за контест! Получил от него огромное удовольствие. Побольше бы таких.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

My code got TLE in DIV-1 B in the 12th case. After contest, I changed my 'long long' variables to 'int' and it passed. I know 64bits datatypes will be slower than the 32bit ones, but is it slow enough to give TLE? specially in a fast judge like CF?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I think it's slow because intended solution is O(n^4), while yours is O(k*n^3).

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Your solution runs in about 1000*60*60*60 operations. But "correct" solution should do about 60*60*60*60 operations. So it will be really hard not to get TL even if you use int. But if you use long long you will obviously get TL.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for replies. Somehow I didn't realize that computing Ks >n is pointless.

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

Смешно: в задаче С (div. 1), если правильно понял, летает лобовой bfs, при этом TL-ится честное решение (правда, написанное весьма неоптимально на контесте). То ли я неудачник, то ли задача такая.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    pfff... Левит? обычный поиск в ширину:)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А какое там честное? Мне вот witua объяснил довольно простое решение, которое точно (n+m)*log(n), а не как у Левита, черт знает что:) :) Сначала посчитаем BFS расстояния от каждой вершины до ближайшего гида (это можно сделать в одном обходе графа), потом будем бинарить по ответу, а в бинарке проверять достижимость обычным DFS. Вся идея в том, что если мы идем по путях между вершинами длиной не более k, то это аналогично тому, что мы идем по вершинах, которые не дальше чем за k/2 от ближайшего гида (только еще надо поставить гида в конечную вершину).

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну вот так, да. Можно еще в бинпоиске склеивать в dsu гидов, если расстояние между их вершинами в начальном bfs не превосходит Q. А еще можно без бинпоиска вообще, склеивая гидов по ходу bfs (и ловя момент попадания начальной и конечной вершин в одно множество), так за линию получается.

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Контест отличный (по крайней мере, Div2)! Вот только эх, не дотянул до 1700. Ну ничего, посидим пока тут.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Кстати интересно, а какая может быть максимальная длина кратчайшего оптимального пути в задаче C?

»
12 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Задача Е ништяк. Идея простая, реализация сложная. По С интересно действительно ли можно доказать решение которое как бы за квадрат. Я думал над ним на контесте, но ничего в голову не пришло.

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

    По С я во время контеста думал, что доказал, что мы из каждой вершины релаксацию не более 2 раз будем делать, а вот сейчас понял, что ошибся в доказательстве. Мне кажется, там оценка получается похожая на , но доказать я ее вот так сходу не могу

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      По крайней мере тест, который работает за такое время я вчера придумал, а вот до квадрата дотянуть не получается.

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Won't there be any editorial for this round?

»
12 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

It was very good round :)))