### cdkrot's blog

By cdkrot, history, 2 years ago, translation,

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)

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.

• +187

 » 2 years ago, # |   +74 An unusual start time!!! Hope it give me an unusual experience .
•  » » 2 years ago, # ^ |   +135 -300?
•  » » » 2 years ago, # ^ |   +46 Bold of you to assume that's not my usual experience
 » 2 years ago, # |   -47 Ind vs Pak CWC 2019 at 3 pm IST . Hard choice for Indian Cricket Fans to participate in this round.
•  » » 2 years ago, # ^ | ← Rev. 2 →   -20 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
•  » » » 2 years ago, # ^ |   -6 Brother from another mother ... Haters gonna hate ....
 » 2 years ago, # |   +9 Who is Keldysh?
•  » » 2 years ago, # ^ |   +52 https://en.wikipedia.org/wiki/Mstislav_Keldyshprobably its him
 » 2 years ago, # |   +1 The time is very very very friendly to Chinese
•  » » 2 years ago, # ^ | ← Rev. 5 →   -32 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?
 » 2 years ago, # |   -52 Is it rated for everyone?
 » 2 years ago, # |   -44 Clashes with India Vs Pakistan :-/
•  » » 2 years ago, # ^ |   +22 No problem, rain will interupt the match
•  » » » 2 years ago, # ^ |   0 Rain may affect the later part of the game. The match will start at the usual time without any interruption.
•  » » » » 2 years ago, # ^ |   0 then interesting part to watch would be what crowd will do as a result!!!
 » 2 years ago, # |   -34 The number of reds in this post is "Huuuuuuuuge".Like if you read it like Trump xD.
•  » » 2 years ago, # ^ |   0 Least funny thing I ever read
•  » » 2 years ago, # ^ |   +120 No, I don't work together with him because he is quite nasty and rude.
•  » » » 2 years ago, # ^ |   +38 The guy won two consecutive ICPCs his ego must be huge.
•  » » » » 2 years ago, # ^ |   +57 vintage_Vlad_Makeev and vintage_Vlad_Makeev both won 1-1 ICPC.
 » 2 years ago, # |   0 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 :(
•  » » 2 years ago, # ^ |   +3 wow your rating graph is inspirational!!
•  » » » 2 years ago, # ^ |   0 That's true. I think so!
•  » » 2 years ago, # ^ |   +37 Just go to a reality where you are already master.
 » 2 years ago, # |   +8 please How many problems were prepared
 » 2 years ago, # |   +3 May I know how many problems are there and if the solution will be pubished?Sorry for my poor English :) Thanks
 » 2 years ago, # |   +10 Minor clarification, I'm new around here. Does All-Russian mean the questions will be in Russian only?
•  » » 2 years ago, # ^ |   +38 Statements are translated into English for the round.
 » 2 years ago, # |   +6 what is the score distribution??
 » 2 years ago, # |   -24 Is it a rated contest?
•  » » 2 years ago, # ^ |   +4 Of course
 » 2 years ago, # |   -8 I just hope it won't be a mathforces
•  » » 2 years ago, # ^ |   -8 Agree with you
 » 2 years ago, # |   +5 Can you let me know how many problems are there and what the score distribution is?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +19 It'll be announced 3 seconds before the start of the round.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +29 *10 seconds after round start :)
 » 2 years ago, # |   +3 hoping for specialist. prey for me.
 » 2 years ago, # |   -9 *me -> Wait a minute... *me -> Who are you? *to codeforces 567
 » 2 years ago, # |   0 Codeforces round vs India-Pakistan WorldCup match.Let's see what Indians prefer.
•  » » 2 years ago, # ^ |   +12 Obviously Contest
•  » » 2 years ago, # ^ |   0 green Indians...
 » 2 years ago, # |   +52 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).
•  » » 2 years ago, # ^ |   +42 You can hack easy version only if you solved hard.
 » 2 years ago, # |   +4 How to solve C ?
•  » » 2 years ago, # ^ |   +1 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
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +4 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).
•  » » » 2 years ago, # ^ |   0 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
•  » » » » 2 years ago, # ^ |   +1 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.
 » 2 years ago, # |   0 Hard, but interesting. Thanks!)
 » 2 years ago, # |   +3 So hard.55555~~~
 » 2 years ago, # |   -40
 » 2 years ago, # |   +24 So hard, feel like I am a retard
 » 2 years ago, # |   0 How to solve D?
 » 2 years ago, # |   +7 hard problem for B
•  » » 2 years ago, # ^ |   +1 Just use Java BigInteger with some cases handling
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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
 » 2 years ago, # |   0 Where does my solution for problem C go wrong: code
•  » » 2 years ago, # ^ |   +10 Check this case 6 3 aaa aab bbb bcd xxx xxx The answer is 4.
•  » » » 2 years ago, # ^ |   +6 Realized my mistake thanks..
 » 2 years ago, # |   0 let me summarize. B = C, C = D. right?
•  » » 2 years ago, # ^ |   0 And D = B.I really think it feels right like that
•  » » » 2 years ago, # ^ |   0 was that really? Why I didn't try that!
•  » » » » 2 years ago, # ^ |   0 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.
•  » » » » » 2 years ago, # ^ |   0 I found too much edge cases in C that I suddenly forgot what my idea was. And now, I got the idea unfortunately.
•  » » » » 2 years ago, # ^ |   +11 Euclid's first axiom : if A=B and B=C, A=C.
 » 2 years ago, # | ← Rev. 3 →   +33 Light-speed system test, I love it! WOW!Upd. It only used about 20 minutes! REALLY COOL!
•  » » 2 years ago, # ^ |   +11 because of the total number of submissions not huge, comparing for other contest
 » 2 years ago, # |   0 what is the fifth testcase in problem B?? any guesses?
 » 2 years ago, # |   0 weak test cases for B.... (T_T)
 » 2 years ago, # |   +6 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 I saw some AC submitions with search in the BIT, maybe it helps you ^^
•  » » 2 years ago, # ^ | ← Rev. 2 →   +9 I used a Fenwick tree to get the n-th city, and it has passsed. https://codeforces.com/contest/1181/submission/55639812There is no need to merge many Fenwick trees. Just maintain a simple sum-based seg tree.
•  » » » 2 years ago, # ^ |   0 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.
•  » » » » 2 years ago, # ^ |   +3 I solved it with segment tree, check my code.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +5 I used ordered set from pb_ds to solve k-th ordered statistics problem, check out my submission: https://codeforces.com/contest/1181/submission/55642500 Btw it's quite useful data structure, it can replace segment trees sometimes!
•  » » » » » » 2 years ago, # ^ |   0 Can you explain your solution? I was also trying it with policy data structures
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 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 :)
•  » » 2 years ago, # ^ |   +3 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
 » 2 years ago, # |   0 How to solve E?
•  » » 2 years ago, # ^ |   +42 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.
•  » » » 2 years ago, # ^ |   0 You can change set into list or 2 stacks and this solution will work in O(n log n).
 » 2 years ago, # |   0 How to solve D? can you help me.
•  » » 2 years ago, # ^ |   +3 I pre solved it in an offline manner. Sort all the queries in terms of time stamp. Interate through all the queries and merge the candidate cities in the process. I used two pointer like approach and fenwick tree to maintain this. You could read my submission first if it passes. I am currently away from my laptop.
•  » » » 2 years ago, # ^ |   0 Thanks
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 damn, got TLE using multiple policy based trees
 » 2 years ago, # |   +12 So I will wait for Div.3 to raise my rating xD
 » 2 years ago, # |   +20 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..
•  » » 2 years ago, # ^ |   +16 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.
•  » » » 2 years ago, # ^ |   0 I like your submission but I think this is easier to understand: https://codeforces.com/contest/1181/submission/55655895The difference between this submission and the one I had during the contest is that I tried to check everything separately, so the guy I stole this from in 3 lines what took me 15. I don't think its the lines, I usually like clean expanded code, I don't mind long code as long as its properly formatted, that's why I almost never use shortcuts, its very easy for me to write 150 lines, I'm a fast typewriter, its just that its very easy to get confused in such large code.The reason this guy pulled it off in 60 lines is because he's done tasks like these several times and for him he just needs to understand the problem, and then the problem is solved, the implementation is no problem.For me, I encountered this kind of problem for the first time ever, implementation is almost non-existent because I'm not exactly sure what to do. The greedy solution of taking the middle is obvious, figuring out leading zeroes and summing up strings (and not numbers) is difficult if you've never done it before, and I've also had lots of problems with a lot of corner cases, which this guy solved with his mini function which I did not have and I never thought of it.Anywho, I've learned about it and I'm going to be ready the next time such a task arrives, if they ever arrive.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   +1 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.
 » 2 years ago, # |   +2 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.
•  » » 2 years ago, # ^ |   +5 May be because you were using += and concatenating strings. Use string.substr function instead. https://codeforces.com/contest/1181/submission/55632022
•  » » » 2 years ago, # ^ |   0 You're right. Thanks.
•  » » » 2 years ago, # ^ |   0 but why substr takes less time than +=.
 » 2 years ago, # |   +61 Am I the only person who felt this contest was boring, with lengthy statements and implementations?
•  » » 2 years ago, # ^ |   +5 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.
 » 2 years ago, # |   +2 Do B have weak test casesI found many codes which fail on 5 10100
•  » » 2 years ago, # ^ |   -19 Is the correct answer 110?
•  » » » 2 years ago, # ^ |   0 yes
•  » » » 2 years ago, # ^ |   -12 why are you downvoting me? I asked him to check if my solution was giving the same output ...
 » 2 years ago, # | ← Rev. 2 →   +24 Fast Testing...Btw i did not like B at all
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 There's not much to test. Problem A from the last contest has more solves than this entire contest. In fact lets compare. 567 Div2 : 6578 solves566 Div2 : 16000 solvesTake away 2000-3000 solves on after-contest solves and the last round still has 2x more solves than this one.
 » 2 years ago, # |   0 power of system test -> 1200 — 3086
 » 2 years ago, # |   -17 0 doesn't have leading 0. but in problem B it have !!!!
•  » » 2 years ago, # ^ |   0 you sure?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +15 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.
 » 2 years ago, # |   +31 very hard and boring and just implementation
 » 2 years ago, # | ← Rev. 2 →   +68 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...
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Also, end cases were not covered in the pretests.
•  » » 2 years ago, # ^ |   +20 55636748This doesn't look like a 100 lines.
•  » » » 2 years ago, # ^ |   0 Actually, the solution will fail at '55'. Why do I know that? Because I made the same mistake. -_-!
•  » » » » 2 years ago, # ^ |   +11 but it's accepted...
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +14 Wow, that was unexpected.Added the test for the upsolving.
•  » » 2 years ago, # ^ |   +5 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.
 » 2 years ago, # |   +2 What is C test case 20? Anybody else fail on that case?
 » 2 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +6 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)
•  » » » 2 years ago, # ^ |   +12 I coded it and got ACCEPT just now. Without doubt this is a really cool problem, thank you!
•  » » 2 years ago, # ^ |   +6 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)?
•  » » » 2 years ago, # ^ |   0 I get it, thank you voidmax and nigus.
 » 2 years ago, # | ← Rev. 2 →   0 I had a mistake in adding long numbers. Very irritated now.
 » 2 years ago, # |   0 Could anybody please tell why this submission doesn't work for problem C? https://codeforces.com/contest/1181/submission/55645536
 » 2 years ago, # |   +3 Too bad. I can't solve more than 2 problems in a contest that's meant for school students.
•  » » 2 years ago, # ^ |   0 It was div 2.I think so div 3 is for school students
•  » » » 2 years ago, # ^ |   +3 It was based on All Russian Olympiad which is meant for school students.
 » 2 years ago, # |   +15 Time to become Expert!
•  » » 2 years ago, # ^ |   +22 Thanks to this contest.I eventually became "Expert" too.It really gave me unusual feelings!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +5 Congratulations!
 » 2 years ago, # |   +18 Problem A has 16 tags now. :O
•  » » 2 years ago, # ^ | ← Rev. 2 →   +41 xD
•  » » » 2 years ago, # ^ |   +1 And now 15 of that disappeared, the only left one is "math". X)
•  » » » 2 years ago, # ^ |   0 This seems more like a challenge than a tag.
 » 2 years ago, # |   +20 Next Div-3 contest is converted to the div-2 contest. lol...
 » 2 years ago, # |   0 There is change in figure of problem C,but no announcement of it -_-
 » 2 years ago, # |   0 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...
•  » » 2 years ago, # ^ |   +11 I guess ios_base with cin.tie would be enough
•  » » 2 years ago, # ^ |   0 Yea if ur a cin/cout user u should make it a good habit to use fast io, considering input is large most of the time...
•  » » 2 years ago, # ^ |   0 O3 pragma often hurts the runtime instead of improving it. It is the sync_with_stdio that did it for you.
•  » » » 2 years ago, # ^ |   0 -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.
 » 2 years ago, # | ← Rev. 2 →   0 Any hints for problem C? (not in a complexity of 1e9)
•  » » 2 years ago, # ^ |   0 n²log(n)= 660000 if you use segment tree to get how much you can extend the flag
•  » » 2 years ago, # ^ |   +1 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
•  » » 2 years ago, # ^ |   +5 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 We can do it in O(n*m) Hint : Consider only flags of width one.
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 Try for this test case 3 110 Your program gives the output 11 which is wrong because splitting 110 into 11 and 0 is not valid. Both numbers should be positive without leading zeroes.
•  » » » 2 years ago, # ^ |   0
•  » » » 2 years ago, # ^ |   +8 It should be 11 which is 10+1.
•  » » » 2 years ago, # ^ |   +11 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!
•  » » » 2 years ago, # ^ |   0 Sorry. 11 is the correct answer.
•  » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ |   0 Your logic is correct. I think the problem is with your add function. Just try this case 4 9911 
•  » » » » 2 years ago, # ^ |   0 But still, I don't know why this is giving a wrong answer on test 9 with a comment "Not a valid integer".
•  » » » » » 2 years ago, # ^ |   0 Could someone provide an explaination to this Thanks in advance
•  » » » » 2 years ago, # ^ |   0 Yeah i didnt take this case into account thanks!!
•  » » » 2 years ago, # ^ |   0 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).
•  » » » » 2 years ago, # ^ |   0 I did checked the 4 nearest possiblt splits to n/2 i think that should suffice
 » 2 years ago, # |   0 Weak test cases for problem B
•  » » 2 years ago, # ^ |   0 Im sorry didnt get you. Was asking for the mistake in my solution.
 » 2 years ago, # |   0 Had a screwed up contest, when will the editorials be out?
 » 2 years ago, # |   +22 Editorials?
 » 2 years ago, # |   +20 Why did this 55636748 get accepted when it is failing for test cases like 2 55 and 2 65 
•  » » 2 years ago, # ^ |   0 Super Weak Tests for Prob B.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 After big summation i forgot to process the carry: return (k?"1":"")+t; }new submission 55660679
 » 2 years ago, # |   +3 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.com/contest/1181/submission/55659680
 » 2 years ago, # |   0 How could one prove the corretness of greedy splitting in E?
•  » » 2 years ago, # ^ |   +3 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.
•  » » » 2 years ago, # ^ |   0 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?
•  » » » » 2 years ago, # ^ |   +3 You are absolutely right!)
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
 » 2 years ago, # |   0 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.com/contest/1181/submission/55663264
 » 2 years ago, # |   0 Nice contest, but way too heavy on data structures. My beginner students were struggle a lot.Even B uses big integers.
 » 2 years ago, # |   +3 Could someone explain why is it that in Problem C 10^9 operations also get accepted. Shouldn't that give TLE. Thanks in advance.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Could someone plz explain this
 » 2 years ago, # |   0 getting runtime error on test case 10 in problem D. https://codeforces.com/contest/1181/submission/55675351
 » 2 years ago, # |   0 Thank you for opening the contest.
 » 2 years ago, # |   +1 When a new girl enters the class. Boys be like: