Hello everyone!

Codeforces Round #167 will take place on Wednesday, February 13th at 19:30 MSK. This is my fourth Codeforces round and I hope not the last.

I'd like to thank Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values will be standard in both divisions.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over. Congratulations to div1 winners:

1). tmt514

2). tourist

3). scott_wu

4). rng_58

5). dreamoon_love_AA

and div2 winners:

1). yefllower

2). Harlos

3). pseudopodia

You can view tutorial here.

Are you sure about this date : "Sunday, January 13th at 19:30 MSK"

Guys according to your date the contest has been completed... because your date

Sunday, January 13th at 19:30 MSKis gone....After 7 rounds, all the 3 digits of this round is strictly increasing :)

Here 167 is a prime , 67 is a prime && 7 is a prime as well :D

scoring??

they'd say if it was unusual (i mean it wasn't 500 1000 1500 2000 2500)

Rishat_Ibrahimov used #define long unsigned long long and that costed me a wrong challenge, shouldn't that be considered code obfuscation?

No, you should read the code properly

div 2 D,can it be solved w/o chinese remainder theorem(CRT).

Let's sort all pairs. There can be equal ones, which can be now easily recognized. If there aren't — the answer is (n+m)!, obviously. But if there are, we should divide our (n+m)! by number of equal pairs (since 2! = 2; if there were equal triples, we might have divided by 6). Division goes using Fermat's little theorem since we're using modulo.

Edit: forget about the theorem, those 2's are from factorials, as MohallaBoy noticed.

What do you mean by (n+m)! ？Can you show some details?

I'm very sorry about misinformation — only yesterday before resubmitting D I realised that I wrote incorrect part of solution here. Please disregard it :) There's an editorial for now.

basically you to find values like (n! / (2) ^ k) % m You can do this by removing 2's in the numbers which are used for calculating factorials. and taking then modulo m.

first recognize all equal pairs, then for each repetition of the x term we calculate (length)!, omitting a 2 for each pair earlier. Although im 100% sure this is the solution i didnt implement it well enough for pretests :(.

When we calculate factorial let's just divide each factor by 2, if there is any pairs left. Even if we use chinese remainder theorem, we can't calculate modInverse of 2 if 2 is divider of our modulo.

The answer is integer so when we got our answer badCount == 0

any ideas for solving C Div 1 ??

Edited : I was wrong !

Randomly distribute horses in 2 parties. Now if each horse has at most 1 enemy in its party, this distribution is correct. Otherwise, there exists horse A in party 0 that is enemy with horses B and C in the same party. Now move horse A to party #1 and it'll have at most 1 enemy in its new party. To prove this solution works, just define an invariant as count of enemy pairs in same party. Observe that after each move, this invariant decreases and hence our procedure is finite.

How do you prove that if this method fails to find a partition, then a partition is impossible?

Actually, when our invariant decreases at each step, it'll eventually reach 0 which means we are left with a correct distribution of horses in 2 parties. Possible partition always exists and it may not be unique but our algorithm guarantees to find one :-)

Sorry for being picky but I think it's variant, not invariant.

You're right. Thanks for pointing this out. Topic of this problem in Combinatorics is invariants and that's why I confused them :D

I think it is called monovariant.

Imagine, that all the horses are in part 0. According to your alrorithm, firstly we move horse 1 to part 1 (enemies 2,4,5). Then we move horse 2 to part 1 (enemies 3,5). Also we move horse 3 (enemies 4,6). Horse 2 now has 2 enemies (1,3) in its part. So, it doesn't work. Maybe I've misunderstood you, so please, can anybody explain me the correct solution of this problem?

UPD:All right, I understood you. But it was not easy to push it through TL (3126714). Maybe it's because of Java. Is that an optimal solution?Complexity is

O(m) and the idea behind this solution comes from a known graph problem. So I reckon this solution is optimal.Sorry for tourist. How fast he was. But even this didn't help him to pass Pretest 0 ( Compilation ). 3123727 and 3123677 :)

PFFFFFF)

:S DIV 2.B: Any one have an idea that why 3122613 has wrong answer on pretest #8?! I'm really sure that it should produce a correct answer. :S

ans++ , seriously , it will TLE

What does TLE mean?

TLE = Time Limit Exceeded

But System's Test say "Wrong answer on pretest #8" rather than any TLE!

You shouldn't

`continue`

on`a[i] == a[j]`

at line 40.And you use insertion sort which is O(n^2). I think it will timeout before finishing input.

Oooops...

Thanks ray040123!

Actually I confused

`1<=i<j<=n`

with`1<=a[i]<a[j]<=n`

:((DIV1 D is an original problem.

http://community.topcoder.com/stat?c=problem_solution&rd=14422&pm=11179&cr=10574855

TopCoder has its harder version.

one of the best contests ever..!!

well balanced on thinking and data structures...

wasn't anyone fool enough like me to use segment tree for div 2 C.

well, i used BIT

submission in queue...

I used Fenwick Tree for that problem :)

and fingers crossed.....:)

I think you don't notice A[i] <= A[i+1] , I'm too) But I did it after writing void build(.... )))

But even if it wasn't A[i]<=A[i+1] you can create sequence B such that B[1]=A[1] and B[i]=max(B[i-1], A[i]), so this assumption wasn't really necessary ; p.

No, you weren't :/ Segment tree consumed all of my time — I should have read D first...

lol, i wanted to code it, but then i saw a number of acceptions for this task.

I use segment tree, too. I've got some MLE after some TLE and finally I forgot to use

`long long`

.same here :) I got it Accepted and also I apologize to Segment tree for using it in this easy problem

atleast u got AC,long long cost me WA....:(

I was fool too :(

I didn't notice that the stairs are sorted

I also didn't notice that boxes fall from the left until I coded it

anyway I was fooler because my code was fail on test 45 because of overflow :(

It looks like the only difference in kissbuaa's and xiaodao's 2000s is the link in the beginning.. ..which is pointing to the same solution, yep. http://codeforces.ru/contest/273/submission/3115085

http://codeforces.ru/contest/273/submission/3114783

The same http://community.topcoder.com/stat?c=problem_solution&rd=14422&pm=11179&cr=10574855

I solved this problem after read this about one year ago ... > < .. I lost some of my code after a hard-drive broken and can't log-in to TC to access my solution. (because there is a SRM 2 hours early .. ) This is not a hard dp problem, but need implementation carefully. Even if I solved it before can't ensure I can solve it on the contest within the time. (I even didn't have a Java Complire on my laptop ... so only change the code under a text-editor ..

.. PS: The DIV 1 C is also a original problem ...

Can Topcoder work without java? LOL~~~

考挂自己弱，xlk 最弱！。

Orz xiaodao, Orz xlk div1 C can also found here:http://acm.timus.ru/problem.aspx?space=1&num=1128

There are more than 2: 3122346

3121856

3121632 (change variable names?)

3120914

3119084

and there might be more...

I wonder how could you find them?

I have seen Div 1 C problem in Soviet math olympiad in 1979. This problem is "Proof that there always exists answers."

http://acm.timus.ru/problem.aspx?num=1128 It is here.

I have seen this so many times :D. I have even coded exactly the same task and did this problem with 2 of my pupils as a classic problem for variants :P.

Div 2 B was ambiguous

I've accepted problem C Div 2 at 1:29:22 ( Only 30 seconds untill the end of contest) ! I wonder if it was a record!?

You can easily check it on the status or standings page

How to get test case data on which our program has failed.

Since test input is large so It is showing only part of it.

i was about to ask the same question !!!!

it's not possible in CF :)

An untidy way.. but if u really really need it you can make a hack.. Just print say 20 tokens once (or whatever size fits in the screen), then next 20 and so on..

76 contests and 18 months of ups and downs and finally I get to taste Division 1 in Codeforces, the place where I started online programming.. May be small thing for others but it means a lot lot to me because this is where I started from.. Sometimes getting close and then falling back and sometimes no where near to the horizon..Yes... Now I can proudly say that I am Div 1 in codeforces and topcoder together .. I dont know how long I am going to stay here but just being here is a great feeling... :) I hope I will never see Div 2 again.. Thanks to the author Sereja and Egor as always for CHelper

Gotta thank Sereja for the best contest in my whole life. Couldn't be better than this for me! :D

It's because You became candidate master and solve five problems?

Well if You can solve C segment tree with updating on segments, it doesn't seem so simple. And if You solve D in few minutes to the end, it doesn't seem so simple too.

I did problem D in div2 carelessly and WA for 4 times in the contest. At last I only got 880 for this problem... But my rank seems OK...

Ignore it, I didn't understand you.

The same to you. I solved the problem D 5 minutes before contest just because of my carelessness.

what happened to your tutorial link?

The tutorial is written in Russian, it hasn't been translated now. Only Russian vision is visible... So just wait them to translate...

http://www.codeforces.com/contest/272/submission/3128898

i don't understand the fail of my solution ?

As you use C but not C99 you must declare i and j before the loop:

Can you give me a small test case where my submission fails. Thanx in advance

There is a problem:

cnt can be equal to 10

^{5}, so overflow will happen.my bad :( .... should have noticed earlier :D . And thanks a lot Fefer_Ivan :)

By python, I can not solve C in Div I! If anyone know, please post it!

The input is n<=3*10^5, m <= 9*10^5, about 10^7. It's just too large for python. My C++ solution cost 375ms and my python solutions are always 10 times slower. So I guess python need about 4 seconds for each test case.

yes, I think so. I also meet this issue. I implement C++ and python with the same algorithm. The C++ code is accepted in 500ms, but the python one is not.

can you explain about the second argument in your

`change`

function? Your solution is recursive. I can convert it to non-recursive version if I understand the trick.