vito1036's blog

Croatian Open Competition in Informatics (COCI) 2022/2023 — Round #2
By vito1036, history, 2 years ago, In English

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!

  • Vote: I like it
  • +133
  • Vote: I do not like it

Comments Comments (33)
| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Looking forward to trying interesting problems and not being able to solve any :D

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good luck to everyone participating including me :)

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Reminder: the contest starts in one hour.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn t receive confirmation e mail. Any problem with the server ?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not certain, I do not have the authority to check that, but I asked and are waiting for responce.

    → Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve E? I guess it should be solved with euler's formula...

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought the same but it led me nowhere. Commenting so that if anyone posts solution i'll be notified.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +31 Vote: I do not like it

      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!

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I got only 13/50 points on Tramvaji, how to get all 50 points?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it
    My approach
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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

    → Reply
»
2 years ago, # |
← Rev. 6   Vote: I like it -8 Vote: I do not like it

The contest has ended! I scored 120 in total. Here's my approach homemade editorial for "Ekspert".

Approach for Subtask 1
Approach for Subtask 2
Approach for Subtask 3
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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 ;-;

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve "Lampice"? Thanks!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    My approach
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, how can I see problems?

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Great contest for me! I managed to get 200

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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~!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

When will we be able to upsolve the problems? Thanks!

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why were the last three problems (Lampice, Prijateljice, Kruhologija) not sorted alphabetically by their names as stated in https://hsin.hr/honi/pravila.html ?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Could you please make it possible for us to upsolve the contest? vito1036

→ Reply