The contest is in the gym: Innopolis Open 2019-2020, qualification, contest 2

Hello!

The second qualifier to Innopolis Open 2020 rescheduled to December 14th 1:00 PM UTC.

Qualifier duration is 5 hours, there are five problems in the contest. Those, who scored high enough, will be invited to the final contest that takes place on February 22-23, 2020. Those, who already qualified, can compete in second qualifier as well, but they won't influence qualification.

Innopolis Open is only for middle and high school students. All others will be able to solve the problems in Codeforces::Gym.

There is a trial round taking place, it ends in the evening of December 13. If you are new to Innopolis Open it's good to take part in trial round to get to know the testing system and format of problems. Be careful, the trial round and qualifier don't take place on Codeforces website. To take part in the trial round or the qualifier you are required to sign up on Innopolis Open website. Don't forget to read the rules and the testing system guide on the website.

First qualifier took place several weeks ago, you can try to solve the problems in Codeforces gym: Innopolis Open 2019-2020, qualification, contest 1.

Previous year contests. Be careful, some of them may be in ICPC format:

• Innopolis Open, Final round, 2015-2016
• Innopolis Open, Elimination round, 2016-2017
• Codeforces Round #402 (Div. 1) (Round based on 2016-2017 finals)
• Innopolis Open, Elimination round 1, 2017-2018
• Innopolis Open, Elimination round 2, 2017-2018
• Codeforces Round #467 (Div. 1) (Round based on 2017-2018 finals)
• Innopolis Open, First elimination round, 2018-2019
• Innopolis Open, Second elimination round, 2018-2019
• 2018-2019, Innopolis Open

Hello.

On December 23rd at 07:00 UTC we are hosting the second elimination round of our olympiad for high school students. More information on olympiad's website. The rules are IOI-like. Round will last for 5 hours, and consist of 5 problems to solve.

Live standings

We hosted the first round Innopolis Open, First elimination round, 2018-2019 on December 1st. Those, who already advanced to the final round, can skip the round, but certainly can participate if they want.

We can discuss problems after the round here.

Good luck all!

Prepared by gritukan

Prepared by GreenGrape

Prepared by dusja.ds

Prepared by pashka and YakutovDmitry

Prepared by dusja.ds and VArtem

Prepared by dusja.ds and burakov28

Prepared by BudAlNik

Editorial

Hello!

Codeforces Round #467 (Div. 1) and Codeforces Round #467 (Div. 2) will take place on February, 25 at 14:35 UTC. Most of the problems are Innopolis Open Olympiad in Informatics problemset. We ask olympiad participants not to take part in Codeforces rounds and not to discuss the problems till the end of the rounds.

Problems were prepared by: niyaznigmatul, pashka, gritukan, VArtem, burakov28, BudAlNik, YakutovDmitriy, dusja.ds, GreenGrape, tourist. We thank testers: demon1999, senek_k, the_art_of_war, Qrort, ayoyia, izban и julsa.

Good luck!

UPD: The round is rescheduled to +1.5 hours to avoid collisions with other events.

Hello.

On December 17th at 07:00 UTC we are hosting the second elimination round of our olympiad for high school students. More information on olympiad's website.

Scoreboard

Contest in gym: Innopolis Open, Elimination round 2, 2017-2018

We hosted the first round Innopolis Open, Elimination round 1, 2017-2018 on December 2nd. Those, who already advanced to the final round, can skip the round, but certainly can participate if they want.

The problems are prepared by dusja.ds, burakov28, julsa, KamilBek, josdas, BudAlNik, disa, lightning, VArtem, pashka, niyaznigmatul, firezi, ilnar. We thank the developers of PCMS for testing system, we also thank ilsaf13, who does the technical support of our olympiad. We thank the testers of the rounds senek_k, demon1999, hapooo, zclimber, YakutovDmitry.

We can discuss problems after the round here.

Good luck all!

779A - Pupils Redistribution

Problem setter: MikeMirzayanov

To solve this problem let's use array cnt[]. We need to iterate through first array with academic performances and for current performance x let's increase cnt[x] on one. In the same way we need to iterate through the second array and decrease cnt[x] on one.

If after that at least one element of array cnt[] is odd the answer is  - 1 (it means that there are odd number of student with such performance and it is impossible to divide them in two. If all elements are even the answer is the sum of absolute values of array cnt divided by 2. In the end we need to divide the answer on 2 because each change will be counted twice with this way of finding the answer.

779B - Weird Rounding

Problem setter: MikeMirzayanov

To solve this problem we need to make k zeroes in the end of number n. Let's look on the given number as on the string and iterate through it beginning from the end (i.e. from the low order digit). Let cnt equals to the number of digits which we reviewed. If the current digit does not equal to zero we need to increase the answer on one. If cnt became equal to k and we reviewed not all digits we need to print the answer.

In the other case we need to remove from the string all digits except one, which equals to zero (if there are more than one such digit we left only one of them). Such digit always exists because the problem statement guaranteed that the answer exists.

779C - Dishonest Sellers

Problem setters: MikeMirzayanov and fcspartakm

To solve this problem we need at first to sort all items in increasing order of values a _i - b _i. Then let's iterate through sorted array. If for the current item x we did not buy k items now and if after discounts it will cost not more than now, we need to buy it now and pay a _x, in the other case we need to buy item x after discounts and pay b _x.

778A - String Game

Problem setter: firezi

In this problem we have to find the last moment of time, when t has p as a subsequence.

If at some moment of time p is a subsequence of t then at any moment before, p is also its subsequence. That's why the solution is binary search for the number of moves, Nastya makes. For binary search for a moment of time m we need to check, if p is a subsequence of t. We remove a ₁, a ₂, ... a _m and check if p is a subsequence greedily.

778B - Bitwise Formula

Problem setter: burakov28

Note that changing i-th bit of chosen number doesn't change any bits of any of the variables other than i-th one. Also note that the total number of values is greater, as more variables have 1 at i-th position.

Let's solve for every bit independently: learn, what is the value of i-th bit of chosen number. We can try both values and simulate the given program. Choose one of the values that makes more variables to have 1 at i-th position. If both 0 and 1 give equal number of variables to have 1 at i-th position, choose 0.

778C - Peterson Polyglot

Problem setters: niyaznigmatul and YakutovDmitriy

While erasing letters on position p, trie changes like the following: all the edges from one fixed vertex of depth p are merging into one. You can see it on the picture in the sample explanation. After merging of the subtrees we have the only tree — union of subtrees as the result.

Consider the following algorithm. For every vertex v iterate over all the subtrees of v's children except for the children having largest subtree. There is an interesting fact: this algorithm works in in total.

Denote as s _x the size of the subtree rooted at vertex x. Let h _v be the v's child with the largest subtree, i.e. s _u ≤ s _{h v} for every u — children of v. If u is a child of v and u ≠ h _v then . Let's prove that.

1. Let . Then and .
2. Otherwise, if , then we know that s _u + s _{h v} < s _v. Therefore, .

Consider vertex w and look at the moments of time when we have iterated over it. Let's go up through the ancestors of w. Every time we iterate over w the size of the current subtree becomes twice greater. Therefore we could't iterate over w more than times in total. It proves that time complexity of this algorithm is .

Solution:

1. Iterate over all integers p up to the depth of the trie
2. For every vertex v of depth p
3. Unite all the subtrees of v with running over all of them except for the largest one.

How to unite subtrees? First method. Find the largest subtree: it has been already built. Try to add another subtree in the following way. Let's run over smaller subtree's vertices and add new vertices into respective places of larger subtree. As the result we will have the union of the subtrees of v's children. All we need from this union is it's size. After that we need to roll it back. Let's remember all the memory cells, which were changed while merging trees, and their old values. After merging we can restore it's old values in reverse order.

Is it possible to implement merging without rolling back? Second method. Let's take all the subtrees except for the largest one and build their union using new memory. After that we should have two subtrees: the largest one and the union of the rest. We can find size of their union without any changes. Everything we need is to run over one of these trees examining another tree for the existence of respective vertices. After this we can reuse the memory we have used for building new tree.

778D - Parquet Re-laying

Problem setter: pashka

Let's assume that the width of the rectangle is even (if not, flip the rectangle). Convert both start and final configurations into the configuration where all tiles lie horizontally. After that, since all the moves are reversible, simply reverse the sequence of moves for the final configuration.

How to obtain a configuration in which all tiles lie horizontally. Let's go from top to bottom, left to right, and put all the tiles in the correct position. If the tile lie vertically, then try to turn it into the correct position. If it cannot be rotated, because the neighboring tile is oriented differently, proceed recursively to it. Thus, you get a "ladder", which can not go further than n tiles down. At the end of the ladder there will be two tiles, oriented the same way. Making operations from the bottom up, we'll put the top tile in a horizontal position.

778E - Selling Numbers

Problem setters: niyaznigmatul and VArtem

Because the target value for this problem is calculated independently for all digits, we'll use the dynamic programming approach. Define dp _k, C as the maximum possible cost of digits after we processed k least significant digits in A and C is the set of numbers having the carry in current digit. This information is sufficient to choose the digit in the current position in A and recalculate the C set and DP value for the next digit.

The key observation is that there are only n + 1 possible sets instead of 2 ⁿ. Consider last k digits of A and B _i. Sort all the length- k suffixes of B _i in descending lexicographical order. Because all these suffixes will be increased by the same value, the property of having the carry is monotone. That means that all possible sets C are the prefixes of length m (0 ≤ m ≤ n) of this sorted list of suffixes. This fact allows us to reduce the number of DP states to O(n·|A|). Sorting all suffixes of B _i can be accomplished using the radix sort, appending the digits to the left and recalculating the order.

The only thing that's left is to make all DP transitions in O(1) time. To do that, maintain the total cost of all digits and the amount of numbers that have the carry. After adding one more number with carry in current digit, these two values can be easily recalculated. After processing all digits in A, we have to handle the remaining digits in B _i (if there are any) and take the best answer. Total running time is .

Hi, Codeforces!

Codeforces Round #402 (Div. 1) and Codeforces Round #402 (Div. 2) are going to happen on February, 26th, at 08:05 AM UTC. The round will run at the same time with Innopolis University Open, Olympiad in Informatics. Division 1 problems are the same as olympiad problems. Some of Division 2 problems are prepared by MikeMirzayanov, thanks to him.

The problems are developed by MikeMirzayanov, YakutovDmitriy, VArtem, firezi, burakov28, pashka.

We hope you enjoy the problems!

UPD:
problem scores for div1: 500 — 1000 — 1500 — 2250 — 2250
problem scores for div2: 500 — 1000 — 1000 — 1500 — 2000 — 2500

UPD 2: Congratulations to winners!

Top-10 (Div.1)

1. bmerry
2. ainta
3. Marcin_smu
4. kcm1700
5. moejy0viiiiiv
6. anta
7. FizzyDavid
8. Reyna
9. dotorya
10. gs12117

Top-10 (Div.2)

1. Chiaki.Hoshinomori
2. WhyamIhere
3. mjkocijan
4. Schemtschik
5. kiiiiii
6. pisos_pro
7. marcospqf
8. fushar
9. safarisoul
10. Panole233

Editorial is here.

Hello, Codeforces.

This weekend ITMO University in St. Petersburg with Barnaul, Almaty and Tbilisi will host ACM ICPC Northeastern European Regional Contest.

We have 266 teams (thanks to MikeMirzayanov and snarknews for the link) competing for the chance to go to the ACM ICPC World Finals 2017 which is going to take place in South Dakota, USA.

In ITMO University site 106 teams will compete, including ACM ICPC 2016 World Champions and the team that is leading Opencup ranklist.

We have an Instagram account, we will post there some pictures from contest halls and other weekend activities.

If you are not competing in NEERC, you can try to solve the same problems in mirror. It will take place at 8 AM UTC, December, 4.

Contest scoreboard.

Team name	Team member 1	Team member 2	Team member 3	Total rating
SPbSU Base	aid (2765)	ershov.stanislav (2739)	-XraY- (2551)	8055
MIPT Jinotega	zemen (2741)	ifsmirnov (2721)	Arterm (2506)	7968
ITMO University 1	izban (2762)	enot.1.10 (2550)	Belonogov (2545)	7857
Perm SU Indigenous	I_love_Tanya_Romanova (2650)	mmaxio (2576)	KuchumovIlya (2411)	7637
Saratov SU 1	HellKitsune (2537)	dans (2485)	IlyaLos (2349)	7371
ITMO University 2	BudAlNik (2450)	YakutovDmitriy (2422)	SpyCheese (2413)	7285
Belarusian SUIR	netman (2571)	andrew.volchek (2318)	teleport (2247)	7136
SPbSU 3	Kaban-5 (2474)	pavel.savchenkov (2431)	tunyash (2226)	7131
Ural FU Charmander	Tinsane (2438)	kb. (2363)	KungA (2262)	7063

Good luck to all participants
NEERCNews