| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
This contest will be on saturday (20.12.2014) at 14:00 GMT/UTC.
The fourth contest of the Croatian Olympiad in Informatics takes place.
You can login/register here(no registration for contest is required).
For more information this and this.
Good Luck to everyone :)
Looking forward to it :)
Hello I'm new to COCI. Is it allowed to submit the solutions online to previous contest for practice?
Thanks
You can find previous contests testdata, solutions and tasks here.
Each contest's practice mode is available after the contest.
Can I practice a task from a previous contest (e.g. contest #3) on evaluator?
I'm getting "You're not allowed to log in from this location." when I try to login. Ideas why?
You must change HONI to COCI in registration
Thanks :)
Check the contest bar. It should be coci not honi.
It would be fabulous if COCI uses full feedback (Like USACO) :)
What were approaches to E (SABOR) and F (STANOVI)? I couldn't come up with anything short of brute force for E, and got nothing for F.
Edit: I meant nothing short of brute force for E, apologies.
Note on brute-force for D: you can prove that it's always beneficiary to use superpipe powers, since you need to pass at least 1 liter through every pipe. So, either bottom-up DP or simulation with binary search should work.
I got precision errors though, perhaps the whole task was actually to avoid that.
binary search? exist test where answer is 10^500
They announced that the answer can be up to 2e9 only.
Oh, that's quite sad. I reached that problem and I had a minor headache, so when I thought that I had to code long double numbers, I just gave up on the whole contest :P
My solution for E: First select a random party for each MP. Then find a MP who has more than two connections to MP's in the same party and change this MP's party, and repeat this until everything is ok. I got full points, no idea why this works :D
Let T be the number of edges uv that u and v has the same color. Each time you change the color of some vertex, T is decreased by at least one so you find a correct solution after at most M changes
I do the same thing, but I get TLE in the 10th test case. Can you give me some hints to make my code run faster? Thanks!
Here is my code: http://ideone.com/FQtOdy
My code: http://pastebin.com/fFrZ0SmY
I think there are two major differences:
U can use greedy on D Easily Excuse me for my naive code http://paste.ubuntu.com/9581807/
Why this O(N logN) solution Exceeded Time Limit This
It would be
O(N logN)if you delete a element from the set for constant number. While you're decreasing some index, you're also increasing other. That's why, this is notO(N logN).My overall feeling is that this was the weirdest COCI I've ever written.
2nd task: Am I missing some really easy solution here? I don't understand why this is second task, considering 3rd or 4th.
3rd task: max(sum, 2*max). It was actually nice to prove that and I liked it, but at the same time this was so easy to guess that I feel that many didn't even bother to prove it.
4th task: Again, it's clear that since we need to deliver amount of water >= 1.0 to each note, that using superpipe powers is always beneficiary. From here it's trivial bottom-up DP or binary search with simple simulation. Just need to avoid precision errors. Why N <= 1000? Why restrictions on water to each node >= 1.0? These simplify things too much in my opinion. Easier than 2nd task (unless I'm missing something there).
5th task: I liked this task, but as already mentioned here, looks like it was vulnerable to random approach without actually solving task.
The third task was actually a simplified version of a recent CodeChef problem: http://www.codechef.com/NOV14/problems/SEAORD
I see. I wouldn't mind if they just required to output any order as well, which would require to at least think of why it's max(sum, 2*max).
5th task is a bit different version of one of the most known Math problems. The solution is quite elegant, but there is already the same at timus and one of Sereja's rounds at CF.
2nd task: This task was tricky. The idea is very simple, but there are lots of things that you can mess up. Just simulate the game and pay attention to the last steps of the game.
4th task: N <= 1000 because N <= 100000 doesn't make the problem harder, does it? Yeah, this one seemed pretty straightforward, doesn't deserve the 4th spot.
in second task the players don't play optimally they just do the steps mentioned in the statement so this is just a simulation problem.
Sure, however there are many things to mess up in simulation. Hence, I believe it was a lot harder to code than 3rd or 4th problem. Unless there is some clever solution which can avoid all this stuff.
In my solution, I just coded up binary search on the point at which a player loses. I thought this got rid of some unneeded casework. My code isn't the most concise, but I had relatively few problems dealing with tricky cases. Here is my code for reference: http://ideone.com/nmp1PH
Not so many things: http://ideone.com/HkkDuR
There's nice short solution (<500 Bytes): http://ideone.com/208cQF Got full score (80pts) with this code.
That's amazing :)
Last problem can be solved easily with simple dp. There are N.M.16 states. Since you just need to remember width, height and for each edge out or in (24). To calculate each state one can silmply divide current rectangle with horizonal or vertical segments. So overall complexty is O(N316).
PS:I dont understand why this problem was 6th problem. I would not give it even 4th level. What do you think?
Last problem can be solved easily with simple dp.Yes it's simple but why it's correct? Can you prove it?
We are not going any state that has all 4 edges are "in". We have 2 options to decide whether divide our rectangle to smaller ones or do not divide at all. If we are not dividing then answer for that state equals (width * height - K)2.
Solution found from above procedure obviously guarantee that every rectangle has at least a window at the end. Also every end state that fulfills the conditions are handling too. So answer can not be less then the solution we found.
You have to prove in some optimal solution, exists a vertical line with length equal to m or a horizontal line with length equal to n. You are using this fact in your solution while dividing the table into smaller ones.
Now i understand where you are coming from :) To be honest, i did not noticed this until you told me. I did not thought about it much but it seems like when there is not any of the "huge" lines you described above, it's impossible to make every rectangle has a window.
Well, I don't think so! You can reach that target without the 'huge' lines but that case won't be optimal.
It looks hard to prove!
Could you give an example of splitting which has not got any huge lines and every rectangle has a window?
Sorry... I was wrong. Your idea is correct! I proved it using induction. Now everything makes sense! :)
I read statement of CESTA 20 mins and did not understand, why this problem first and only 50 pts? I can solve it only with hashing/suffix array. Now i see my code got 0 pts, and we need to shuffling, not shifting digits :D
I can't tell whether you're being serious or not...
If you are, then I can tell you it is just trivial maths. Notice that number must be multiple of 3 at the beginning (before reshuffling) and must have a zero after shuffling.
He misread the problem statement. He thought that we are only allowed to shift, not shuffle.
Could anypony describe solutions to Sabor and Stanovi?
For Sabor, assign a party to each member, any assignment will do. Next, we will "fix" this assignment. For a person who has more than 2 opponents from the same party, we flip his party . Doing this will guarantee that the number of invalid people goes down by at least one. Hence, if we repeat this process, not only will the number of invalid people go down until 0, but the complexity will also be bounded by the number of people.
And when the COCI Contest #5?
COCI site