VArtem's blog

By VArtem, 2 weeks 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
  • +67
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

First qualification round will be on Codeforces?

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I didn't receive my credentials.

»
2 weeks 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 [email protected]

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

    Hi Artem.

    Please note that my emails to [email protected] were not answered.

    Can you please pass to them that the registration link for non-russian speakers did not work (I never get any reply from the system with credentials)?

    I want to make sure that this does not repeat for the 2nd qualification round, so we can join it?

    (Last time some of us used translation and went through the russian site, while others, I know, missed the qualification round.)

    Thanks!

»
13 days 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?

  • »
    »
    13 days 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.

    • »
      »
      »
      13 days 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

      • »
        »
        »
        »
        13 days 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.

    • »
      »
      »
      10 days 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?

      • »
        »
        »
        »
        10 days 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
  • »
    »
    13 days 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]$$$.

»
13 days 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? 

  • »
    »
    13 days 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.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        9 days 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.

»
9 days 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).

  • »
    »
    9 days 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?

  • »
    »
    9 days 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.

    • »
      »
      »
      9 days 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.

      • »
        »
        »
        »
        8 days 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?

      • »
        »
        »
        »
        8 days 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

      • »
        »
        »
        »
        8 days 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?

  • »
    »
    8 days 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?

»
8 days 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 ?

»
36 hours 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?