vito1036's blog

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

Hi everyone!

The 17th season of COCI is starting soon! The first round will be held this Saturday, November 5th 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, psruk, Bartol, lovro_nidogon1, 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
  • +110
  • Vote: I do not like it

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

Auto comment: topic has been updated by vito1036 (previous revision, new revision, compare).

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

I wonder if you've added rust?

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

    The main purpose of COCI in Croatia is to serve as a part of the complicated team selection process for CEOI and IOI. The problems and judging system were created and are maintained with that purpose in mind. Rust is not currently available at IOI or any highschool informatics competition that I know off. As such, there are currently no plans of adding Rust, and unless Rust becomes an regularly available language at international highschool informatics competitions, there won't be.

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

      fair enough, though I was under impression from some of organizers replies last year that it would be indeed added

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

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

    no nut novmeber (X) dick destroyer december(✓)

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

vito1036 do you have anything with sending evaluator.hsin.hr username and password to HONI participants? It's 9:20 PM (UTC+1) and I still haven't got it.

Is it my problem or it hasn't been sent yet?

UPD: nevermind I got it now 30 minutes later after sending an e-mail to honi@hsin.hr (I don't know if that matters or I would get username and password at this time anyway)

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

Reminder: the contest starts in one hour.

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

How is this even possible?

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

    Eh, sometimes it's hard to find the right balance between big test cases, tricky test cases and not making the judging servers explode...

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

How to solve Čokolade, and Neboderi ?

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

    Here is my solution to the problem Neboderi:

    Let's mainain a set of positions on which prefix gcd decreased. The set will have at most log positions. When we add an element to the beginning of the the array new set will consists only of a subset of elements that where in the previous set and the new element. We can easily update the set by iterating through every element in it and checking if it still decreases prefix gcd.

    We will start with the empty set and add each element from the end of the sequence. After updating the set the only segments that we need to check are those that end right before decrease of gcd. We iterate through the set n time so the overall time complexity will be O(n log n).

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

Tasks are available for upsolving now on this link in map HONI -> 2022/2023 -> 1.kolo.

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

This is kinda late. But I think problem like Berilij is should be avoided or turned into integers only. If the answer was always guaranteed to be YES, I think using doubles is fine. But the issue is with checking YES/NO.

Even in samples of the problem, we need to use some value of eps to check some equalities. I don't know if I was using something with bad precision (I was using long double) for everything, but I had to set my eps values to more than $$$2 \cdot 10^{-9}$$$, which is larger than the precision of input. After contest dorijanlendvaj even mentioned that eps of $$$10^{-4}$$$ works. From the problem statement, it seems me must be able to check conditions for the YES/NO case with perfect precision. Yet, using eps much larger than precision in input gives AC. I think such YES/NO that is not numerically stable should be avoided in the future.

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

    Precision needed may depend on the algorithm and implementation you use. For example, the task can be solved in $$$O(n + m)$$$ without multiplying any two real numbers together and with using only doubles and precision of $$$10^{-4}$$$. It can also be solved in $$$O((n+m)log(C\epsilon^{-1})$$$ with squaring some real numbers, however you migh need higher precision structures like long double.

    I agree that tasks with floating point precision should generally be avoided, however since COCI in Croatia is designed as part of team selection and preparation for later contests the contestants should be able to handle tasks with floating point numbers.

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

When will solutions and test cases of this contest be published? Thanks.

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

    I am not completely certain about the date, but everything should be published next week.

    → Reply