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

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

Сегодня, 19-го января в 12:00 мы открываем новый проект Codeforces::Тренировки. Через 30 минут, в 12:30 мы начнем первую тренировку, на которой вы сможете познакомиться с системой. Продолжительность тренировки – 3 часа. Приглашаем вас принять участие! Как и всюду в Codeforces::Тренировки, будут использованы ACM-ICPC правила.

Так как будет проведена тренировка, то будут использованы задачи некоторого прошедшего соревнования (спасибо авторам!). Пожалуйста, не участвуйте в тренировке, если вы видели эти задачи. Не портите тренировку другим участникам. Спасибо за понимание.

UPD: Контест перенесен на 10 минут вперед. Все замечания по работе и предложения следует писать в виде комментариев в трекере проекта.

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

»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Nice concept... :)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to participate ?
Sorry I don't know about the "Gym" . .
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
how do i take part in this???
there is no "test" contest as mentioned in the blog???
can someone please guide?

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

This sounds like a great idea although it will be 2 30 AM in my time zone, as this is training don't you think you could open another three hour contest in an hour more suitable for us in America (the continent)?

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

>>Через 30 минут, в 12:30.

Если говорить про московское время, то 12:30 настанет через 80 минут, но никак не 30. И все-таки, где раздел тренировки?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Проект откроется в 12:00, после этого через 30 мин, т.е. в 12:30 состоится первая тренировка
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can teams take part in todays contest?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть ли тут кто-нибудь красный, кто может залить парочку моих контестов?
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Баг: на тренировку я зарегистрировался, но надпись "Зарегистрироваться" никуда не пропала.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
will it be rated? (or like other virtual contests, unrated)
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
10 more minutes to prepare? Nice !!!
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
.doc ?????????
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача про восьмиугольники очень понравилась =)
»
13 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
Не пойму, зачем кампус в задаче А. Из Офиса едем по адресам, потом из адреса в след. адрес, возращаемься в школу. А где кампус фигурирует?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится
    Или кампус типа, переходная вершина, если напрямую не могу добраться из адреса в адрес?
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Кампус - это общага школы, видимо=)

    P.S. А вообще тест из условия все обьясняет.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Кампус - это собственно школа
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Упс, действительно. Не знаю, почему у меня в голове засело, что это только общежитие. Видимо, перепутал с dormitory. Спасибо.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
хм, что-то мне кажется, что я какую-то ерунду запихал в В... ))
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Как кто решал задачу B?

Написанная мной жадная редукция 
"abababab" -> "" 
"abababa"->"b"
"ababa"->"bab"
"aa"->"'
(и аналогично для других 5 типов строк) у меня в голове находится где-то между "не могу доказать" и "просто ересь". Однако она проходит все тесты,  и я даже не знаю, верно это или нет.

Какие еще у кого идеи?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Аналогично
    string repl[9][2] =
    {
    {"aa",""},
    {"bb",""},
    {"cc",""},

    {"ababa","bab"},
    {"babab","aba"},

    {"acaca","cac"},
    {"cacac","aca"},

    {"bcbcb","cbc"},
    {"cbcbc","bcb"}
    };

    Тоже хз как доказать.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я также делал, только у меня был сначала RE. Сделал отсечение по количеству операций - зашло :D
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Я делал почти так, только если есть правила "aa" -> "", то нужны только шесть штук типа "ababa" -> "bab", "acaca" -> "cac", ...

      Доказать не очень сложно: достаточно рассмотреть "самый крайний пятиугольник", который затронут замкнутым путём. Если таковой имеется, то всегда сработает редукция.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а как E решать? =)
      Странно, что её больше, чем B решили
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Динамикой по тому, на каком из занятий И-той дисциплины ты был - с переходом с новое занятие И+1 дисциплины. Тут задачи не были отсортированы по сложности.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Единственный переход в динамике, который приходит в голову - это за квадрат, и он по времени не заходит...
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            вот вот, но на cf заходит) cf слишком быстрый или теста такого нет

            P.S. взял код одного из участников с таким же решением, всунул туда генератор, на сервере проработало 3.75 секунд

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

            можно было решать быстрее.
            Для начала отсортируем в каждой дисциплине кабинеты по позиции
            Сформируем граф следующего типа:
            граф состоит из С уровней и 2-х дополнительных вершин - начальная и конечная.

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

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

            Теперь для произвольной вершины с i-го уровня (кроме последнего) бинпоиском найдем ближайшую справа и слева вершину со следующего уровня. проведем ребра в каждую из этих вершин (длина ребра расстояние между этими кабинетами + затраченная энергия). Из последнего уровня будем проводить ребра в конечную вершину. Сложность построения O(C*T*log(T))

            Таким образом в графе будет C*T+2 вершин и не более (С+1)*T*2 ребра.

            Теперь найдем длину кратчайшего пути между начальной и конечной вершиной алгоритмом Дейкстры за O(E*log(V))

            Таким образом итоговая сложность для одного теста O(C*T*log(C*T))

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Просто B - единственная задача, в которой надо было подумать)
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Надо считать минимальную энергию, которую потратит Фред для посещения t-го занятия на c-й дисциплине, и позицию этого занятия: т.е. для каждой новой дисциплины перебрать все её новые занятия, а для каждого занятия (t) с энергией (eNew) и позицией (pNew) - перебрать все предыдущие занятия(tt): eMinNew[t] = min{ tt = 0..T } ( eNew[t] + eMinPrevious[tt] + abs(pNew[t] - pPrevious[tt]) ); pPrevious = pNew; eMinPrevious = eMinNew;

        Ну и в конце сделать переход в псевдо-занятие с энергией 0 и позицией L (соответственно, первое псевдо-занятие с энергией 0 и в позиции 0)

        O(Z*C*T*T)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is it allowed to view others' solutions after the gym contest? I couldn't do this now.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    No, only if you've solved the problem you can see others solutions.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А там еще 3 тренировки есть, они тоже позже запустятся(у них времени нет). Или прочерк значит что только виртуально решать?
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Eh. Why not treat it as normal CF contests which allow people learning from others' code? Otherwise, it's more like another online judge.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Does solving in practice mode count?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

обидно, подумал в Е не зайдет 500млн (Z*C*T*T), написал решение за Z*C*T, сдал черти во сколько... 

как С решать?

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

    Искомую точку всегда можно выбрать на пересечении двух окружностей (кроме тривиального случая, когда ответ - 1).

    Это довольно часто встречающася штука, и доказывается она легко. Допустим мы нашли некую оптимальную точку. Ее всегда можно сдвинуть в какую-нибудь точку пересечения, ни разу по пути не пересекая окружностей. При этом она по-прежнему будет оптимальной.

    Перебираем все пары окружностей, находим их точки пересечения, проверяем насколько эти точки хорошие. Итого O(N3).

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

      так и решал, но почему то не заработало даже на примере, наверное где-то в геометрии косяк

      спасибо за объяснение

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Про какие пары окружностей идет речь?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Окружности радиуса 2.5 с центрами в данных точках.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      .Блин, как всегда моё решение не такое как у людей:)
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А можно решение E за O(ZCT)?

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

      ну идея такая же, только переход за линию: ну считаем данные, и отсортим для каждой дисциплины ее занятия по возрастанию их мест

      в переходе динамики будем сливать места занятий i и i+1 дисциплины (так, чтобы сохранялась упорядоченность), будем идти по этому массиву и поддерживать минимум дп спереди и сзади от нашего текущего j-го, когда мы сдвигаем указатель на j+1, минимум спереди j у нас увеличвается на расстояние между j и j+1, а сзади уменьшается на это же расстояние. каждый раз при новом j релаксируем наши минимумы, то есть если значение дп в этой точке меньше, чем текущий минимум, то делаем релакс. и таким образом мы считаем дп для i+1 дисциплины

      надеюсь более или менее понятно объянил (что врядли), думаю по коду будет понятней

      P.S. ах да, решениие получается за О(ZCTlogT) за счет сортировки, ну само дп за O(ZCT)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я никогда не умел решать геометрию. Поэтому задачу C я сдал следующим алгоритмом. Утверждается, что одним из оптимальных решений будет окружность на границе которой находится одна из точек.
    Переберем эту самую точку. Угол (между этой точкой и центром окружности) переберем с шагом в один градус. Переберем все углы между выбранной точкой и всеми оставшимися. Переберем так же сами точки данные во входном файле. 
    Для каждого из вариантов самым тупым образом посчитаем количество достижимых точек. Выберем лучший вариант.
    Итоговая асимптотика O(N3).
    Может что-то из этого и было лишним, но зашло и на том спасибо.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hi,

Can someone help me with problem C? My code is available here: http://pastebin.com/nPXPM9yB

I made the observation that there must exist an optimal solution where at least 2 contestants lie on the circumference of the circle. Therefore, for every pair of points (A,B), I find the circle of radius 2.5 such that it passes through A and B on the circumference. There are 2 possible centres, and I test both of them. With the circle, I loop through all the points again to see whether they are in the range of the circle, and I compute the best answer.

It seems that the test data is not released yet, nor are the codes of the successful submissions. Could someone help me out here? Is my idea correct?
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Yes, your idea is correct. Here is my code: http://ideone.com/DPTXz EDIT: For some reason, only people who are registered as coaches can view source code at the moment. It looks like your code fails if there are no pairs of points with distance <= 5. Your program prints out 0 when the answer is really 1.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как делать C за 30мс, тратя при этом 15 минут? Я написал за 4ю степень, прошло за 280мс. Знаю еще как за N2log(N), но неужели все это писали?

P.S: почему я не могу видеть ничьи коды по этой задаче, кроме кода maksay?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I noticed that submissions that do not pass the 1st test case do not seem to count: my incorrect submissions do not show up as "+1", but instead show only "+". On the other hand, programs that fail the 2nd, 3rd, etc. test case cause the user to gain penalty points. Is this intended?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It is a small bug. In future system will count attempt failed on the first test if the problem contains exactly one test.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am unable to implement the problems like A. Can someone tell me the way to practice similar problems? I can only think that this problem could be solved by graph but how to proceed next step? Please guide me.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Well I think it's a good idea to create a forum for each contest. Somewhere that people can share ideas and thoughts about each contest just like the way CF rounds are discussed. Is it possible?!
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если два участника назначили виртуальный контест на одно и то же время - они будут видеть результаты друг друга в турнирной таблице?