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!
Looking forward to trying interesting problems and not being able to solve any :D
Good luck to everyone participating including me :)
Reminder: the contest starts in one hour.
I didn t receive confirmation e mail. Any problem with the server ?
I am not certain, I do not have the authority to check that, but I asked and are waiting for responce.
How to solve E? I guess it should be solved with euler's formula...
I thought the same but it led me nowhere. Commenting so that if anyone posts solution i'll be notified.
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!
I got only 13/50 points on Tramvaji, how to get all 50 points?
For 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.
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
The contest has ended! I scored 120 in total. Here's my
approachhomemade editorial for "Ekspert".We can do
A C C$$$y$$$ times. I think most people wouldn't take too long to realize this.Use the idea for repeated squaring, but instead of squaring, use adding. We can then translate adding to queries.
x+=xbecomesA A A,c+=xbecomesA C C. note that the 'D' register is unused.The 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.
"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.
Yep, you are right. I actually meant
D D C.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
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 ;-;
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
How to solve "Lampice"? Thanks!
Assign 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.
Hi, how can I see problems?
You can find them at the contest website, here: https://evaluator.hsin.hr/events/coci23_2/
If you didn't participate, tasks will be available probably tomorrow on: https://hsin.hr/coci/
Great contest for me! I managed to get 200
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~!How can sorting both arrays help you?
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.
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
When will we be able to upsolve the problems? Thanks!
Why were the last three problems (Lampice, Prijateljice, Kruhologija) not sorted alphabetically by their names as stated in https://hsin.hr/honi/pravila.html ?
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.
Could you please make it possible for us to upsolve the contest? vito1036
ppavic dorijanlendvaj vito1036
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. :(