Hi!

Tomorrow will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! Olympiad is conducted under the guidance of the Moscow Olympiad Scientific Committee, in particular GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot and, of course, Helen Andreeva.

We are happy to announce the codeforces round based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Jun/16/2019 12:35 (Moscow time). You might have already participated in rounds based on the school olympiads, prepared by Moscow Olympiad Scientific Committee (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545)

The problems of this olympiad were prepared by voidmax, alexey_kuldoshin, ch_egor, budalnik, achulkov2, manoprenko, vintage_Vlad_Makeev, Endagorion.

Thanks KAN for his help in organizing the Codeforces version of this contest and MikeMirzayanov for the Codeforces and Polygon.

Also I would like to thank the Tinkoff company and personally Tatyana Kolinkova for organizing the onsite competition.

Good luck!

**Scoring: 500-1000-1500-1750-(2000+750)**

**upd.** Congratulations to winners!

Div. 2:

unofficial Div. 1:

The editorial will be published soon.

**upd.** the editorial was published.

An unusual start time!!! Hope it give me an unusual experience .

-300?

Bold of you to assume that's not my usual experience

Ind vs Pak CWC 2019 at 3 pm IST . Hard choice for Indian Cricket Fans to participate in this round.

for dislikers: soccer world cup final attracted 1.6 billion viewers while today's India vs Pak crikcet match expected to attract 1.5 billion viewers..so dislikers do respect other's choices as well.. although i will be going for the contest :P

Who is Keldysh?

https://en.wikipedia.org/wiki/Mstislav_Keldysh

probably its him

The time is very very very friendly to Chinese

So What? It is equal to say, "Although the time is not friendly for many other people, but the time is friendly for Chinese." Doesn't it?

Clashes with India Vs Pakistan :-/

No problem, rain will interupt the match

Rain may affect the later part of the game. The match will start at the usual time without any interruption.

then interesting part to watch would be what crowd will do as a result!!!

Glad to see vintage_Vlad_Makeev and vintage_Vlad_Makeev working together

No, I don't work together with him because he is quite nasty and rude.

The guy won two consecutive ICPCs his ego must be huge.

vintage_Vlad_Makeev and vintage_Vlad_Makeev both won 1-1 ICPC.

Another round I will miss because of university exams :(

These stupid exams came when I am that close of becoming master, My rating in 2080 :(

wow your rating graph is inspirational!!

That's true. I think so!

Just go to a reality where you are already master.

please How many problems were prepared

May I know how many problems are there and if the solution will be pubished?

Sorry for my poor English :) Thanks

Minor clarification, I'm new around here. Does All-Russian mean the questions will be in Russian only?

Statements are translated into English for the round.

what is the score distribution??

Is it a rated contest?

Of course

I just hope it won't be a mathforces

Agree with you

Can you let me know how many problems are there and what the score distribution is?

It'll be announced 3 seconds before the start of the round.

*10 seconds after round start :)

hoping for specialist. prey for me.

Codeforces round vs India-Pakistan WorldCup match.Let's see what Indians prefer.

Obviously Contest

green Indians...

How does hacking work when there are two (easy and hard) versions of the same problem? They have to be connected somehow because somebody would be able to solve easy with brute force, lock it and check codes to find some which work even for hard version (and learn how to solve it).

You can hack easy version only if you solved hard.

How to solve C ?

I found every 1 column flag and found out how wide they could become.

for every such flag, we get width*(width+1)/2 different possible flags.

Yes, |: 10^9 operations but it passed

You can sort the list of 1 column flags in such a way that corresponding flags end up next to each other (sorting by row and column). Then it is easy to check how far they extend horizontally. This was quick enough that even my python solution got accepted (without 10^9 operations).

Hey, can you please help me with my code. I got a TLE by using brute force (10^9 operations).

My code: https://ideone.com/iDkAwr

10^9 is already a lot. Using a map on top of that isn't helping.

Instead of using the map, I simply edited the map and zeroed out the positions that were already calculated and it barely passed.

Hard, but interesting. Thanks!)

So hard.55555~~~

So hard, feel like I am a retard

How to solve D?

hard problem for B

Just use Java BigInteger with some cases handling

Big integer summation. use this. https://www.geeksforgeeks.org/sum-two-large-numbers/ I didn't even know how to implement summation .And, find out the index where s[i] != 0 near to the middle. then split the string and use that link for summation

Where does my solution for problem C go wrong: code

Check this case

The answer is 4.

Realized my mistake thanks..

let me summarize. B = C, C = D. right?

And D = B.

I really think it feels right like that

was that really? Why I didn't try that!

Yeah I just read it and I think it was! It was a huge mistake not to start with it after A.

Might take some coding but no edge cases like in B & C.

I found too much edge cases in C that I suddenly forgot what my idea was. And now, I got the idea unfortunately.

Euclid's first axiom : if A=B and B=C, A=C.

Light-speed system test, I love it! WOW!

Upd. It only used about 20 minutes! REALLY COOL!

because of the total number of submissions not huge, comparing for other contest

I wrote an O(nlogm+mlogm+qlogm) solution to problem D by merging some segment trees link. I thought that would pass under a TL of 2.5s for n,m,q<=5e5. However, it got a TLE. I tried all methods I know to make it run faster but it always gets TLE on pretest 10 or 11. I'm just wondering why a nlogn solution gets TLE. Is the constant of my code too big or a solution with a better complexity(O(n) maybe?) exists?

Sorry for my poor English.

I saw some AC submitions with search in the BIT, maybe it helps you ^^

I used a Fenwick tree to get the n-th city, and it has passsed. https://codeforces.cc/contest/1181/submission/55639812

There is no need to merge many Fenwick trees. Just maintain a simple sum-based seg tree.

Thanks, I've discussed that with my friends and they told me about the solution with BIT. I think maybe the constant of segment trees is too big.

I solved it with segment tree, check my code.

I used ordered set from pb_ds to solve k-th ordered statistics problem, check out my submission: https://codeforces.cc/contest/1181/submission/55642500

Btw it's quite useful data structure, it can replace segment trees sometimes!

Can you explain your solution? I was also trying it with policy data structures

Well, let's do the following: let's maintain ordered set $$$d$$$ that represents all cities with the smallest number of hosting days. If the current year is $$$timer$$$, then in the next $$$d.size()$$$ years these $$$d.size()$$$ cities wiil be selected to host the olympiad according to their indices(in ascending order). And this process continues until there is other city to add to $$$d$$$. Thus, we can answer queries $$$q_i\in[timer, timer + (cur - prev) * d.size())$$$, where $$$prev$$$ is number of hosting years of all cities in $$$d$$$ and $$$cur$$$ is first city with number of hosting years larger than $$$prev$$$. For query $$$q_i$$$ the answer is simply a city with order of $$$((q_i - timer)\mod{}d.size())$$$ in ordered set $$$d$$$. Then we can add new cities(cities that hosted $$$cur$$$ times) and continue this operation.

Hope this was helpful, I struggled with English and LaTeX very much :)

I solved it in $$$O(q log(q) + m log(m) + q log(m))$$$ using Treap but finished the implementation when the contest was already finished :( 55644594

How to solve E?

Let's solve the problem recursively. If $$$n=1$$$, the answer is "YES". Otherwise, we have to find a horizontal or vertical line which separates rectangles into smaller ones without intersecting any of them. If no such line exists, the answer is "NO". If it exists, we can greedily assume that it was the line of the last merge and solve problems recursively.

So, $$$O(n^2)$$$ (maybe $$$O(n^2 \cdot \log(n))$$$) is easy. How to speed it up? We'll try something like "smaller to greater", but in reverse. As we'll split the problem into two smaller ones, we can do it in complexity $$$O(size\_of\_the\_smaller\_part\_after\_the\_split)$$$ (possibly multiplied by $$$O(\log(n))$$$) and the overall complexity will be good. The problem is that we don't know if the line that we are looking for will be horizontal or vertical and we don't know if it'd be closer to the beginning or to the end of the list of sorted rectangles.

The solution is to try every option at the same time. Maintain $$$4$$$ sets, one for each possibility, go through each of them and if you'd find a good line, stop here, split each set into two smaller ones and the complexity will amortize.

You can change set into list or 2 stacks and this solution will work in O(n log n).

How to solve D? can you help me.

I pre solved it in an offline manner.

You could read my submission first if it passes. I am currently away from my laptop.

Thanks

So I will wait for Div.3 to raise my rating xD

B was incredibly time-consuming in my opinion. I hate strings, it took me 150 lines of code to solve B and I couldn't even submit it in time. After half an hour of coding B I realized that there's like a 100k digits and I can't sum the string as numbers but as strings, so this was my first time ever doing this and i hate it, I hate strings, they're just tedious things that are very easy to mess up because there's so many things that you need to do with strings to manipulate them that its very easy to mess up the code and then debugging takes a lot of time. And I unknowingly solved A within 10 minutes but because I forgot about long long, I thought that there was a math error in my code, so I just skipped A.

At least I learned something..

You should study some accepted submissions and learn simpler ways to approach the implementation. Then you can stop hating strings!

Here is my B. ~40 lines, 15 min.

String manipulation is much less annoying in python (in my opinion). My solution was less than 30 lines (and wasn't really optimized), so you might consider using a higher level language. Edit: 13 lines after cleaning up my code a little.

Such problems are easier to implement using languages which already have built-in support for large integers, like Python and Java.

It is always handy to learn the basics of such language (assuming you use C++).

55623625 Python solution in 8 lines.

About problem B. The complexity of adding 2 strings is O(max length of 2 strings). I added 2 trings with max length <1e5 three times but I got TLE. I couldn't solve B. Can anyone explain? Thank you very much.

May be because you were using += and concatenating strings. Use string.substr function instead. https://codeforces.cc/contest/1181/submission/55632022

You're right. Thanks.

Am I the only person who felt this contest was boring, with lengthy statements and implementations?

I'm not rated high enough to give an expert opinion about this contest, but from my perspective, this was a pretty lame contest. One or two more sentences in each problem to clear some stuff up would go a long way to helping us solve these problems, I feel like some of the information in the tasks were withhold from us just so the tasks would be harder to solve.

Do B have weak test cases

I found many codes which fail on

5 10100

Is the correct answer 110?

yes

why are you downvoting me? I asked him to check if my solution was giving the same output ...

Fast Testing...Btw i did not like B at all

power of system test -> 1200 — 3086

0 doesn't have leading 0. but in problem B it have !!!!

From the problem statement: "To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a POSITIVE integer without leading zeros." 0 isn't a positive number.

very hard and boring and just implementation

B is not fair for C++ ( and other programming languages which do not have bigint library ) programmers.

I solved B using python in 40 lines while C++ needs 100+. ps. sorry for my poor English...

Also, end cases were not covered in the pretests.

55636748

This doesn't look like a 100 lines.

Actually, the solution will fail at '55'. Why do I know that? Because I made the same mistake. -_-!

but it's accepted...

Wow, that was unexpected.

Added the test for the upsolving.

Honestly, it wouldn't take more than 3 one liner functions to get the same features.

But I agree, it is unfair to C++ users.

they'd have to spend precious minutes writing those functions and it could make the difference between rank 400 and rank 14.

What is C test case 20? Anybody else fail on that case?

E1 can be solved by simply dividing, now the problem is how to get an $$$O(n \log n)$$$(maybe) algorithm to solve E2.

Pls help me.

Let’s optimize dividing. When we are finding cut, we do it in O(number rectangles in one part). Let’s go in 4 directions in one time and cut min part.

Also, when we found cut, we should erase one part and keep correct orders in 4 directions. We can do it using stack or list.

This solution works in O(n log n). (We gave here TL from the original contest, where you can solve this problem with python.)

(Sorry, more details will be in editorial)

I coded it and got ACCEPT just now. Without doubt this is a really cool problem, thank you!

hint: for a subset of rectangles $$$A$$$, you probably have some function $$$solve(A)$$$ which splits $$$A$$$ into $$$B_1, B_2$$$ and returns $$$ solve(B_1) \text{ } AND \text{ } solve(B_2) $$$. The problem is that this splitting takes $$$O(|A|)$$$. Can you make it take $$$O(min(|B_1|, |B_2|))$$$ instead (with some log-factor)?

I get it, thank you voidmax and nigus.

I had a mistake in adding long numbers. Very irritated now.

Could anybody please tell why this submission doesn't work for problem C? https://codeforces.cc/contest/1181/submission/55645536

Too bad. I can't solve more than 2 problems in a contest that's meant for school students.

It was div 2.

I think so div 3 is for school students

It was based on All Russian Olympiad which is meant for school students.

Time to become Expert!

Thanks to this contest.I eventually became "Expert" too.

It really gave me unusual feelings!

Congratulations!

Problem A has 16 tags now. :O

xD

And now 15 of that disappeared, the only left one is "math". X)

Next Div-3 contest is converted to the div-2 contest. lol...

There is change in figure of problem C,but no announcement of it -_-

Got tle on D, put #pragma GCC optimize("O3") and ios_base::sync_with_stdio bla bla bla and got AC with 889 ms.... damn it hurts...

I guess ios_base with cin.tie would be enough

O3 pragma often hurts the runtime instead of improving it. It is the sync_with_stdio that did it for you.

`-O3`

does wonders on brute-force solutions (just ask MrDindows) but it won't do much to improve the running time of a segment tree, for example.Any hints for problem C? (not in a complexity of 1e9)

n²log(n)= 660000 if you use segment tree to get how much you can extend the flag

Build 2d-prefix array for each character, then consider each $$$(i,j)$$$ as the bottom left corner of the flag. Binary search the heigh of one stripe — the maximum value of $$$h$$$ such that all characters from coloumn $$$j$$$ in range $$$[i, i + h)$$$ are equal. Then check wherher all characters from $$$j$$$-th coloumn in ranges $$$[i+h, i+2h)$$$ and $$$[i + 2h, i + 3h)$$$ are equal. If not — $$$(i,j)$$$ can't be the bottom left corner of the flag. Otherwise use binary search again to find the maximum value value of $$$w$$$ such that all characters in rectangles $$$[(i,j), (i+h-1, j+w-1)]$$$, $$$[(i+h,j), (i+2h-1, j+w-1)]$$$ and $$$[(i+2h,j), (i+3h-1, j+w-1)]$$$ are equal. (Here $$$[a,b]$$$ means the bottom left and top right corners of the rectangle). There is exactly $$$w$$$ possible flags having cell $$$(i,j)$$$ as their left bottom corner, add this value to the answer and procced to the next cell.

Here is a bit prettified version of my solution: https://ideone.com/dKdcpu

For each j from 1 to m, we count number of submatrices which left most vertices are in column j. To do so, we divide column j into a list of segments of consecutive characters, for example: 'aabbbcd' -> (1,2) (3,5) (6,6) ('aabbbcd' is characters of column j)

For each 3 consecutive segments, let x, y, z be lengths and c1, c2, c3 be single characters of 1st, 2nd and 3rd segment. For above example, with segments 2, 3, 4, we have: x=3, y=1, z=1, c1='b', c2='c', c3='d'.

Now we can get the start of correct flags here if c1 != c2, c2 != c3, x >= y, y <= z. Then we can do binary searching to find maximum length which we can append from the start to get a correct flag. Assume it's d, if d = 0 then it means we can't append anymore from the start, and result += 1 (the start). So result += d + 1.

When do binary searching, we have to check whether all three strips have only one character. To do so, we can precalculate 2d prefix sum of 26 characters.

We can do it in O(n*m)

Hint : Consider only flags of width one.

Could someone please help me figure out what is wrong in the 9th test case in problem B. Here is my submission 55649908. Thanks in advance.

Try for this test case

Your program gives the output

`11`

which is wrong because splitting`110`

into`11`

and`0`

is not valid. Both numbers should bepositivewithout leadingzeroes.It should be 11 which is 10+1.

What you talking about? In this particular case correct answer will

`11`

cuz we separate 110 to 1 and 10 and sum of this two numbers its 11, dont post stupid idea if dont realy sure about it!Sorry.

`11`

is the correct answer.My logic was to look at the correct split point as close to mid point. Is this logic correct Also im not understanding the comment on my answer Could someone please help

Your logic is correct. I think the problem is with your add function. Just try this case

But still, I don't know why this is giving a wrong answer on test 9 with a comment "Not a valid integer".

Could someone provide an explaination to this Thanks in advance

Yeah i didnt take this case into account thanks!!

I didn't check your code, but maybe it is wrong because you need to check splitting not only in mid index (if possible), but in mid + 1 and in mid — 1 too (again, if possible).

I did checked the 4 nearest possiblt splits to n/2 i think that should suffice

Weak test cases for problem B

Im sorry didnt get you. Was asking for the mistake in my solution.

Had a screwed up contest, when will the editorials be out?

Editorials?

Why did this 55636748 get accepted when it is failing for test cases like

and

Super Weak Tests for Prob B.

Can anyone help me with a test for problem B? This is my solution and i can't find where the bug is https://codeforces.cc/contest/1181/submission/55659680

How could one prove the corretness of greedy splitting in E?

Let’s look on some correct splitting. What changes then we cut some line? Some next cuts will split set of rectangles in two parts with empty one. All those cuts should be deleted. After deleting correctness doesn’t change.

Please, tell me if i understand well.

If we look at some correct splitting, we can add this extra horizontal or vertical line, and then some regions may be empty ( without castle ). We can always merge this regions with their neighbours by deleting some parts of existing lines in order to achieve one castle in one region. Is this correct, or am I missing something?

You are absolutely right!)

Ok, thank you for your reply.

There is actually one more thing im not sure about. After doing this operations shape of some regions may change. How do we ensure that it is always possible to merge them one by one ( finally achieving the whole rectangle ). Some of them will change they size so why is it always possible to obtain correct soltuion? Some of the initial mergings may be not available now.

Can you guys help me to debug my solution to problem D? I used a treap to update and find the kth smallest. Code : https://codeforces.cc/contest/1181/submission/55663264

Nice contest, but way too heavy on data structures. My beginner students were struggle a lot.

Even B uses big integers.

Could someone explain why is it that in Problem C 10^9 operations also get accepted. Shouldn't that give TLE. Thanks in advance.

Could someone plz explain this

getting runtime error on test case 10 in problem D. https://codeforces.cc/contest/1181/submission/55675351

Thank you for opening the contest.

When a new girl enters the class. Boys be like: