FelixMP's blog

Spain Olympiad in Informatics 2024 now available on Codeforces Gym
By FelixMP, history, 9 months ago, In English

I have added this year's Spain Olympiad in Informatics to the gym, both the two days of the finals and the online qualifier round.

Contest facts:

  • One 6-tasks contest and two 5-tasks contests with OI scoring (subtasks).
  • Statements in English and Spanish.
  • There are short editorials available only in Spanish, but it should be feasible to use a translation service.
  • Problems are ordered by difficulty in the online qualifier, but not in the finals.
  • Problem authors: FelixMP, misteg168, JanBobi, Rio.Parquer, MeGustaElArroz23 and ikaurov.
  • The problems cover a wide range of difficulties, and the subtasks make it possible to progress in all problems, so the finals should be interesting contests for participants of all skill levels. The online qualifier has a lower difficulty ceiling but some of the problems are still interesting I think.

I hope you like the problems!

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an editorial or something?

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

    Yes there is, it is in the attachments in Spanish, you can translate it. Feel free to ask here for further explanations.

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

      Sorry I didn't notice it because it doesn't appear during the virtual. Thank you!

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

      Hello! Sorry to bother again. Can you provide more detailed proof for problem E in day 1? Also how to calculate the probability of the solution for problem B in day 1? Thanks in advance.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        Problem B is an easier version of this task(link). There is also an explanation in its editorial. In both tasks choosing a random element of array(and a difference of 1) and looking at its prime divisors gives at least 50% probability to find an answer, so the probability of not finding the answer in the worst case after all guesses is 1/(2^guesses).

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

          oh, we didn't find any similar problem when we set this problem :( (even after a long search because the problem seemed suspiciously common). Thank you for the link.

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

        For problem B, the idea is that $$$T$$$ = 2 is already quite good, since you are trying to minimize the sum of $$$a_i$$$%$$$T$$$, this sum is at most $$$n$$$. With this, you can make another observation, if there is a $$$T$$$ better than 2, then there are at least $$$\frac{n}{2}$$$ elements where $$$a_i$$$%$$$T$$$ = 0, 1, thus you can randomly select like 20 indexes and check the prime divisors of the selected $$$a_i$$$ and $$$a_i-1$$$ and the probability of success is at worst $$$\frac{1}{2^{20}}$$$.

        For problem E, let's prove that in the worst case, you can split the array into 1 element and $$$n-1$$$ elements. Let's think of the bitmask of $$$k$$$.

        If there is at least an element in $$$a$$$ that has a bit equal to 1 more significant than the most significant bit of $$$k$$$, then we have two subcases:

        1- There is an even number of elements in $$$a$$$ that have a bit equal to 1 more significant than the most significant bit of $$$k$$$, then we choose one of these elements (any of them).

        2- There is an odd number of elements in $$$a$$$ that have a bit equal to 1 more significant than the most significant bit of $$$k$$$, then we can choose one of the elements that do not have a bit equal to 1 more significant than the most significant bit of $$$k$$$, these elements exist because $$$n$$$ is even.

        If no element in $$$a$$$ has a bit equal to 1 more significant than the most significant bit of $$$k$$$, then, since $$$a_i$$$ > $$$k$$$ for all $$$i$$$, all elements have a 1 in the most significant bit of $$$k$$$, we can ignore this bit and repeat the process.

        If this process never ends, it means that all elements in $$$a$$$ are equal to $$$k$$$, and, in this case, we can choose any element.

        The conclusion is that it does not matter in which case we are, we can always choose one element. If you implement this proof in $$$O$$$($$$nlogk$$$) you will get 88 points.

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

      maybe the editorial has disappeared. Could you please check it?

      → Reply