eduardische's blog

COCI 2012/2013 — контест №6
By eduardische, 12 years ago, translation, In English

Today (09.03.2013) at 14:00 UTC the sixth (the last regular) contest of the Croatian Olympiad in Informatics. takes place. You can login/register here. Duration: 3 hours. Good luck!

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

»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I believe it is on 9 March :[ http://hsin.hr/coci]

→ Reply
»
12 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

May anyone suggest a suitable method to solve 4th problem ? I only came up with the following observation.


For a horizontal line y = c : 
the answer is the number of triangles that have at least one line segment (x1,y1)<-->(x2,y2) : y1 < y2 , 
c belongs to the interval ]y1..y2[
-  For a vertical line x = c : 
the answer is the number of triangles that have at least one line segment (x1,y2)<-->(x2,y2) : 
x1 < x2 , 
c belongs to the interval ]x1..x2[

I used 2 segment trees to handle the horizontal and vertical cases , but that scored 80 / 120 , due to exceeding the memory limit in the last 2 testcases. I think there are some tricks(coordinate compression , solving the horizontal cases then clearing the segment tree then solving the vertical cases) , but I'm not sure if they can help out.

And may anyone suggest how to approach 5-th problem ?

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

    If you have the range of [0..2^x-1] you can easily store a segment tree in one array of integers — for values. Every other needed information is easily computed on-the-go.

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

    You only need to do two sweep lines, one for the X queries, and another for the Y queries.

    In each sweep line, you need to keep a counter that tells you the number of active triangles.

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

    Regarding the 4th problem: First off, lets simplify the prob by assuming we deal with rectangles rather than triangles. Using that simplification we can make two arrays X and Y. where we are going to append X_min and X_max and Y_min and Y_max for each rectangle respectively. Secondly, we make two new arrays for X and Y: X' and Y' where on the i-th index we write the number of rectangles, edges of which are situated on the different sides of X[i].

    This is just an idea.

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

    The 5th problem can be solved with a simple O(N2) DP. The key observation is that any two adjacent elements in a good sequence differ by not more than 1. The reverse is also true: any sequence in which every two adjacent elements differ by not more than 1 and the first and the last elements are equal to 0 is good.

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

      I would also say that the correct relief of length N form a bijection with correct bracket sequence of length N-1, where in N-1 spaces we can put spaces as well. For example in 3rd sample case:

      ? ? ? 2 ? ?
 ( ( - ) )
 ( - ( ) )
 - ( ( ) )

      The numbers represent the level of bracket sequence at a given point.

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

        I had implemented the same idea, and it got accepted.

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

      also we can improve this using combinatorics making the solution become O(N)

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

        Can u explain more about the O(N) solution? I can't solve it with O(N^2) neither because of memory limit...

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

          you use dinamic array as i think dn[N][N]

          you can use dinamic array like this dn[2][N]

          because f(n,k) = f(n+1,k)+f(n+1,k-1)+f(n+1,k+1)

          n is the position in the array and k is the what is the array[i]

          so you must only know N th and N+1 th rows .

          → Reply
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Just published Results.

→ Reply