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

Автор Djok216, история, 6 лет назад, По-русски

Let's discuss problems.

How to solve F?

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

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

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.

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

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

    Interesting, does anybody solved it in another way?

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

      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.

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

What's the idea behind problem H solution?

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

    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 :)

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

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

      Now I got it, thanks.

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

How to solve B?

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

    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

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

      Which tool did you use to generate the image ?

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

      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.

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

      Thank you!