ToniB's blog

Croatian Open Competition in Informatics (COCI) 2024/2025 — Round #1
By ToniB, 6 weeks ago, In English

Hi everyone!

The 19th season of COCI is starting soon! The first round will be held tomorrow, October 5th at 14:00 UTC. You can access the judging system here. If you are not familiar with the COCI contest format, we encourage you to read the announcement.

The round was prepared by jklepec, Agnus, celin, fbabic, mlicul and me.

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

Hope to see you tomorrow!

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

»
6 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

What happened to vito1036

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

    I'm still here :) (just not coordinating contests anymore)

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it clashing with meta hacker cup

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

    No it's on a different day. Nvm I was wrong. The contest ends when hackercup starts

    → Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I know you guys are busy and everything but on the announcement page the years for the previous 2 seasons are wrong and the current contest page says 2023/2024

good luck on the contest)

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

Hey, its clashing with Meta Hacker cup. Can the coci contest be shifted to another time?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If we were to shift it, it would conflict with AtCoder. Unfortunately, there is no ideal solution, so we will keep the time as is.

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

How to solve Učiteljica?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    What I did in contest was like this: try to calculate how many good subarrays we have ending in each r (right end), for increasing r. To do that, for every nonempty mask of {1, 2, ..., k} I try to see how many indexes i <= r have no values that occur some frequency that is part of mask. With these, the answer is just calculated by principle of inclusion-exclusion: r minus the number of subarrays not having some frequency i plus the number of subarrays not having the frequencies i and j and so on. Now, for every mask I try to keep some v[i] = the number of good values (that is, with frequency in mask) for subarray [i..r]. When moving from r — 1 to r, we must update some v[i] values. Well, let's look, from right to left, at the positions of the value a[r] (since only its frequency changes): let them be p[1] = r, p[2], p[3], and so on. Considering some frequency f (and the masks containing it), we can see how all i between p[f + 1] + 1 and p[f] considered the value a[r] as bad before (since it had frequency f — 1 and we are looking for r) and now consider it good, while all i between p[f + 2] + 1 and p[f + 1] considered this value as good before and now consider it as bad (for frequency f, since it now has frequency f + 1). So we can use a lazy segtree to put some +1 and -1 on these ranges, and then query how many 0s we have, which is actually equivalent to asking about what is the minimum value and what is its frequency. This works in something around 2^(k — 1) * k * N * logN, which passed without having to optimize stuff.

    code (it is written in contest so it isn't really nice to read but maybe it is helpful): https://pastebin.com/jEnKEWHU

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

When we can upsolve the problems, if we can, how? It seems I am unable to submit any code?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    They should become available on the evaluator soon. I will reply here with the link when the problems are up.

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    You can now upsolve the problems here.

    Go to HONI > 2024./2025. > 1. kolo, and you should be able to see all the tasks. Sorry for the wait.

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

Why does it take so long to publish the results?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    The organizers can be slow sometimes. I reminded them to publish it, so you can expect it to be up soon. Note that participants can see the scoreboard through the evaluator.

    Sorry for the inconvenience.

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

    I'm not sure why the results aren't out yet. You can view them unofficially here.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial has the same problem title twice)

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

    It is a typo, the first one refers to task Hijerarhija. It is ordered the same way as in the problemset.

    → Reply