Madball's blog

By Madball, history, 4 years ago, translation, In English

Hello, Codeforces!

I would like to invite everybody to participate in a mirror of Ural Regional School Programming Contest, which will be held on Timus Online Judge this Sunday, 31th of January, 12MSK.

For onsite participants this was a standard team contest with ICPC rules. Online participants may play it alone or in a team (up-to-3 people). Even though this is a school student competition with a certain number of simple problems, it also contains some very tricky problems, so it will be interesting for a wide range of people.

The problems were invented and prepared by Gmacem, teewar, BdE and me.

I also want to thank reshke for testing.

Good luck to everyone!

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      As far as I can tell, we were expected to derive speed and initial shift from samples.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I realized in the end!:) That was a big troll ngl=)))

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve A?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation!

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve L?