### VArtem's blog

By VArtem, 3 weeks ago, translation,

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.

• +67

 » 2 weeks ago, # |   +8 First qualification round will be on Codeforces?
•  » » 2 weeks ago, # ^ |   +8 Link?
•  » » » 2 weeks ago, # ^ |   0 I registered and received a mail that I will get information before competition start. But there are 20 minutes before the start.
•  » » 2 weeks ago, # ^ |   0 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.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Link to the pcms?
•  » » » » 2 weeks ago, # ^ |   0
•  » » » 2 weeks ago, # ^ |   0 Okay, thanks!
•  » » » 2 weeks ago, # ^ |   +11 I registered over here. How do I find my PCMS credentials? I haven't received any email.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 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)
•  » » » » » 2 weeks ago, # ^ |   0 I'm not from Russia so I don't have a profile there.
 » 2 weeks ago, # |   +11 I didn't receive my credentials.
•  » » 2 weeks ago, # ^ |   +3 Neither I
•  » » 12 days ago, # ^ |   0 Hi Artem.Please note that my emails to olymp@innopolis.ru 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!
 » 2 weeks ago, # | ← Rev. 2 →   0 Since the contest is over, I think it's appropriate to ask: how to solve C?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +61 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.
•  » » » 2 weeks ago, # ^ |   0 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
•  » » » » 2 weeks ago, # ^ |   +61 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.
•  » » » » » 2 weeks ago, # ^ |   0 Thanks a lot!
•  » » » 13 days ago, # ^ |   0 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?
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   +46 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 cin >> l >> r; if (l <= -1 && r >= -1) { cout << -1; return 0; } l++; r++; if (l < 0) { l = -l; r = -r; swap(l, r); for1(i,l,r) { int x = sqrt(i); if (x * x == i) res--; } } int cur = l; for (int i = 1; i * i <= r; i++) { int x = l / i * i; if (x < l) x += i; for (int j = x - l; j <= r - l; j += i) { cnt[j] += 2; } while ((i + 1) * (i + 1) > cur && cur <= r) { res += cnt[cur - l]; cur++; } } cout << res; 
•  » » » » » 12 days ago, # ^ |   0 Thank you very much!
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   +8 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]$.
 » 2 weeks ago, # |   0 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?
•  » » 2 weeks ago, # ^ |   0 The tutorials are coming soon (likely tomorrow). In the meantime, check the post for the Gym link with today's problems.
•  » » » 13 days ago, # ^ |   +1 I can't find the tutorial? Where can I find it?
•  » » » » 12 days ago, # ^ |   0 Sorry, some IRL stuff got in the way! I've updated the post with the link.
•  » » » » » 12 days ago, # ^ |   0 Thank you!
 » 12 days ago, # |   -12 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).
•  » » 12 days ago, # ^ |   +25 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?
•  » » 12 days ago, # ^ |   +42 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.
•  » » » 11 days ago, # ^ |   -47 I'm sorry the clash with COCI happened. We had to schedule the second round during weekend and Sunday is already incredibly busy.
•  » » » » 11 days ago, # ^ |   +44 Well , can't you make it the next week , or the week prior to that?
•  » » » » 11 days ago, # ^ |   +43 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
•  » » » » 11 days ago, # ^ |   +24 Why did you postpone it when it clashed with techno cup and didn't when it clashed with COCI?
•  » » 11 days ago, # ^ |   +43 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 days ago, # | ← Rev. 3 →   +41 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 ?
 » 4 days ago, # |   0 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?
•  » » 4 days ago, # ^ |   +9