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

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

13-го апреля в 12:00 вас ждет не совсем обычный раунд. Дело в том, что впервые за долгое время Gerald почти не принимает участие в подготовке контеста. Раунд подготовлен мной (как же приятно сделать раунд!), Nerevar-ом, не обошлось без помощи Gerald-а и Fefer_Ivan-а. Маша, спасибо за переводы!

Вас ждут классические баллы за задачи: 500 — 1000 — 1500 — 2000 — 2500.

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

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

А он же пересекается с опенкапом?

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

    Да, я уже отвечал в другой теме. Скопирую ответ:

    Этот раунд проводится по мотивам студенческой олимпиады г. Саратова и не может быть куда-то сдвинут. Типичный D2 раунд привлекает ~2500 участников — большинство из них не участвует в соревнованиях Открытого Кубка.

    Мне кажется, если у вас есть команда и возможность написать Кубок — пишите Кубок. Если вы хотите поучаствовать лично или у вас нет возможности участвовать 5 часов — пишите раунд. Напомню, что раунд будет доступен в виде виртуального ACM-ICPC контеста, как и другие раунда Codeforces.

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

    Ну а так как вы из Div1 — то уж точно вам лучше выбрать кубок, чем этот раунд.

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

sounds cool! Good luck

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

Good luck everyone

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

This round is writen by MikeMirzayanov.Sounds very good!Good luck to everyone!

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

MikeMirzayanov's round.... sounds nice! GL&&HF

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

I'm sure there will be nice questions :)

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

А где же традиционное: Спасибо Михаилу Расиховичу за систему?)

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

    Мне кажется, самого себя благодарить как-то не очень)

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

      Мне кажется, глупо комментировать шутки как-то не очень)

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

I new people join, What is hack?

Please help me?

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

Как решать задачу D?

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

    Я написал жадник. Если пройдет, напишу.

    UPD: Не прошла =)

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

В E предполагалось решение за O(n4)?

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

Как решать D и E?

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

    У меня была такая идея по Е — посчитаем матрицу кратчайших путей алгоритмом Флойда. После этого перебирая пары вершин для ответа, будем также перебирать все дороги из графа. Суммарно выходит O(n4). Судя по ограничениям, такое вполне могло влезть, если написать оптимально...

    Или нет...

    UPD: Конечно, не должно. Не умею я 500 в четвёртую степень возводить :(

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

      Можете объяснить сэмпл в Е, пожалуйста? Я немного не понял условия.

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

        Для всех возможных различных пар s, t (s < t) найдите количество дорог, которые лежат на хотя бы одном кратчайшем пути из s в t.

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

        Вот-вот. Я так сэмпл и не понял. Написал Флойда с возможностью восстанавливать пути. Затем перебирал s, t и для них считал количество дорог, восстанавливая путь от s до t. Итого О(n ^ 3), но в сэмпле я не разобрался.

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

I don't know, if I'm the only one, but really, it seems that problem B and Problem C are easier than problem A... :/

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

That was really funny round. Especially hacks for problem A. Also really nice tasks.

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

For C, I sorted the groups in descending order of the amount of money they paid and then the tables by their size — my soln didn't get accepted. What's the right way of solving it?

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

In problem A , I made 10 successful hacks , however my solution is wrong itself , but no one in my room hacked mine .. :D

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

It was a very good contest.............I enjoyed.........

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

this round trolled me: 46 place before pretests and 542 after )

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

Прибежал на страницу отправки D в 14:00:10. Надеюсь, решение не получит AC, а то я расстроюсь :)
upd. Ураа, TL20 :) Хотя странно, вроде O(nlogn). Но, видимо, как обычно, руки кривые, что ж поделать.

Задачи средние, что-то понравилось, что-то было так себе, в любом случае, спасибо авторам, было достаточно интересно)

А также традиционная рубрика "поноем после контеста". И сегодня у нас в программе "о боже, какая бага!".

Решаю С первой. Достаточно долго — пятнадцать минут. Но тем не менее. Отправляю, получаю WA8. Долго ищу багу. Безрезультатно. Откладываю на потом. ... И вот я с нова её дебагаю. В программе была строчка Table cur = set.ceiling(new Table(g[i].c, Integer.MIN_VALUE));. В ней я ищу первый стол из оставшихся, на котором как минимум g[i].c свободных мест, а если таких несколько, то с минимальным айдишником (для этого второй параметр и стоит Integer.MIN_VALUE). Думаю, люди, знающие, как работают компараторы в Java, а также примерно по мне представляющие, какой я раздолбай, уже поняли, в чём суть. А кто не понял, поясняю. Вот код компаратора для класса Table:

		public int compareTo(Table t) {
			if (r != t.r)
				return r - t.r;
			return id - t.id;
		}

Что же здесь не так? Когда сравниваются два объекта, у которых равны первые поля, а также у первого из которых в поле id стоит Integer.MIN_VALUE, происходит переполнение, которое приводит к неверному сравнению объектов.
Заменил Integer.MIN_VALUE на -1, которое тоже отлично справляется с ролью "минимального возможного, но несуществующего айдишника" и получил AC на 55 минуте. Иии... -400 баллов из-за такой вот чепухи.

И, пожалуй, на сегодня всё с рубрикой "поноем после контеста"! Будьте внимательней при написании своего кода, не допускайте баг, как у дурачка автора поста, и удачных вам контестов ;)

upd2. Хм, странно, E получила WA, хотя решение весьма тупое и прямолинейное. То есть оно могло бы получать TL или ML, но никак не WA. Эх, и снова руки-крюки в деле, да что ж ты будешь делать.

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

Когда будет разбор?

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

    Как обычно — никогда. Здесь таких слов не знают.

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

      а почему минусуем? Майк обычно разборы не пишет, что правда, то правда

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

        Вообще-то это не так. Мой комментарий на самом деле был неприкрытым сарказмом, т.к. сейчас публикуют разборы ко всем раундам на кф. Очевидно, что и в этот раз разбор должен появиться, следует только подождать.

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

      Видимо ты прав

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

Can anyone give me a hint for Prob E ?

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

If we have 2 sets — a, b is it possible to insert all elements of b into a faster then b.size() * log(a.size()) ?

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

Расскажите жадник в С. Я писал дпшку.

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

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

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

      И правда, действительно все просто) Как-то я до этого не додумался.

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

Is this possible to see what input a participant used to hack?

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

Как решать D,E?

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

    Я решил D, стараясь жадно набирать прогрессии.

    Пусть мы в начале новой прогрессии. Идем, пока не наберем последовательность вида -1 … -1 a -1 … -1 b, где -1 может быть и нулевое количество. Если вдруг не наберем, то все хорошо, заменяем все -1 на a или на произвольное число (в случае отсутствия a). Если наберем, то понятно, что заменить минус единицы, чтоб получилась прогрессия можно единственным образом.

    Тогда если эта прогрессия плохая, т.е. знаменатель нецелый или минус единицы придется заменять на <=0, то берем b, как начало следующей прогрессии (а всё предшествующее b будем считать стационарной последовательностью).

    Если все ок, то тогда мы знаем все последующие члены этой прогрессии. Идем дальше, как только встретим несовпадение (или члены вдруг станут <=0), берем первый неподходящий элемент, как начало новой прогрессии.

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

good contest! I did today.

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

My greedy approach for D didn't work. Can you tell me why? 6357863

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

Editorials??

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

Since there are not any tutorial.Can anybody explain the method to solve problem D.