Djok216's blog

Grand Prix of Azov Sea
By Djok216, history, 7 years ago, translation, In English

Let's discuss problems.

How to solve F?

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

»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I solved it with DP, where the state is (number of saucers removed from queue, machine that is empty, time after which the other machine will become empty) and the value is the minimum time to get to that state. The important observation that allows this solution to fit in the limits is that the third parameter can be bounded by MAXH*MAXS, because if the free machine can process one saucer before the other machine will become empty it is always optimal to do so.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Thank you for perfect explanation! Actually, this is the author's solution =)

    Interesting, does anybody solved it in another way?

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

      I did slightly differently- Dijkstra with the same state. TBH I am not sure how to do it in DP way, because I had cycle in DP state: at a state instead of taking for one machine, that machine would give up its chance for the other machine, so I had to do it in Dijkstra fashion.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea behind problem H solution?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Author's solution is offline: sort queries by time -> solve problem -> sort queries by id -> output. Main idea is to move Ti instead of Si. You need to store list of validity time intervals Si..Si + 1 (Sn..∞ for the last one) for typed numbers (only if 1 ≤ Bi ≤ N). For each interval you can use lower_bound/upper_bound (with delta depending on Ti of current question) to find first query to increase and decrease counter of correct answers and put such events to priority queue (or just sorted array). The last step is to process all requests one by one using +1/-1 events from priority queue.

    Online solution exists too, but we decided to make simple and fun contest for our on-site participants :)

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

      This solution is based on the fact that no two questions have the same answer.

      Now I got it, thanks.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    We've approached it like this. Let's construct convex hull. After that you calculate answers for all segments of convex hull with two pointers.

    Given one segment you want to find the farthest segment (in terms of index in convex hull array) such that you can remove all points between these two segments. You want the rays constructed from the segments (you connect i-th and (i + 1)-th points for one ray and (j + 1)-th and j-th for another, I mean different directions) to intersect. This can be interpreted as "the angle between the rays is strictly less than π", this can be checked with cross product of their vectors.

    Several points on the same line don't make difference because you will always have the better answer when you take the earliest clockwise of them. We only solved the case with the whole convex hull being on one line with separate if.

    Hope the image tells it clearer. :D

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

      Which tool did you use to generate the image ?

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

        Geometry widget from csacademy and paint lines over it :D

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thank you for the answer. Author’s solution is the same. I just want to add a comment to make your explanation more clear.

      Several points on the same line doesn't make difference because you will always have the better answer when you take the earliest clockwise of them.

      Several points on the same line don’t affect the described algorithm, but you should take into account all the points lying on the boundary of the convex hull to select a right pair of edges and to get correct answer.

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

      Thank you!

      → Reply