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

Автор Madball, история, 4 года назад, По-русски

Привет, Codeforces!

Приглашаю всех принять участие в зеркале Уральской региональной командной олимпиады по программированию, которая пройдёт на системе Timus Online Judge в это воскресенье, 31ого января в 12:00 MSK.

Для очных участников это соревнования проходило по стандартным правилам ICPC. Онлайн участники могут играть в одиночку или в составе команды (до 3х человек). Несмотря на то, что это школьное соревнование и в нём будет определённое количество простых задач, в нём также будут и достаточно сложные задачи, поэтому оно будет интересно широкому кругу людей.

Задачи вместе со мной придумывали Gmacem, teewar и BdE.

Также хочу поблагодарить reshke за тестирование комплекта.

Желаю всем удачи на контесте!

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

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

5 hours! Is it closer to Div 1 or 2? Also, how many problems?

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

    I hope the contest will be interesting for both divisions. There will be 12 problems.

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

https://acm.timus.ru/problem.aspx?space=1169&num=11. I think this statement is very weird. I mean: "several lampposts", shouldn't we know this number to find the k-th interesting lamppost and also it looks like we don't have any data at all about his walk, just find the k-th lamppost. Am I missing something?

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

    I see that there are some people that agree with me(judging by upvotes), so more might have faced this issue. May one of the contest writers clarify the statement or give some explanation of a sample?

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

Somewhat confusing wording in I: in real world "wind direction" is usually understood as the direction from which the wind originates, and you are using the opposite of it.

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

How to solve A?

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

How to solve J?

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

    Consider building a solution inductively (we claim that the answer is always YES).

    If $$$n = 3$$$, then there is always a cyclic order (clockwise or anticlockwise) along which the $$$a_i$$$'s are non-decreasing. Hence, using that, we can easily construct a solution for $$$n = 3$$$. Note that in this solution, no set is empty.

    We can look at the assignment as assigning arrows between $$$a_i$$$ and $$$a_{i+1}$$$ (indices wrap around), where the clockwise arrows are for assigning the conversation to player 1 and anticlockwise ones for assigning the conversation to player 2. The "balance" of the configuration can be defined as the sum of $$$to - from$$$ over all arrows $$$(from, to)$$$, and it is sufficient to find a balanced assignment of arrows inductively.

    Now consider how we get from $$$i-1$$$ to $$$i$$$. You need to fit $$$a_i$$$ between $$$a_1$$$ and $$$a_{i-1}$$$. To maintain the balance between the two players, you need to assign directions to arrows between $$$a_{i-1}$$$ and $$$a_i$$$, and $$$a_i$$$ and $$$a_1$$$ depending on the direction of the arrow that is currently between $$$a_{i-1}$$$ and $$$a_1$$$.

    As it turns out, this can be done in a manner similar to the $$$n = 3$$$ case, and you'll be done inductively (in $$$O(n)$$$).

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

      Add those with $$$(a_i - a_{i + 1}) < 0$$$ in one set and $$$(a_i - a_{i + 1}) > 0$$$ in other.

      The sum of two sets should be the same as the net sum in a circular array will be $$$0$$$.

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

        This won't quite work when there are indices $$$i$$$ where $$$a_i = a_{i+1}$$$. For handling those cases, it would be sufficient to assign roughly half of those to the first player and the remaining ones to the second player.

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

          Duh, that was a super trivial case, so I left it out of my explanation.

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

      Thanks for the explanation!

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

Madball, what was the intended solution for H? It was quite similar to https://codeforces.net/problemset/problem/1446/F, except that $$$k = 1$$$ in the case of this problem, but this approach gave me TLE during the contest.

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

Did the problems disappear from the site or I just search for them in the bad place?

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

how to solve L?