keko37's blog

Croatian Open Competition in Informatics (COCI) 2021/2022 — Round #4
By keko37, history, 3 years ago, In English

Hi everyone!

The fourth round of COCI will be held tomorrow, January 29th 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 ominikfistric, Bartol, paula, pavkal5, 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
  • +63
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

The timing does not work for me, unfortunately. But I really want to try the problems. How can I virtual it (or upsolve the problems)?

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

    You can view old COCI problems on the judge by going to tasks (HONI). The problems from this round will be added once the round is over, within a day or two.

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

Any success with adding rust?

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

    No, sorry. :(

    We didn't manage to do it for this round. We'll try to do it for the next one.

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

      Thanks for info. Let's hope

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

If you want to try to do C in linear time, here's a version with higher bounds.

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

How the fuck have ~50 people managed to solve the third problem? Is there any easy solution which I could not find? I see two solutions with either sqrt decomposition or divide and conquer plus some tricky observations, O(N*log^2(N)) or O(N*sqrt(N)) complexities.

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

    I think the idea of problem C might be a bit classic and old. It has appeared in a Chinese contest about five years ago, and also in the contest mentioned by xiaowuc1. So probably some of the participants have seen this problem before.

    I'm not sure of the details of your sqrt decomposition approach, but if your method is to enumerate the majority element — then with only minor modifications you can get a beautiful $$$O(n)$$$ approach.

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

problem Parkovi (D) is similar to Atcoder ARC116_E — Spread of Information

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

Can someone please explain the idea behind problem B?

My approach:

I got 40/70 pts, so I'm wondering if my approach is nearly correct or if I'm actually completely wrong.

→ Reply