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

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

http://hsin.hr/coci

40 minutes left. Enjoy!

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

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

How to solve problem E?

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

how to solve problem D for 100% ?

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

    All you need to do is summon mkisic (task author) to the rescue :)

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

    As mkisic is occupied by Maja, I will explain the solution.

    Imagine fixating a row. Now make an array where the value of a field is the number of consecutive fields empty in the up direction. So now we have a problem of findning the sum of areas of all rectangles in a histogram. We can solve the problem in two ways, one is in O(N log N) using divide and conquer and the other one is using stack in O(N).

    I will explain the divide and conquer solution. Using segment tree we can fin the minimum in an interval. Now we want to count the sum of areas of all rectangles whose botom side is in our fixated row and whose height is smaller than or equal to the smallest element in that interval. It is not hard to come up with a formula. Now we proceed with the divide and conquer on the two intervals we get by splitting at the minimum. Notice that you have to be careful not to count some rectangles twice, but this can be easily avoided.

    Insted of using the segment tree to find out those intervals, you can do a simmilar thing with a montone stack.

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

Where can I submit solutions?

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

deleted