-300?

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

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

probably its him

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?

No problem, rain will interupt the match

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

wow your rating graph is inspirational!!

Just go to a reality where you are already master.

Statements are translated into English for the round.

Of course

Agree with you

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

Obviously Contest

green Indians...

You can hack easy version only if you solved hard.

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

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

Check this case

6 3
aaa
aab
bbb
bcd
xxx
xxx

The answer is 4.

And D = B.

I really think it feels right like that

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

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.net/contest/1181/submission/55639812

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

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

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.

I pre solved it in an offline manner.

1. Sort all the queries in terms of time stamp.
2. 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.

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.

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

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.

Is the correct answer 110?

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.

Also, end cases were not covered in the pretests.

55636748

This doesn't look like a 100 lines.

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.

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)

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)?

It was div 2.

I think so div 3 is for school students

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

It really gave me unusual feelings!

xD

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.

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.

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.

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

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

Super Weak Tests for Prob B.

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.

Could someone plz explain this