Hello everyone!

We invite you to participate in Codeforces Round #245, scheduled for Sunday, 11th May at 7:30 MSK. This is the fourth round I write for Codeforces. After the last round your upvotes helped me get into the Contributors Top 10. Thanks for all your good remarks; I'll try and do my best in order for this round to be at least as good as the previous one.

This round is prepared by my friend Ioan Petcu (author of D1 E) and I (all problems, except D1 E). We've chosen the problems to be as diverse as possible — no two problems will share the same programming technique. As the problems are varied, we hope you'll find at least one problem of your taste. The main character is Iahub, currently the number one ranked contestant in the Romanian selection camps for IOI. After reading the problem statements, you'll see what the life of a very good Romanian competitive programmer is like (just kidding, it's just my evil imagination).

This round wouldn't have been possible without the people that helped me test it: Gerald Agapov (Gerald), Damian Straszak (DamianS), Dan Alexandru (DanAlex) and Vlad Badelita (vladb). As always, we’d like to thank Mike Mirzayanov for creating the Polygon system and Codeforces plaftorm and to Delinur for translating the problems in Russian.

We wish high ratings to everyone and, above all, have fun!

**UPD** Score Distribution

Division 1: 500 1000 1500 2000 **2000**

Division 2: 500 1000 1500 2000 2500

I apologize for all technical issues during the round, from the ambiguous problem statements to very easy problem D1 D. In my trial to invent a nice task, I didn't see that straight forward solution for it and I have no excuse for this.

**UPD** Winners

Division 1:

Division 2:

**UPD** Editorial

**UPD** Statistics

Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants.

Good to see another Romanian made round. And it's even 1/3 Mures (my home region)

Thanks for the contest! Long time no see:) And tonight I' ll try my best to reach purple( well, not pupil) God bless me:p UPD: I' m so surprised to realize that tomorrow is my birthday too, what a coincidence!

Happy birthdays ..

A contest after 9 days. :) GL HF!!

We really expect to see what the life of a very good Romanian competitive programmer is like :)

I think the problem statements about programmer will be very different && interesting. May be 's counting girlfriends, scheduling for date with girls or some games with girls... haha, just kidding.

Im bored

Why there arent so much comment?

A rare occasion: the points' distribution appeared more than 1 minute before the contest :D

And yet another: there are exactly 1000 registrants in div1!

It seems E question will be easy

I dont want to be first again man

Easier it E(Div1)

Ok ,i'll solve

As you know no problem for me :)

Div 1 начало в 19:40

Div 2 начало в 19:30

UPD. исправили

As usual, delayed :D

why the 10 minutes delay?

Because I had to do my dinner.

Although it was not official, still thanks for consideration Codeforces.

And I needed some time to wash off the sand, running back from the beach :)

I think, server is busy.

Delayed?

Like other contests its delayed

Delayed :(

Good start!

Same as usual

delay delay delay

I think the "usual time of CF Round" should be 7:40 instead of 7:30

Then all of the contests start at 7:50 :D

If so, I think the "usual time of CF Round" should be 7:50 instead of 7:40

Then all of the contests start at 8:00 :D

Just a few recent contest.

Another time... 10 minutes delayed...

For me it showed that it has started.

So, do it!

delay :'(

Looks like somebody important rang and said he was late to register.

maybe tourist ?

nope.

Exacly 1000 participants in div1 :O

Wow, at the same second! :D

What, 999?! I thought it was final..?

Exactly 1000 div1 registrants! :D

It shows 999 to me.

now it is 999 registrants in div1...... I think someone cancel it....

1000 coders for div1 !!!! what an amazing contest~!!!! thanks for the delay!

Exactly 1000 people registered for div1.

exactly exactly exactly

It's contest? :)

I don't know

"As the problems are varied, we hope you'll find at least one problem of your taste."- are you kidding, fchirica?

leaving contest arena, this contest is not for me. :(

what the heck ? >.<

Is Div.2 really Div.2...?

I agree...

I dont understand the problem A div2. Who are the red and blue balls??. I am crazy with this problem. Please, for the next competitions that you should better the content of problem. Now, I see the clarifications of problem A, is very late and I lost many points, WDF!!!!

a

Wrong answer on pretest 2

Wrong answer on pretest 2

Wrong answer on pretest 2 . . .

:|:|:|

What is the solution for problem A Div.2??? A is the hardest problem today:)

sort

Oh, No. It's a very stupid bag :(

Sort point by coordinate and 0 1 0 1 0 1 0

1) Sort points by coordinate. 2) Simply put 1 0 1 0 1 0 1 ... 3) Sort points by order in input 4) Write them to output

I wrote only 1 0 1 0 1 0 1... without sort :(

I did it and got Wrong answer on test 3. But when I sort, I get Accepted.

why sort?

Counterexample (without sorting gives the wrong answer): 3 0 3 1 2

Omg it seems so obvious now...

Hint[1]: you can totally ignore the segments...

Hint[2]: sort

What the heck is A? Could not come up with any idea :-s

0101010101 And sort them by id afterwards

why can't we use all balls of the same color?

Because for example if interval is 1..3, and balls are at 1,2,3 and all of them are black, and no red, then inequality |3-0|<=1 is incorrect.

thanks, I misunderstood the task, I thought ri, bi are coordinates of the balls (facepalm)

So I was not the only one to think on the same lines :)

Though I made the correction but could not get an AC because of the sort thing.

I think D should've been B. (div1) Or A. Ok, not A, but it's seriously easy to solve. I saw several solutions that made use of the fact that |

A[i]| ≤ 10^{4}— solutions, which pass maxtests (easy to make here) in slightly under 2 seconds.Really? >_>

Really :(

Unfortunatelly, I've tested this approach during challenges only — it passes in 1.3s in my implementation.

I rewrote LLI_E_P_JI_O_K's 6595981, ran it on "40000 40000x10000" and got 686 ms using the CF Custom invocation. On my computer, it takes 1200 ms on that test and 3200 ms on "100000 100000x10000", so it should be 1830 ms on CF, +- something in the order of 10 ms.

Unbelievable if O(N*max(A)) solutions could be passed systest.

not max(A) but min(A) (although it's not key ...

min(A) = -10000 => O(-1e9) ??? Faster than every algorithms?

min(abs(A)) ......

At the beginning, I was expecting it might be something related to dp convex hull (yeah, it's problem D) and tried to play around with the formula to solve it. And you probably know how it feels when I finally got the solution...

Really sorry for that. Didn't notice such a solution. =(

Why have O(nlogn) solutions timed out?

Right

O(n*logn) solutions haven't timed out ;)I mean that as someone has already noticed it's easy to make a mistake in this algorithm in this problem by writing somewhere

dist^{2}instead ofdistor vice versa.Yeah you are correct!

Even if we suppose that simple solutions (such as

O(N|A|_{max}) solution with some heuristics) doesn't work, I think D was too well-known for a D. It was just the classic closest pair of points problem. Some participants might have copied the implementation of this problem and submitted..I try to hacking a submission when the countdown show 15sec, then when the hacking is running contest going to be ended, what happen with my hacking? It show "Status: challenge-other"

Why doesnt this work for A?

If we alternate the points 0 1 0 1 0 1 then no segments can have the difference more than 1.

That's right. Sort them by id(input order) then

Ah.....crap assumed points were in order : D

A / Div. 2 sucks.

Looks very hard for A, knowing that the same problem was used for Div1-E just with a little restriction change.

Edit: My excuses, the problem is actually different, I misunderstood.

Nice contest, A was an exemplary A problem, not too hard, not too easy. Speaking about B, things change, a little bit hardcore to implement, otherwise a classical DP problem. C was way easier than D (look at the number of submitted codes for C, it's pretty low). C probably is some backtracking and for D I'm really curious about the solution. At E I smell an idea similar to http://acm.timus.ru/problem.aspx?space=1&num=1129, but much more elaborated. Clearly, the score distribution was a little bit wrong. Hope my rating won't decrease by too much. Overall, I liked this contest a lot. This should be taken as constructive criticism. Everybody makes mistakes. ;)

You mean C was harder than D*

Couldn't understand problem A (Div. 2). I think an example would have been great in the problem statement...

read my comment above.

Look at this from left to right, in case you print 1 0 1: 0 1 1 so segment [2,3] will have |2 — 0| = 0, which violates.

So, the problem is just with the problem text. If he had taken the time to write it properly, there wouldn't have been so many WAs for such a trivial problem.

Thank you Chirica!

Really nice poblemset ;)

I just needed 2 more minutes to submit C :(

System test!!!!!!!!!!!!!!!!

I missed to watch systest.

()

Translation please. Thanks.

How fast have you submitted the A problem?

Just that three words means this long sentence?? Russian language!!

Not really unexpected, considering Slavic languages have something called conjugation and declension (note that I just googled the english words :D).

It's just one example... If you compare the today's problem statements, the Russian versions are longer than English, less words, but more characters and syllables.

In Hungarian, "I love you" is one word, 'szeretlek', but its length in syllables (3) is same as in English. Does that really makes Hungarian more concise than English?

"Did you solve the first one quickly"?

на чем у всех падает div1 B? на том, что не учли, что они не могут встретится в 1 или последней строчке и в 1 или последнем столбце?

Ага(

spent over thirty minutes finding a test case that gives - 1 on problem

ADiv 2. Gave up and submitted and it got accepted. I guess there was no such test case.Is there any such test case? Please mention it.

There's no such case. If you color the points 01010..01, any interval will end up with the same quantity of 0s and 1s (size of interval is even) or |#0 — #1| == 1 (size of interval is odd).

Just adjacent xs and ys enough for D. Such a tests...

Take look to this.6597823

I think tester should explain this.

WA7 в D на решении с перебором

I also had WA7; now I fixed it, and now I have WA8

And what does WA7 mean?

I hadn't checked right border of array

Why the test cases hasn't been visible yet?

How do I check on which test case my submission is failing? Once I click the solution link, its showing test case number "Runtime error on test 34" but not the test case.

Click the solution number, and click the "#" sign above, and you'll get this: 6595417

UPD: Sorry, it used to be there. I don't know where it is now.

UPD2: It is shown now.

...where you also wouldn't be able to see tests :)

the tests for problem D are very weak

6592992 should get WA with this test case n = 1003

501 elements with value 10000 , 1 element with value 5000, 500 elements with value -10000, 1 element with value -5000

(my generator code : http://paste.ubuntu.com/7448665/ )

Unfortunately, the announcement for problem B modified what was asked in the original statement. Instead of requiring that the two characters meet at a single cell, their paths should have only a common cell after the clarification, which is a stronger requirement (since their speed may be different).

This was surely troublesome for those who started the contest with problem B (like me)...

After the contest, xhae had told me that the following paths are feasible to the problem description, but not to what the problem author requires.

A: [1,1] -> [1,2] -> [2,2] -> [2,3] -> [3,3]

B: [3,1] -> [3,2] -> [2,2] -> [1,2] -> [1,1] (edited, Thanks to marspeople! It was previously [2,3] instead of [3,2])

(spent exactly same time on all cells)

In this case, they only meet in [2,2], but this was not included in the solution (since the intersection of both paths is {[2,2], [1,2]}). The problem description is not clear enough. actually wrong.

I think you meant B: [3,1] -> [3,2] ...

Yes, the problem becomes totally different with the added clarification

What are tests 18 and 14 in Div1.D? I have two solutions (6592810 and 6597945) and they both got TLE on corresponding tests, while running the latter on the 'Custom run' page shows me stable 900ms running time.

I think in the following line the difference should be squared:

if (p1 >= 0 && pts[i].proj — pts[p1].proj < ans — eps) {

I had a TL18 with a similar bug.

Thank you, that's definitely a bug.

However, I'm still wondering about the latter submission (and that's my main concern), which was tested via 'Custom run' on several test cases and still got TLE. Do you have any cool ideas about it too?

Nope.

So, I decided to write something stupid in Div 1 D since I haven't thought of solution.

Seemingly, I couldn't construct an example with large length, so I tried to stop my search after something bigger than sqrt(100K). As I like round numbers, I only checked length up to and including 400. Which, unsurprisingly, got WA.

After the contest, I tried using binary search to determine what the actual maximum length was on the test data. Imagine my joy when I gradually found out that the answer to that question was 401.

But, seriously, I am disappointed that this task was included in the contest if the authors were unable to find a case large enough to fail these naive solutions. Even though I liked the task intended solution with conversion to geometry.

I have a standard solution to "closest pair of points": sort the points and sweepline, keep the ones already sweeped in a

`map<>`

; when processing a point, try all points with closey-coordinates, up to theK-th closest in both directions, then add the processed point into the`map<>`

. Time complexity: . I know that ifK= 50, this approach hasn't ever failed me, so I use it :DWhat's wrong with the standard divide and conquer?

It's a bit harder. What I'm talking about is basically a bruteforce+smart condition.

Your bruteforce can be turned into a simple correct solution:

`x`

and maintain a set of points that have already been processed sorted by`y`

`bestAnswer`

— closest distance among pairs of processed points`currentPoint.y - bestAnswer < y < currentPoint.y + bestAnswer`

, delete points with`x < currentPoint.x - bestAnswer`

and update`bestAnswer`

O(1) will get deleted, so the complexity isI just need to remember something like "an solution similarly relies on there being few numbers close to the processed one, so there shouldn't be evil test data for my approach either" :D

This worked for me too for a long period now. ( even with K smaller ) It is very usefull in a Olympiad fromat as you always make many points in short time. :)

never mind!

401? I also binary searched and got 1002... Look at those solutions: http://codeforces.com/contest/429/submission/6598773 (1001 fails) http://codeforces.com/contest/429/submission/6598792 (1002 passes)

I would guess that you're getting WA because your initial value of best is too low.

This is not the case: http://codeforces.com/contest/429/submission/6599177 g(i, i+1) <= 10^8 + 1, so 10^9 is not too low.

Agreed. Hmm, that's interesting...

Here's 400 failing and 401 passing from me. I cannot yet spot the difference in our codes.

UPD: Oh, OK. There were some extra cases added afterwards (from community, I guess). But 401 was enough during the competition then.

Ah, I understand. You're really unlucky :P. But my case is similar, I set bound to 320 :P. I thought about making it larger, but on my computer it took 1s to process maxtest, so I have left it on 320. But cf servers are much faster than my laptop, for 1000 it took 0,3ms to process maxtest using my solution, if I would have known that before, I would enlarge my bound and got AC xd. But we shouldn't complain, in fact we were "cheating" and we don't deserve AC :P.

I only checked up to 100 numbers back + 100 closest positions (larger and smaller) in terms of prefix sums. I didn't know how fast the CF servers were, so I wanted to avoid TLE. Sadly, this got WA on test 39, with < 500 msec. When I increased the limit to 500 I got AC (with a running time of about 1.8 sec). Anyway, I don't think it's easy to create test cases to fail something like this.

"Anyway, I don't think it's easy to create test cases to fail something like this." — it is.

5000 (k x 10000) -5000 (k x -10000)

for some big k.

Div.2 B. I used easy solution with regexps, because there were no big data. Insert x in every possible position, and While (find 3+ equal numbers){delete them}, Calc what is left. Solution with Perl 6597887.

This guy is lucky as hell: http://codeforces.com/contest/429/submission/6591828 He set max difference j-i to 1005 and got accepted but if it will be changed to 1001 it will fail (smallest number which can be set is 1002).

EDIT: I don't know why, but I can't reply to those posts below :( Compare those solutions: http://codeforces.com/contest/429/submission/6599177 (my solution, 1001 fails) http://codeforces.com/contest/429/submission/6598792 (my solution, 1002 passes) http://codeforces.ru/contest/429/submission/6598182?locale=en (eduardische solution, 401 passes)

EDIT2: Explanation of that phenomenon is here: http://codeforces.ru/blog/entry/12254#comment-169126

Nope, 1000 is just fine. http://codeforces.ru/contest/429/submission/6597981

No, the difference of 401 passes, as I mentioned earlier.

Hmmm, and what about http://codeforces.ru/blog/entry/12254#comment-169072

Maybe some new tests were added? My solution also fails with 1000, but works with 1010...

Hi,

Does Codeforces usually allow users to see test cases after the contest ends?

I see that test cases for problem B (DIV 2) are visible now, but not for problem A (DIV 2). Will it be a matter of time until test cases for problem A get released, or does Codeforces sometimes not release them?

lol

What's typically too deep for a recursive solution? I figured 10^5 would cause a stack overflow, so I wrote Div1 A non-recursively (and somehow wrote a bug into it that way).

Codeforces sets the stack to 256 MB, so it's not easy to overflow it with recursion. You'll likely hit a time limit before that.

Ahh, I wasn't aware it was that high! Thanks!

j = 1001

WA 47

http://codeforces.ru/contest/429/submission/6599410

j = 1002

Accepted

http://codeforces.ru/contest/429/submission/6599408

Nice

Why are the test cases not showing up till now ?? -_-

Round Stats

About div1A/div2C How is this test case valid ? http://codeforces.com/contest/429/submission/6589121 test 35

which is

10

1 10

1 9

10 2

10 3

3 7

3 8

9 4

9 5

5 6

1 0 1 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 0 0

But in the question it was given

The root of the tree is node 1But in the test case it states an edge from 10 --> 1 ???Then node 10 is a child of node 1 (the root) !

No the test case assumes that the edges are bi-directional and the optimal answer is found assuming 1 to be a child of 10.

Also the 1st test case has edges,

2 1 and 3 1, which are opposite to 1 10.

I solved the case by hand, assuming that node 1 is the root, and it is showing correct answer !

Hmm .. you maybe correct about what you are saying Let us assume that if the input contains a b then there is a directed edge from a->b , like in this case 1-10, which justifies 1 being the root.

But see the sample test here,

It has the following edges in the input:

2 1

3 1

which tells us that there are edges from 2->1, which contradicts of 1 being the root. I hope you understand what I am trying to say.

Actually this is how I've generated the tests , but some of them were added later. But it didn't came to my mind that this will make any difference or someone will get confused. Though , the statement was clear sorry for the inconvenience.

My friend, why do you assume that the trees are directed?

Typically trees are undirected (unless otherwise stated in the problem), and the input specification just states that a pair

u_{i},v_{i}means that there is an edge between those two nodes. It doesn't mention any particular direction.Problem statement states that 1 is the root of the tree.

Doesn't that mean if the tree is rooted so it has to be directed ?? Because root of a undirected graph doesn't makes any sense.

I frankly have no answer to your statement that "root of a undirected graph doesn't makes any sense".

My recommendation, if you'd like to consider it, my friend, would be to invest a few moments studying the definition of a tree. Wikipedia's entry is fairly well-written and I think it will helpful.

Yes, you're actually right in saying that since it has a root, it must be directed (by definition of rooted tree). However, naming the root isn't enough to uniquely determine the direction of each edge (since they can either be all towards or all away from the root), the edges they give you are just a list of the edges present in the tree (without direction), and it's up to you to assign them a direction that makes sense.

Wonder why they can't simply give us parent index for each vertex. Would be a lot less trouble for everyone involved.

The problem statement goes as follows:

“Each of the next

n- 1 lines contains two integersu_{i}andv_{i}meaning there is an edge between nodesu_{i}andv_{i}.”Note that it mentions an undirected edge

betweentwo nodes, not a directed edgefromone nodetoanother. So, the statement does not imply the nodes will be given in any particular order (from the root, or lexicographical, or whatever).What were your solutions to C? First important observation is that there are at least n/2 leafs. I got AC with some weird backtracking, which tries to build (n/2)! different trees (but its search space is in fact lot smaller, but I can't come up with a better estimation). but after the contest I came up with a solution O*(2^n), but 4^(n/2) is in fact a better description of that :P. Consider a dp with array dp[n/2][3^(n/2)] (^ means power not xor ;) ). We divide non-leafs into 3 groups — nonactive and used, active and used, nonused and for given dp[k][mask] where mask denotes the division of nonleafs into 3 groups. This state is reachable iff we can build a forest where set of vertices are used vertices, set of roots are used and active vertices and where k leafs were used. But when checking if fixed state is reachable we have to search many states, possibly 2^(n/2). So whole algorithms runs in O*(6^(n/2)) ("*" means "*poly(n)", it is standard notation), which is in fact O(*(4^(n/2)) algorithm. Why? I will leave that to you as a nice exercise.

As far as I got you, my solution was similar, but instead of having those 3-states I was attaching children to the nodes in some order, so instead of having 3rd state I had a variable in my DP solution which shows up to which non-leaf node I have already assigned childrent.

DP[mask][assigningTo][remainingLeafs] in my solution is whether we can assign nodes denoted by mask to the nodes from [0 .. asssigningTo] interval using additional 'remainingLeafs' number of leafs. Internally when calculating this DP I was simply checking all the submasks of the given mask.

Here is the solution: 6599572

My DFS solution runs in time. I built it based on simpler solution, that runs in:

O(3^{n}) time. Let's start with sorting nodes by number, given in input. We encode our state as pair i,j — means that we have considered first i nodes, some of them connected and mask j contains all nodes, that have no parents. First note that i is redundant, since the last one in mask is obviously the last node considered, so i equals last bit +1. Let's consider all subsets of this mask and pick each that have at least two bits set and required sum. It is known that total amount will be 3^n. And if we precalc all sums and bitcounts, we will be able to solve problem inO(3^{n})Now let's remove all leafs from mask. Then we will have state i,j — we considered some first nodes and now we have i leaves without parents and inner nodes described in mask j.

All of those accepted solutions are a big shame for tests preparers:

http://codeforces.com/contest/429/submission/6599749 greedy for C

http://codeforces.com/contest/429/submission/6591828 checking pairs of points with small j-i in D

http://codeforces.com/contest/429/submission/6597823 — checking pairs of points with adjacent xs and ys in D :(

For (Div. 1) B, when brute forcing the meeting point after pre-computing the dp tables, my original solution (which got WA on test 23) checked every possible cell, including those on the border. Then, after contest, after viewing some of the accepted solutions, I changed it to only allow them to meet at interior points. So for this case:

3 3 1 1 1 1 1000 1 1 1 1

my new accepted solution gets 8, while my old solution got 1006 (corresponding to them meeting at the left middle cell and then one of them proceeding to the middle). I'm probably just missing some detail in the problem statement, but why is that invalid?

If by "left middle cell" you mean (row 2, column 1), it wouldn't be a valid meeting point because they can't get out of that cell without both moving to (row 2, col. 2), or stepping on a cell previously visited by the other person.

There was a clarification stating something to the effect that both paths have to be completely disjoint,

exceptfor the cell in which they meet.So, in a 3 × 3 grid, the only valid meeting point is (2, 2).

Oh okay, I somehow missed that clarification, but I see it now. Thanks!

What's the solution to 1E problem. I read the code, I see what it does. However, I don't understand what is the idea behind the problem. How do I proof that doing it like this always scott_wu or SergeyRogulenko always returns a solution?

Consider a sorted list of all starting and ending points of every segment. It doesn't matter in which order we place points that have the same coordinate: see below why. Starting points of red segments and ending points of blue segments would be marked with +1, and starting points of blue/ending points of red will be -1. We need to make sure the sum in every prefix is between -1 and 1. This means the sum at all even points will be 0. This means points 2k and 2k+1 must have different signs. Also, obviously, two ends of the same edge must have different signs. We got a graph that we must color in two colors. Now note that the graph has two kinds of edges, and edges of the same kind can never share a vertex (by construction). This means that there are no odd cycles, so we will always find an answer.

The problem A div2 make me crazy!

I used O(min(abs(a[i]))n) past the problem D ....

The data for D is weak. My AC solution gets this case wrong:

1 10000 ... (2000 times) ... 10000 -5000 -10000 ... (1999 times) -10000 -5000

My AC solution: http://codeforces.com/contest/429/submission/6596958

Generator code for this test case: https://gist.github.com/jonathanpaulson/1d5fb7825395185dcd5d

It is difficult that make this problem's data. But my solution is ugly. In this case 100000 10000 10000…… (100000 times) my sulution will TLE.

I feel so stupid trying to solve E for an hour until the time ran out then doing C in 15 minutes after the contest =\

About problem 429A, a recursive version solution got RE while a iterative version passed.

http://codeforces.com/contest/429/submission/6605357 http://codeforces.com/contest/429/submission/6605261

Is this a limitation of a interpreted language, so most people chose compiled languages to do the recursion?

You seem to have set the stack to 100k, which seems to be enough at least for that particular test (but would probably fail on the maximum one). I would avoid python here. It barely works on topcoder, and they have WAY smaller datasets. If a correct solution to any problem takes half a second in C++, it would take like 5 seconds in python.

Yes,it is a huge limitation. I don't prefer to use python for a recursive solution that has a depth of more than 1000(the default recursion limit in python) ... Though the stack size in codeforces is very large, but python requires more!

After some discussion, I think the root cause might be Python need larger stack frame so the stack just overflow. Thanks to sayuan.

In my experience:

sys.setrecursionlimit

just sets "desirable" limit. If stack space ends before this setrecusionlimit is reached, python interpreter just dies silently. Also Python reserves a lot of stack space on each iteration. In one examples of mine I needed just 3,000 recursion limit and it died on my local machine at around 2,500. I didn't even receive any error messages — python just stopped execution and finished. 100K I think is impossible for Python even with very large stack space.

That's true. I also tried to set the stack size but still failed.

http://codeforces.com/contest/429/submission/6609602