VArtem's blog

Innopolis Open 2021/2022, Qualification round
By VArtem, 3 years ago, translation, In English

Hi Codeforces!

The Innopolis Open team invites high school students to participate in the first qualification round this sunday, November 21st, 10:00 MSK.

Innopolis Open is an international contest for high school students annually held by Innopolis University. There are two stages:

First qualification round: November 21st, 2021, 10:00 — 15:00 MSK

Second qualification round: December 11th, 2021, 16:00 — 21:00 MSK

You have the chance to advance to the final round through any of the two qualification rounds. The final round will take place on February 19-20, 2022 on multiple sites in Russia and, possibly, in other countries. More information on the website.

Each round will have 5 problems using IOI rules. You can check out previous years' problems in Gym.

We'll be glad to see you participate and hope you enjoy the problems!

Update: now available in a Gym

Update': the solutions are now available! Also please note that in order to avoid the collision with Russian Team Olympiad and Technocup round, the second qualification round is moved one day earlier, on the December 11th, 2021, 16:00 — 21:00 MSK.

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

Comments Comments (36)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

First qualification round will be on Codeforces?

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

I didn't receive my credentials.

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

For non-Russian speakers: if you didn't get your credentials via e-mail, please contact olymp@innopolis.ru

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

Since the contest is over, I think it's appropriate to ask: how to solve C?

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

    Use Vieta's formula and you get: $$$x_1 \times x_2 - x_1 - x_2 = p$$$ with $$$l \le p \le r$$$ which means $$$(x_1 - 1)(x_2 - 1) = p + 1$$$.

    From here it is a simple problem using sieve.

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

      Bruh, I completely missed that x1*x2-x1-x2+1=(x1-1)(x2-1), guess I'm just bad at common math tricks. Can you give a hint on how to get the AC for D? I only managed to squeeze 3 first subtasks

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

        A simple trie would do for D.

        Imagine you have two tries for the left part and the right part, think how the answer will change if you take an element from the right part and put it in the left part.

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

      Could you please tell me how you solve the problem with sieve? During the competition I found out that the answer is the number of divisors of p+1. By using Miller — Rabin test to check primality I got TL on test 74, so I scored 66p. How to solve the problem for 100 points?

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

        Notice that to calculate the number of divisors of $$$p+1$$$, you can just calculate the number of divisors of $$$p+1$$$ which is smaller than $$$sqrt(p+1)$$$ then double it so we can just check the first $$$sqrt(r+1)$$$ numbers. You can calculate it similarly to a sieve (check the code below).

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

    There is also a bit different solution. Let $$$|x_1| \leqslant |x_2|$$$ and $$$b + c = x_1 \cdot x_2 - x_1 - x_2 = p$$$. It holds that $$$|x_1|^2 - 2|x_1| \leqslant |p|$$$, which is equivalent to $$$(|x_1| - 1)^2 \leqslant |p| + 1$$$. We are only interested in $$$|p| \leqslant 10^{12}$$$ so it is enough to check for all $$$|x_1| \leqslant 10^6 + 1$$$.

    For a fixed $$$x_1$$$, we can count the number of solutions $$$(x_1, x_2)$$$ where $$$l + x_1 \leqslant x_2 \cdot (x_1 - 1) \leqslant r + x_1$$$ and $$$x_2 \notin [-|x_1| + 1; max(|x_1| - 1, -x_1)]$$$. The $$$max$$$ part is needed to avoid counting solutions with $$$x_2 = -x_1$$$ and $$$x_1 \neq 0$$$ twice, you can also count them afterwards and then the condition becomes $$$x_2 \notin [-|x_1| + 1; |x_1| - 1]$$$.

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

Thanks to the organizers for putting up great problems for this qualification round!

I will greatly appreciate posting spoilers / solutions to problems D ("Fantastic Three") and  E ("Reconstructing Pairs").

Also, is there a site where we can upsolve this round's problems? 

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

    The tutorials are coming soon (likely tomorrow). In the meantime, check the post for the Gym link with today's problems.

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

      I can't find the tutorial? Where can I find it?

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

        Sorry, some IRL stuff got in the way! I've updated the post with the link.

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

Dear participants, please pay attention to the change in the schedule: to avoid the collision with the Russian Team Olympiad and the Technocup round, the second qualification round will take place on December 11th, 2021, 16:00 — 21:00 MSK (23 hours earlier than before).

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

    Hmmm... this means that the 2nd Qualification Round happens at the same time as Contest #3 of the Croatian Open Competition in Informatics (COCI).

    Would you consider shifting to another day, in order to avoid this collision with COCI, which is quite popular?

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

    Can you please consider shifting in the other direction? As the current change made the contest clashes with the COCI contest, which happens to have a contribution to our IOI team selection.

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

      I'm sorry the clash with COCI happened. We had to schedule the second round during weekend and Sunday is already incredibly busy.

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

        Well , can't you make it the next week , or the week prior to that?

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

        You can postpone the competition to another date or put it at an earlier date in order to allow the opportunity to participate in the coci

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

        Why did you postpone it when it clashed with techno cup and didn't when it clashed with COCI?

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

    This time clashes with the Croatian Open Competition in Informatics as others have said. COCI contributes into the selection process for the Syrian IOI team. Can it be done on a different date?

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

You change the date because of Technocup round which based on " Russian Informatics Olympiad " . but this change made the contest clash with COCI contest which has an important role in" Syrian Informatics Olympiad " , So can you change the date again to be fair ?

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

Do you plan to publish the results of the first qualification round, so we can know if we have to take the second round, or we are already invited based on the first round?

→ Reply