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!

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 167 |

5 | antontrygubO_o | 166 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

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!

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 22:08:33 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I believe it is on

9March :[ http://hsin.hr/coci]Oops, thanks a lot.

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

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 ?

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.

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.

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.

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

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

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

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

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

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 .

Just published Results.