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!

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

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | Um_nik | 3535 |

4 | 300iq | 3317 |

5 | ecnerwala | 3294 |

6 | maroonrk | 3268 |

7 | TLE | 3223 |

8 | scott_wu | 3209 |

9 | WZYYN | 3180 |

10 | boboniu | 3174 |

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

1 | Errichto | 197 |

2 | antontrygubO_o | 187 |

3 | pikmike | 182 |

3 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 168 |

7 | Um_nik | 164 |

8 | tourist | 163 |

8 | Monogon | 163 |

10 | McDic | 162 |

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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 13:30:30 (f1).

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.