Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### eduardische's blog

By eduardische, 7 years ago, translation, ,

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!

• +19

 » 7 years ago, # | ← Rev. 2 →   +8 I believe it is on 9 March :[ http://hsin.hr/coci]
•  » » 7 years ago, # ^ |   0 Oops, thanks a lot.
 » 7 years ago, # | ← Rev. 5 →   0 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 ?
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   +3 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 7 years ago, # ^ |   +11 The 5th problem can be solved with a simple O(N 2) 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 7 years ago, # ^ |   0 I had implemented the same idea, and it got accepted.
•  » » » 7 years ago, # ^ |   0 also we can improve this using combinatorics making the solution become O(N)
•  » » » » 7 years ago, # ^ |   0 Can u explain more about the O(N) solution? I can't solve it with O(N^2) neither because of memory limit...
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 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 .
 » 7 years ago, # |   +22 Just published Results.