### vito1036's blog

By vito1036, history, 2 months ago,

Hi everyone!

The second round of COCI will be held tomorrow, December 3rd at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by dorijanlendvaj, ppavic, Bartol, mkisic, mlicul and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you and good luck!

• +133

 » 2 months ago, # |   +1 Looking forward to trying interesting problems and not being able to solve any :D
 » 2 months ago, # |   +5 Good luck to everyone participating including me :)
 » 2 months ago, # |   +11 Reminder: the contest starts in one hour.
 » 2 months ago, # |   0 I didn t receive confirmation e mail. Any problem with the server ?
•  » » 2 months ago, # ^ |   0 I am not certain, I do not have the authority to check that, but I asked and are waiting for responce.
•  » » » 2 months ago, # ^ |   0 Thank you ! I have received the confirmation e- mail !
 » 2 months ago, # |   +13 How to solve E? I guess it should be solved with euler's formula...
•  » » 2 months ago, # ^ |   0 I thought the same but it led me nowhere. Commenting so that if anyone posts solution i'll be notified.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +31 Hi, author here, the solution goes as following:Yes indeed, we can use the Euler characteristic of the surface, mainly $V - E + F = 2 - 2g$ where $g$ is the number of holes. Now we have to count $V$, $E$ and $F$. To count $F$ we can simply do a dfs on the faces, marking each face we visit. The number of visited nodes is exactly $F$. Because each face has degree exactly $4$, by the handshaking lemma $E = 2F$.The trickiest part is counting the vertices. For each face you can actually calculate the degrees of the four vertices forming the side. Let's say you are trying to calculate the degree of the left vertex of the edge you are pointing at. You can mark the current face and start a "left cycle" until you return to the marked face. The number of faces you visit is exactly the degree of the vertex, you can easily see this by "flattening" out the part around that vertex, it essentially looks like a flower with either $3$, $4$ or $5$ petals. Now you can easily infer the total number of vertices and then the total number of holes!
 » 2 months ago, # | ← Rev. 2 →   0 I got only 13/50 points on Tramvaji, how to get all 50 points?
•  » » 2 months ago, # ^ | ← Rev. 2 →   -6 My approachFor all sentence from Patrik, we learn the information about $S_i$, the distance from the first station to the current one. Now the issue is on Josip. Can we translate Josip's sentence to Patrik's sentence? In fact, at most two sentences from Patrik will suffice to represent Josip's sentence. For the first sentence said, Josip's sentence is equal to Patrik's sentence. We do not need another sentence for this. For the rest, we can translate Josip's sentence to Patrik's sentence for the current station, subtracted by Patrik's sentence for station $y-1$. Therefore, we get the result that $S_i = t_i + S_{(y_i-1)}$ for Josip's sentences. Now the rest should be the same as your original approach.
•  » » 2 months ago, # ^ |   +15 Let's call a[i] the distance from station 1 to station i. When Patrik says something on query i you assign integer T to a[i+1]. If it is Josip, then you assign a[y]+T to a[i+1]. This always works because when you reach query i, you have already found the answer for all indices 1 through i. Now to find the shortest path you have to see which two consecutive stations have the shortest distance between each other
 » 2 months ago, # | ← Rev. 6 →   -8 The contest has ended! I scored 120 in total. Here's my approach homemade editorial for "Ekspert". Approach for Subtask 1We can do A C C $y$ times. I think most people wouldn't take too long to realize this. Approach for Subtask 2Use the idea for repeated squaring, but instead of squaring, use adding. We can then translate adding to queries. x+=x becomes A A A, c+=x becomes A C C. note that the 'D' register is unused. Approach for Subtask 3The current approach for subtask 2 has $O(\log y)$ complexity. This almost works, but we have a constant of $2$ here, and therefore this approach can get a maximum of about 128 queries. Instead of this, we now use the smaller one to lift the larger one. As $x \cdot y \le 10^{18}$, we can derive that $\min (x,y) \le 10^9$. This reduces the maximum to about 64 queries. note that the 'D' register is still unused. Yes, everyone, the 'D' register is completely useless.
•  » » 2 months ago, # ^ |   0 "We don't need too much thinking to do this."Funny enough, your approach for Subtask 1 is wrong, I think you thought $C$ $C$ $D$.Btw, I liked problem Ekspert so much! So happy I solved it during contest.
•  » » » 2 months ago, # ^ |   0 Yep, you are right. I actually meant D D C.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 How does this work for subtask one? x<=50 and y<=50 means xy<=2500. Btw I solved first two subtasks. My method is that xy<=10⁴so always one of them is smaller than or equal to 100. So depending on which of x or y is smaller you can keep adding them to C
•  » » » 2 months ago, # ^ |   +10 Wait it was that both x and y are equal or less than 50? I thought it was $x \cdot y \le 50$ I think I'm blind ;-;
•  » » » » 2 months ago, # ^ |   0 No I guess I'm the blinnd one. I first read the second subtask x,y<=10^4 then I noticed it was a multiplication dot. Probably the same happened here
 » 2 months ago, # |   +1 How to solve "Lampice"? Thanks!
•  » » 2 months ago, # ^ |   +18 My approachAssign some random 64-bit value to each lamp. Let it be v. Then you will add v to m[x1][y1] and add negative v to m[x2][y2]. This is something similar to hashing. Now all you need to do is count the number of submatrices that have sum of 0. That can be done in O(N^2 * M * log M). Just make sure to not count the ones which have one of their dimensions as 1.
 » 2 months ago, # |   0 Hi, how can I see problems?
•  » » 2 months ago, # ^ |   +1 You can find them at the contest website, here: https://evaluator.hsin.hr/events/coci23_2/
•  » » 2 months ago, # ^ |   +11 If you didn't participate, tasks will be available probably tomorrow on: https://hsin.hr/coci/
 » 2 months ago, # |   +4 Great contest for me! I managed to get 200
 » 2 months ago, # |   0 Hints for Prijateljice? Seems like it is not too hard according to the number of solve in the leaderboard. I thought of some dp but it leads to nowhere. Thanks~!
•  » » 2 months ago, # ^ |   0 HintHow can sorting both arrays help you?
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 do $dp[n+m]$ where $dp[i] = true$ if the guy who has $i$'th smallest string wins by starting with $i$'th smallest string, $dp[i] = false$ otherwise.
•  » » 2 months ago, # ^ |   0 The basis of "game DP" kind of problem is "If you can reach a losing state, then it's a winning state. Vice-versa, if you can only reach winning states, then it's a losing state".Let $dp[i] = true/false$ be whether this is a winning word. We want to check the $dp$ all words that can immediately follow word $i$. There are two ways: The reachable words on the opponent's side forms a continuous range of sorted words. We only check three words: (1) the opponent's immediate larger word starting with the same letter, (2) the opponent's largest word starting with the next letter, (3) the opponent's smallest word starting with the next letter
 » 2 months ago, # |   +16 When will we be able to upsolve the problems? Thanks!
 » 2 months ago, # |   +2 Why were the last three problems (Lampice, Prijateljice, Kruhologija) not sorted alphabetically by their names as stated in https://hsin.hr/honi/pravila.html ?
•  » » 2 months ago, # ^ |   +38 For this round, we made an exception. Croatian version of the contest HONI is made for elementary and high school students. We did not want the younger contestants to get stuck on reading the interactive problem because they probably did not see that type of problem before.
 » 2 months ago, # |   +59 Could you please make it possible for us to upsolve the contest? vito1036
•  » » 2 months ago, # ^ |   +4
•  » » » 2 months ago, # ^ |   +3 Sorry for not answering, I was waiting for the tasks to get uploaded on evaluator, but unfortunately they still are not. Maybe oj.uz can help? Solutions, test cases and tasks are available on hsin.hr/coci. I will inform you when the task become available on evaluator, I cannot upload them. :(