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

Автор riadwaw, история, 8 лет назад, По-английски

Starts in less than 3 hours

Top 200 from round 2 are allowed to participate and top 25 (aged 18+) will advance to onsite finals

Let's discuss problems here.

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

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

How to solve the third problem?

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

    Shortest path between any two cities is either shortest path around the circle or shortest path from A to the center plus shortest path from B to the center. Shortest paths to/from the center can be calculated with Dijkstra's algorithm.

    Then — bunch of binary searches. For each starting city A remaining cities are separated in three groups based on what is the best way to reach them: go right, go left, go to the center. I find three borders for each starting city: when it becomes better to go through the center than go left, similar for right, and when it becomes better to go right than to go left. Turns out that all these functions are monotonous and we can use binary search. After that — a bunch of prefix sums.

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

    First of all, run dijkstra from center and relax r_i. Now we may notice, that we either go throught center or without going to center. From vertex i, we always go clockwise to some range of vertices [i + 1, i + r], counterclockwise for some range [i — l, i + r] and otherwise throught center. Now use 2 bin.searches in each vertex

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

    Edit: I was too slow :|

    First, set R[i] = min cost from i to center (also take into consideration of going around the circle).

    For each i, find left[i] = farthest point on the left where you should go around the circle from left[i] to i.

    Find right[i] which has similar meaning but to the right.

    Array left[i] and right[i] can be calculated in O(N) using 2 pointers.

    Then for each i, there are 3 types of vertices:

    • left[i] to i
    • i to right[i]
    • the other vertices

    Each type can be calculated in O(1).

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

Damn! I copy-pasted the sample from the third problem without the last line, and obviously the answer didn't match. I wasted about 15 minutes trying to find the bug in the code — almost missed the final because of that.

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

    So there is no runtime error or anything in your code when you try and read an integer that is not there?

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

      Of course not when you're using C++.

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

        Well this is not trivially obvious to me, particularly as Al.Cash uses his own custom input parsing library, I don't think there is anything that stops him from throwing in some assert statements to check for this, although in this cases I suppose he does not.

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

          I see why you asked the question now :). I think he kept same behavior as scanf: returns number of arguments successfully read, and not throw error.

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

      Currently not, as I mimic scanf behavior. This incident suggests changing it.

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

How to solve the second problem?

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

    Let's call a pair "splitting" if the friends are in different queues. Let's find the first splitting pair (in lexicographical order). If something "crosses" it, we need to delete these two pairs, solve the problem recursively (for everything before and after it) and returned the doubled product (we can choose the order of deletion of these 2 pairs). Otherwise, we have to delete this pair alone and solve two smaller subproblems again. The base case is when there're no "splitting" pairs (the answer is some binomial coefficient).

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

    Some sketch:

    We can see that not too many different configuratons of pair is allowed. So call group in one line "good" if it's of form "aa" or "abab" — it may be processed without going to other line.

    Now, while we not finished, calculate and skip good groups. Now in the start you see one of not-so-many configuration of two-line divided groups (or answer is zero). So we can process good groups in any order (it is binomial coefficient) and multiply answer by that number and maybe by 2 if we can process "bad group" in two ways.

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

    Let's try to model the process described in the problem statement.

    Suppose, we've already processed first p1 items from the first queue and first p2 items from the second queue. We may either proceed with the operation that depends only on one of the queues or with the operation that depends on both of queues.

    Operations that depend only on one queue look as following (operations of the first type):

    • aa
    • abab

    Operations that depend on both of the queues(operations of the second type):

    1 way to perform:

    • a a

    2 ways to perform:

    • ab ba
    • aba b

    Consider, that we made c1 operations of the first type with the first queue and c2 operations of the first type with the second queue before we have to make the operation of the second type. We can arrange them in C(c1 + c2, c1) ways (C is a binomial coefficient), so we should multiply the result by this value. Then we have to perform the operation of the second type (and possibly multiply the result by 2).

    If in any step we are unable to perform any of the operations — the answer is 0

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

Ah... First task is almost same with this task I wrote about 3 years ago..

Somehow I failed on this task (by mistype 'n' into '1000') otherwise I could advance. :(

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

Providing the inverse suffix array as an input instead of a suffix array in the first problem was the evilest possible thing :(

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

    Why? You note that at a glance when you look at the first sample. Anyway, there was no reason to do so, I don't justify the authors.

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

      Well, I always have both these arrays in suffix array, so it's weird to call "usual suffix array" only one of the permutations.

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

    what's the difference considering you need both of them?

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

It seems I had small implementation bug in last task, good thing tests had not caught it

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

    Will you release screencast of your win, or are you not doing those anymore? It has been nearly a year now :(

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

      I think about some new formats for this. I do not do screencasts for now unfortunately

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

(pity post warning)

I solved A, D, and submitted for problem B. However my problem B fails due to overflow error, passes with one extra line of "ans %= MOD;"

Sad orange coder ksun48 would have qualified

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

    One of the reasons I wrote a wrapper class that handles modulus for me. It's used for example in this submission 24049890