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 | 3698 |

2 | Um_nik | 3463 |

3 | Petr | 3341 |

4 | wxhtxdy | 3329 |

5 | LHiC | 3300 |

6 | ecnerwala | 3285 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Benq | 3262 |

10 | mnbvmar | 3248 |

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

1 | Radewoosh | 187 |

2 | Errichto | 183 |

3 | rng_58 | 161 |

4 | PikMike | 159 |

5 | Petr | 157 |

6 | Vovuh | 156 |

7 | Ashishgup | 151 |

7 | 300iq | 151 |

9 | Um_nik | 148 |

9 | majk | 148 |

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: Apr/21/2019 10:13:23 (e1).

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.