paula's blog

Croatian Open Competition in Informatics (COCI) 2020/2021 — Round #1
By paula, history, 4 years ago, In English

Hi everyone!

The 15th season of COCI is starting soon! If you are not familiar with COCI contest format, we encourage you to read the announcement. The biggest news this season is the new judging system and full feedback! You can access the judging system here. There you can also find problems from the previous seasons.

The first round will be held this Saturday, October 17th at 14:00 UTC. The round was prepared by Gabrijel, mkisic, pavkal5, satja, stjepanp, dpaleka and me.

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

Hope to see you on Saturday!

(We are aware that the round overlaps with Codeforces Raif Round 1, but the time sadly cannot be changed. Sorry about that.)

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

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Expected difficulty? CF Div1 or 2 or 1.5?

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

    It should be somewhere between CF Div. 1 and Div. 2. You can also check out last year's problems and solutions here to get a feeling for the difficulty.

    Keep in mind that the last three problems are worth the same number of points, and are sorted alphabetically, not by difficulty. But, they have different difficulties. This is to train our students to recognise easier and harder problems, a useful skill for IOI and similar contests.

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

Friendly reminder: the contest starts in one three hours.

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

    Are you sure? It says it starts in more than 2 hours...

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

Will be there editorial ? How to solve Bajka and Papričice ? I got partial points only (20,50).

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

    I can tell you about Bajka. My solution is Dynamic Programming.

    Define dp[i][j] = min cost to reach character j of favorite word (included) such that current position in text is i.

    Base Case is j=0 and you can perform transition in O(n).

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

    The editorial and official solutions will be published (probably) tomorrow.

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

Was there some registration deadline? when I was late for an hour there wasn’t an active event in the UI..

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

    I'm sorry you missed it :(. Registration was open until 14:10 UTC (10 minutes into the contest).

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +23 Vote: I do not like it

can anyone give a good test case for Patkice?

my idea was to check N,E,S,W from 'o' then check the path that leads to 'x' then to add the start direction and the distance/steps taken in an array or else if the path leads to '.' then add 1e6 to the array with the start direction, then sort the array of four elements if they have equal distances then sort them with smallest(direction('N','E','W','S')-'A') .

my code doesn't seems to work or i'm missing something ... my code works on sample cases but fails on real tests (0) :(

my code

or is there a way to download the test data paula?

Thank you.

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

    One bug I faced in contest was that I didn't account for the case where the current pushed me back to the initial island (o). Maybe you have a similar bug?

    Edit

    It does seem to have a similar bug. Try this case:

    4 10
..........
.vo>>>>>x.
.>^.......
..........
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

      OHH(face palming).. thank you so much . i'm so dumb because i spent so much time on this problem figuring why my solution doesn't work... That was the bug. got accepted 50/50. once again thank you socho.

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

        No worries. Congrats on AC :)

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

The editorial is published! link

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

How to prove |S(y) − (n+S(x)) / 2| in task papricice?

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

    Intuitively, we want $$$S(y) - S(x)$$$ and $$$n - S(y)$$$ to be "as equal as possible", so we should minimise their absolute difference, which is equal to $$$\lvert 2S(y) - (n + S(x)) \rvert$$$.

    A formal proof: Let $$$d = \lvert 2S(y) - (n + S(x)) \rvert$$$. Component sizes are $$$S(x)$$$, $$$\frac{n - S(x) + d}{2}$$$ and $$$\frac{n - S(x) - d}{2}$$$. Maximum of the three numbers is equal to

    Unable to parse markup [type=CF_MATHJAX]

    , and it is minimised when $$$d$$$ is minimal. Minimum is equal to $$$\min \left( S(x), \frac{n - S(x) - d}{2} \right)$$$, and is maximised when $$$d$$$ is minimal. So the difference between the max and the min is minimised when $$$d$$$ is minimal.
    → Reply