Hi everybody,
This Sunday there will be a XVII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583).
Round will be held at Oct/20/2019 12:05 (Moscow time) and will last for 2 hours. Each division will have 6 problems.
Problems are prepared by wrg0ababd, vintage_Vlad_Makeev, DebNatkh, grphil, voidmax, vintage_Vlad_Makeev, volcolac, Sehnsucht, isaf27, cdkrot, Flyrise, budalnik, platypus179, Endagorion under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.
Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.
Good luck everybody!
UPD1: Winners!
Div. 1:
Div. 2:
- lolkekaidarbek
- qdd
- mathusalen
- conan1412yang99
- fauzdar65
- DeepThought42
- mikeleven
- AnnieCai
- liuandi6
- jyf111
Editorial will be published soon.
UPD2: Editorial
Score distribution?
does it matter?
So is it rated?
This is my first div 1 contest! UPD. Oh nope, too hard. My div1 contest flew away
How many shared problems are there between div1 and div2?
Each division will have 6 problems.
Question was about shared problems
Usually Div.2 C is the same as Div.1 A, so I think there will be four.
If my rating can increase 33 , I will be so happy XD Good luck everyone :)
Wow, we have the same rating! Hope for the best results :)
We failed together XD I believe we can do it soon:D
Did you get positive rating? It's bad luck for us QQ
I think that I will rest for some time, after taking a regional contest yesterday I'm a little tired to solve more problem
Hope u can do it as fast as possible :)
Wow..I think you should have a rest:D I will take part in a regional contest in Nanjing:) To be honest,I am nervous because I got a bad rank last regional contest:(
Wish u a good luck and making the best performance! :) Yesterday was my first time traveling to the other city for a contest, actually not having a good outcome make me a little sad
maybe I need some time to adjust myself...
I'll take your advice, thanks. XD
Multiple contest in a Queue.. Thanks codeforces ...
Yes!
A big team of the problem setter!
Also a friendly time for Chinese!
Relatable :(
Joining the club :|
And Really you become pupil..
Tonight I'm gonna sleep a lot :]
Lol, why are vintage_Vlad_Makeev and vintage_Vlad_Makeev both mentioned? Aren't they the same person?
They are different people.
vintage_Vlad_Makeev and team never won ICPC.
vintage_Vlad_Makeev and team won ICPC 18.
vintage_Vlad_Makeev and team won ICPC 19.
Updated.
vintage_Vlad_Makeev won ICPC 18. Not vintage_Vlad_Makeev.
my head hurts, is this div 1 E?
If only I knew this trick when I was competing.
All three ids link to the same page.. So it's three people using one account?
They are just 3 different handles of same account
Huh..are people openly allowed to create multiple accounts?
I hope I will become CM :)
Good Luck then
score distribution??
Hope to become Blue today. Good luck all!
Is the round rated?
Sure
score distribution ?
You'll find out in a minute, why so impatient?
About the order of difficulty......
Div1 C is the most frustrating problem ever made
wth is pretest 4
Pretest 4 (i think) is a situation when there actually can be a queue before the tank. Once you understand this situation, you understand the pretest.
(idk, maybe it's obvious, but I understood this only after like an hour of solving).
You need to read the statement multiple times — there is a queue involved too.
(Unfortunately, I made an implementation bug somewhere probably and failed on pretest 10, back to CM for me :/)
After two wrong submissions, I realized oh queue is also involved, then I got what is wrong with my code, but didn't get the time to implement it.
maybe sth. like
what should the answer to be for this instance
At 1-th minute, the fifth people go and take water. But at the 2-th minute, the fourth people want to take some water, and find that all people before him is sitting there, so he will go and wait behind the fifth person.
So actually there is also a queue in the place where the water is taken.
But during contest, I didn't realize there is a queue, and I checked my code for an hour, thinking there is nothing wrong. LOL
I felt this way about div1 B. Not sure if my solution or implementation was wrong but having to reconstruct made it much more work.
in Div2-C, what is pretest 7 ?
what is the idea of C ?
find a few facts then you can use backtrack and dp to find the answer I thing tutorial is published and you can read it to find your answer Good Luck ;)
difficulty balance be like
The one, who came up with such a great problem as Div1B : you can go and prepare problems for yourself.
how to solve easy version of it with n <= 500.
brute force the two swapping positions and then count the number of satisfied cyclic shifts.
I think in every new round setter competes with the previous setters for setting more difficult problems.
So I think I made a <= 3 character bug for 2 consecutive rounds......
This is what you call a truly imbalanced contest!
Wow, B was really hard and annoying for a div1B. Does anyone have an easy solution?
I only realised with 2 minutes left that the queue-stuff from C's statement was actually relevant, since for example passenger 2 could get ready to get water at time 1, and passenger 1 at time 2, then passenger 1 sees no empty seats in front of him and goes to the queue. Would have been nice to have a sample that shows that this is possible :/
OMG ! Div1 C = English test :/
In case too many passengers will go for boiled water simultaneously, they will form a queue
Ok, so there is a queue.
Nobody likes to stand in a queue.
Oh, so no queues?
There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them will go to the tank, while all others will wait for the next moment.
Alright, no queues it is.
This is what I was thinking.
This is exactly what I was thinking, too. LOL
I'm not sure if it's that hard as a solution, but it's easy to get lost looking for it. The quantity we're maximising is the number of minimum prefix sums. If we swap parentheses $$$i$$$ and $$$j$$$, prefix sums $$$i+1$$$ through $$$j$$$ change — either they increase by 2 or decrease by 2, depending on parenthesis $$$i$$$.
Obviously, if we don't select all occurrences of the current minimum, the resulting minimum of all prefix sums can only decrease, by at most 2. If we select it, then the resulting minimum can only increase or decrease by at most 2 as well. We can now try all possibilities for the resulting minimum and "increase/decrease", since there are $$$O(1)$$$ of them.
If we want minimum $$$m$$$ with "decrease", all prefix sums in the range $$$[i+1, j]$$$ must be at least $$$m+2$$$, at least one must be exactly $$$m+2$$$ and all prefix sums outside this range must be at least $$$m$$$. For a fixed $$$i$$$, we can choose the maximum $$$j$$$ such that the first condition holds, i.e. prefix sum $$$j+1$$$ is $$$m+1$$$, and check the other conditions. Since $$$m$$$ is fixed for all $$$i$$$, this runs in $$$O(N\log{N})$$$ and maybe even $$$O(N)$$$.
If we want minimum $$$m$$$ with "increase", all prefix sums in the range $$$[i+1, j]$$$ must be at least $$$m-2$$$, at least one must be exactly $$$m-2$$$ and everything outside this range must be at least $$$m$$$. It can be solved in the same way.
It needs more ideas, but they're not really that hard.
My ideas were using a stack:
If we push the string on to a stack and keep popping the matched ones, we will be left with $$$..))((..$$$ Then you swap the first and last of the leftover on the stack.
Do above with string s[n-1]s[0..n-2]. (to tackle $$$(()())$$$ case)
Print max of the two as answer.
You could further simplify it by assuming when we swap parenthesis $$$i$$$ and $$$j$$$, instead of the prefix sums $$$i+1$$$ through $$$j$$$ increasing by 2, the remaining prefix sums decrease by 2.
Now, if the original minimum is $$$m$$$, then you just need to consider 2 cases, where the minimum $$$m'$$$ is $$$m$$$ or $$$m - 1$$$.
The above simplification also reduces the search for the segment to $$$O(n)$$$, since for each case, you can just loop over the string and keep a count of elements exactly equal to $$$m' + 2$$$ and reset whenever you find an element $$$ < m' + 2 $$$
Submission for reference: https://codeforces.me/contest/1239/submission/62998813
I actually simplified by rotating the string so the minimum is $$$0$$$. Then we don't want to increase anything. Still, that's an extra idea and the shortest path to knowing you have a working solution is more along the lines of what I wrote — $$$O(1)$$$ cases and queries for range minimum.
First note that any string that can become balanced with one swap, can be rotated to be balanced. So no need to waste the swap here; find the prefix with the minimum sum
( = 1
,) = -1
and move it to the end.If the string is still not balanced, the answer is 0.
Otherwise we need to use the swap to maximize the number of balanced parts in the first level
(...)(...)(...)
.There are two cases:
(()x()()y)
: swapping x and y will move the parts between them to level zero and will create one more part to the left, so this swap adds 3 to the base answer.Swapping the two ends of any part in level 0
(...)
will leave 1 + the number of parts between them. For example(()())
->)()()(
which is()()()
.In a single pass with a stack, you can consider the two cases for all ends and maximize the answer: 63011541
Div 2 D, what would be a correct way to compute a string's beauty? I've tried finding the string's longest suffix where the number of opened parenthesis is greater than the number of closed parenthesis, cycle the string so that become a prefix, then find out the number of concatenations this new string is made with (0 if the string is not valid). Wrong answer on test 8.
You mean div2 D
Oh yeah, thanks mate
Isn't the number of 0's in the prefix sum of a string equal to its beauty?
I did finding and counting all such suffixes such that $$$N_{closed} - N_{opened}$$$ in the suffix is less or equal than $$$min(N_{opened} - N_{closed})$$$ on all prefixes. Also make sure that overall $$$N_{opened} = N_{closed}$$$.
If the string contains an equal number of 1's and -1's, the beauty equals the number of minimum prefix sums. However I think what you described should work as well. Maybe there's a bug?
Could be a bug, I'll wait to see the test it fails on and try debugging with it. Thank you for your explanation!
Using stack and then while inserting least recently used opening bracket may be tracked and counter increased when it matched. (for D1, do for all n rotations)
String's beauty is number of minimal balances, if balance of all string is 0; (Balance is number of '(' on prefix minus number of ')' on prefix)
how to solve div2 c ??
Bruteforce + finding pattern for answer
I sent $$$\big(m$$$-th Fibonacci number $$$+$$$ $$$n$$$-th Fibonacci number $$$- 1\big)\cdot 2$$$. No idea why.
Wow, that's a very clever approach, and a valid one too i think according to dp states... With matrix exponentiation we could have even solved for very large n,m then...
Yes, with $$$n,m \le 100000$$$ you can just calculate them directly.
Yes
Was trying to make the product of Fibonaccis work. Can't prove why this works when n != 1 and/or m != 1. Any suggestions?
Consider there is only 1 line. You can use a easy DP to get that there are $$$S$$$ ways to color the first line. Except ways $$$101010...$$$ and $$$010101...$$$ there are $$$S-2$$$ ways to color the line with surely $$$\ge$$$ one pair of $$$00$$$ or $$$11$$$.
For these $$$S-2$$$ ways of coloring the first line ,because they contain substrings $$$00$$$ or $$$11$$$ ,there is excatly $$$1$$$ way to color the rest for each ways. So the contributions to the answer is just $$$S - 2$$$
For $$$101010...$$$ and $$$010101...$$$ ,in the rest lines ,there is no way to color $$$00$$$ or $$$11$$$ in a line but maybe in a column. And you can use the same DP to solve it.
Did anyone try hard to push cubic solution for Div2D1?
My solution is cubic, it passes pretests
Isn't the intended complexity cubic? My cubic solution passed pretests in 529 ms.
My cubic is TLE#8. Ok, maybe my solution isn't as cubic as it need to be.
$$$O(n^3/2)$$$ will pass
HOW TO SOLVE DIV 2C?
try to solve the problem for 1 * m table . then you can see that in only 2 cases second row isnt unique
Try to make just 1 contiguous equal pair, you'll find that you cannot place any vertical contiguous equal pair if horizontal is present and vice versa, ie, the other one is alternate.Also a row or a column can only repeat at max 2 times in an assignment, and there are only 2 types of those, alternate, so I ran a dp of n*2*2, and another along column m*2*2, and just added their final states at n,m respectively.States were (position, current type of row(column), length of contiguous sequence till then). Also at the end remember to subtract 2 from answer so as to avoid the repetition of case when no contiguous blocks are equal.... Hope it helps!
You forgot to sort problems
Every contest seems to be highly unbalanced after the tourist balanced round
Hi,
Regarding Div2D, Can it be proved that a string with equal number of '(' and ')' can be made correct by a certain k-rotation?
Yes, if you push given string on the stack, and pop matching ones, you will be left with something like $$$...)))(((...$$$ always, and then you can rotate the mid point to balance everything.
Oh. That was easy. Thanks!
Yes, you can pick a k-rotation, such that count of '(' minus count of ')' on prefix n-k is minimal
Can I meet Balanced Problem Set ever??
How to solve div2d easy in O(n3) time.
How to solve Div1 D/Div2 F? Does any greedy work for the case when the bipartite graph is completely connected , i.e., just 1 connected component ?
Edges are actually directed so think of SCC. There's an answer iff there's more than 1 SCC.
Ya got it, thanks. I wasn't considering directed edges and hence was always getting answer for more than 2 connected components and wasn't able to think how it works for just 1. But on scc the same logic works, just answer no for 1 scc.
Damn, I was thinking of SCC number but for some reason I directed some edges in both directions >_<
My solution is, given the input graph, you just need to create strongly connected components and then, if there is only one, output "NO".
I think I can get substantial increase in rating in the next round given the distance from my average rating -_-.
OMG!!!! problem C takes me over 1 hour,but D only 30 minutes.unluckily when I pass all the examples in problem D ,it's 3 minutes after the contest. :(
Don't you mean D1? D1 is less points than C.
Yes,however I still get TLE after contest. :(
Strong pretest and no successful hacking attempt in div 1. Yeah!
Hardest div1A for me, back to div2..
welcome :)
This is the first time I saw Div1A and Div1D of the same diffculty.
This is the first time I saw Div1A much harder than Div1D.
Today I learned that Python has a preset recursion limit of 1000. Cost me Problem C lol
This round reminds me of the Codeforces Round 588 (Div. 2) on which the problem set was created by Radewoosh
A random picture
What's wrong with that, if B and C were both 1250?
In fact D1D is also random, but it's not strictly a "random picture" discribed in D1A.
I think the main reason is that D1D is 2000, if it's 1250, we'll have a random picture with 3 columns.
This guy(gal?) randoms
Great contest, fast testing (during and after). Fun problems that required more thinking than edge-cases and writing. Thank you all involved in writing, keep em coming :)
These days are crucial for contestants with poor math skills :|
Damn right! Brother
It was the best round I had participated in from a long time
I believe today's contest (Div. 2) was awesome, for me personally at least, with less system test failure's and a good and simply code-able problem C.....Looking forward to such and even better contests in future on codeforces!
This round reminds me of Codeforces Round 543 (Div. 1, based on Technocup 2019 Final Round). How on earth is D worth more than B?
why is this submission got WA on pretest 4?
I thought passanger 1 gets the boiled water at 2000000009, because after the first person (idk which index, but seeing the result has suffix 9, it must be 9), every passanger already wanted to take the boiled water, but the leftmost (index=1) will be getting the boiled water first.
Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.
Why do cubic solutions pass on D1?
500^3 == 1.25*1e8 It is well within time limit
My whole life was a lie.
Yes! despite getting to bruteforce solution I didn't submit cause of above calculation and given 1s time limit :(
Div 2 Problem E
Can someone justify why 3rd value in the answer is less than the 1st one?? Shouldn't it be greater?
Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.
I have the same output like you ??? I don't know where i was wrong in reading the statement :V But i don't know why the answer can reach 1e10 when p<=1e9 and ti<=1e9 :V It doesn't make any sense ???? Pls explain too me .Tks you ans sorry for my poor English
There is a mistake in the statement of problem D. Instead of
"Cyclical shifts i and j are considered different, if i/=j"
it should be
"Cyclical shifts by i and j are considered different, if i/=j".
It can be deduced from the examples though.
how can we prove the solution for div2C ?
If you filled the first row cells and first colm cells you will find that there is only one way to fill the remaining cells
.
TIL that seats can be busy.
I found these submissions: 62996146 62993334. It really looks like they were cheating.
Codeforces plagiarism checker is really very bad that they can spot these same codes with some variables changed. Nice done buddy, I think admin must look into this once.
The tutorial of C said that it's a strip problem and the solution seems easy... But the question is what is a strip prolem... Am I retarted?
You should look on case when n = 1. It will help to understand whole problem.
It can be solve by easy dp.
dp[i][j] — number of such coloring, if last j colors are equal.
The same question =))
O(n) solution for div2.B is to use count sort ?