### Allanur's blog

By Allanur, 5 years ago, ,

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

Good Luck to everyone :)

• +47

 » 5 years ago, # |   -13 Looking forward to it :)
 » 5 years ago, # |   +3 Hello I'm new to COCI. Is it allowed to submit the solutions online to previous contest for practice?Thanks
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 You can find previous contests testdata, solutions and tasks here.Each contest's practice mode is available after the contest.
•  » » » 5 years ago, # ^ |   +3 Can I practice a task from a previous contest (e.g. contest #3) on evaluator?
 » 5 years ago, # |   -6 I'm getting "You're not allowed to log in from this location." when I try to login. Ideas why?
•  » » 5 years ago, # ^ |   +12 You must change HONI to COCI in registration
•  » » » 5 years ago, # ^ |   -6 Thanks :)
•  » » 5 years ago, # ^ |   +3 Check the contest bar. It should be coci not honi.
 » 5 years ago, # |   +24 It would be fabulous if COCI uses full feedback (Like USACO) :)
 » 5 years ago, # | ← Rev. 2 →   +4 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 5 years ago, # ^ |   0 binary search? exist test where answer is 10^500
•  » » » » 5 years ago, # ^ |   0 They announced that the answer can be up to 2e9 only.
•  » » » » » 5 years ago, # ^ |   0 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
•  » » 5 years ago, # ^ |   +8 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
•  » » » 5 years ago, # ^ |   +31 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
•  » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   +10 My code: http://pastebin.com/fFrZ0SmYI think there are two major differences: I process the MP's in random order (array h contains a random permutation of the numbers) my code can change several parties during one round
•  » » 5 years ago, # ^ |   0 U can use greedy on D Easily Excuse me for my naive code http://paste.ubuntu.com/9581807/
 » 5 years ago, # |   0 Why this O(N logN) solution Exceeded Time Limit This
•  » » 5 years ago, # ^ |   0 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 not O(N logN).
 » 5 years ago, # | ← Rev. 2 →   +9 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.
•  » » 5 years ago, # ^ |   +8 The third task was actually a simplified version of a recent CodeChef problem: http://www.codechef.com/NOV14/problems/SEAORD
•  » » » 5 years ago, # ^ |   0 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).
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   +5 Not so many things: http://ideone.com/HkkDuR
•  » » » » 5 years ago, # ^ |   +5 There's nice short solution (<500 Bytes): http://ideone.com/208cQF Got full score (80pts) with this code.
•  » » » » » 5 years ago, # ^ |   +21 printf("%sko\n%d %d\n",a<=b?"Slav":"Mir",N[i],N[j]); That's amazing :)
 » 5 years ago, # | ← Rev. 3 →   +4 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?
•  » » 5 years ago, # ^ |   0 Last problem can be solved easily with simple dp. Yes it's simple but why it's correct? Can you prove it?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 5 years ago, # ^ |   +5 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.
•  » » » » » » 5 years ago, # ^ |   0 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!
•  » » » » » » » 5 years ago, # ^ |   0 Could you give an example of splitting which has not got any huge lines and every rectangle has a window?
•  » » » » » » » » 5 years ago, # ^ |   0 Sorry... I was wrong. Your idea is correct! I proved it using induction. Now everything makes sense! :)
 » 5 years ago, # |   +8 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
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   +5 He misread the problem statement. He thought that we are only allowed to shift, not shuffle.
 » 5 years ago, # |   0 Could anypony describe solutions to Sabor and Stanovi?
•  » » 5 years ago, # ^ | ← Rev. 2 →   -8 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.
 » 5 years ago, # |   +1 And when the COCI Contest #5?
•  » » 5 years ago, # ^ |   0