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.
First qualification round will be on Codeforces?
Link?
I registered and received a mail that I will get information before competition start. But there are 20 minutes before the start.
No, we use PCMS hosted by Innopolis U for this contest. If you registered on the website, you should have the link and your account credentials there.
Link to the pcms?
https://pcms.university.innopolis.ru/pcms2client/login.xhtml
I registered over here. How do I find my PCMS credentials? I haven't received any email.
You don't have a profile on this site? Russians can get passwords for PCMS in profile of https://dovuz.innopolis.university/. I believe, you should have a profile on your site too.(login is your email btw)
I'm not from Russia so I don't have a profile there.
I didn't receive my credentials.
Neither I
For non-Russian speakers: if you didn't get your credentials via e-mail, please contact olymp@innopolis.ru
Since the contest is over, I think it's appropriate to ask: how to solve C?
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.
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
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.
Thanks a lot!
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?
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).
Thank you very much!
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]$$$.
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?
The tutorials are coming soon (likely tomorrow). In the meantime, check the post for the Gym link with today's problems.
I can't find the tutorial? Where can I find it?
Sorry, some IRL stuff got in the way! I've updated the post with the link.
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).
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?
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.
I'm sorry the clash with COCI happened. We had to schedule the second round during weekend and Sunday is already incredibly busy.
Well , can't you make it the next week , or the week prior to that?
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
Why did you postpone it when it clashed with techno cup and didn't when it clashed with COCI?
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?
Дорогие участники, пожалуйста, обратите внимание на изменение в расписании: чтобы не пересекаться со ВКОШП и раундом Технокубка, второй отборочный тур пройдет 11 декабря 2021, 16:00 — 21:00 МСК (на 23 часа раньше).
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 ?
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?
Results