Sereja's blog

By Sereja, 11 years ago, translation,

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.

• +195

| Write comment?
 » 11 years ago, # |   +45 Are you sure about this date : "Sunday, January 13th at 19:30 MSK"
 » 11 years ago, # |   +16 Guys according to your date the contest has been completed... because your date Sunday, January 13th at 19:30 MSK is gone....
 » 11 years ago, # |   -17 After 7 rounds, all the 3 digits of this round is strictly increasing :)
•  » » 11 years ago, # ^ |   -14 Here 167 is a prime , 67 is a prime && 7 is a prime as well :D
 » 11 years ago, # |   0 scoring??
•  » » 11 years ago, # ^ |   +9 they'd say if it was unusual (i mean it wasn't 500 1000 1500 2000 2500)
 » 11 years ago, # |   +2 Rishat_Ibrahimov used #define long unsigned long long and that costed me a wrong challenge, shouldn't that be considered code obfuscation?
•  » » 11 years ago, # ^ |   +14 No, you should read the code properly
 » 11 years ago, # |   0 div 2 D,can it be solved w/o chinese remainder theorem(CRT).
•  » » 11 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 11 years ago, # ^ |   0 What do you mean by (n+m)! ？Can you show some details?
•  » » » » 11 years ago, # ^ |   0 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.
•  » » 11 years ago, # ^ |   +4 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.
•  » » » 11 years ago, # ^ |   0 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 :(.
•  » » 11 years ago, # ^ |   +3 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. long f(long n) { long res = 1; for (int i = 2; i <= n; i++) { int k = i; while (k % 2 == 0 && badCount > 0) { badCount--; k /= 2; } res = (res * k) % MOD; } return res; } The answer is integer so when we got our answer badCount == 0
 » 11 years ago, # |   +6 any ideas for solving C Div 1 ??
•  » » 11 years ago, # ^ | ← Rev. 2 →   0 Edited : I was wrong !
•  » » 11 years ago, # ^ |   +9 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.
•  » » » 11 years ago, # ^ |   0 How do you prove that if this method fails to find a partition, then a partition is impossible?
•  » » » » 11 years ago, # ^ |   +7 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 :-)
•  » » » » » 11 years ago, # ^ |   +5 Sorry for being picky but I think it's variant, not invariant.
•  » » » » » » 11 years ago, # ^ |   0 You're right. Thanks for pointing this out. Topic of this problem in Combinatorics is invariants and that's why I confused them :D
•  » » » » » » 11 years ago, # ^ |   0 I think it is called monovariant.
•  » » » 11 years ago, # ^ | ← Rev. 2 →   +5 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?
•  » » » » 11 years ago, # ^ |   0 Complexity is O(m) and the idea behind this solution comes from a known graph problem. So I reckon this solution is optimal.
 » 11 years ago, # |   -9 Sorry for tourist. How fast he was. But even this didn't help him to pass Pretest 0 ( Compilation ). 3123727 and 3123677 :)
•  » » 11 years ago, # ^ |   +6 PFFFFFF)
 » 11 years ago, # |   0 :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
•  » » 11 years ago, # ^ |   +4 ans++ , seriously , it will TLE
•  » » » 11 years ago, # ^ |   -10 What does TLE mean?
•  » » » » 11 years ago, # ^ |   +4 TLE = Time Limit Exceeded
•  » » » » » 11 years ago, # ^ |   +3 But System's Test say "Wrong answer on pretest #8" rather than any TLE!
•  » » 11 years ago, # ^ |   +4 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.
 » 11 years ago, # |   +60 DIV1 D is an original problem.http://community.topcoder.com/stat?c=problem_solution&rd=14422&pm=11179&cr=10574855TopCoder has its harder version.
 » 11 years ago, # |   -18 one of the best contests ever..!!well balanced on thinking and data structures...
 » 11 years ago, # |   +15 wasn't anyone fool enough like me to use segment tree for div 2 C.
•  » » 11 years ago, # ^ |   0 well, i used BIT submission in queue...
•  » » 11 years ago, # ^ |   0 I used Fenwick Tree for that problem :)
•  » » » 11 years ago, # ^ |   0 and fingers crossed.....:)
•  » » » 11 years ago, # ^ |   0 I think you don't notice A[i] <= A[i+1] , I'm too) But I did it after writing void build(.... )))
•  » » » » 11 years ago, # ^ |   +3 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.
•  » » 11 years ago, # ^ |   0 No, you weren't :/ Segment tree consumed all of my time — I should have read D first...
•  » » 11 years ago, # ^ | ← Rev. 2 →   0 lol, i wanted to code it, but then i saw a number of acceptions for this task.
•  » » 11 years ago, # ^ |   +9 I use segment tree, too. I've got some MLE after some TLE and finally I forgot to use long long.
•  » » 11 years ago, # ^ | ← Rev. 2 →   0 same here :) I got it Accepted and also I apologize to Segment tree for using it in this easy problem
•  » » » 11 years ago, # ^ |   0 atleast u got AC,long long cost me WA....:(
•  » » 11 years ago, # ^ | ← Rev. 2 →   +4 I was fool too :(I didn't notice that the stairs are sortedI also didn't notice that boxes fall from the left until I coded itanyway I was fooler because my code was fail on test 45 because of overflow :(
 » 11 years ago, # | ← Rev. 3 →   +15 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.com/contest/273/submission/3115085http://codeforces.com/contest/273/submission/3114783
•  » » 11 years ago, # ^ |   +9
•  » » 11 years ago, # ^ | ← Rev. 5 →   +5 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 ...
•  » » » 11 years ago, # ^ |   +18 Can Topcoder work without java? LOL~~~
•  » » » » 11 years ago, # ^ | ← Rev. 2 →   -30 考挂自己弱，xlk 最弱！。
•  » » » 11 years ago, # ^ |   +5 Orz xiaodao, Orz xlk div1 C can also found here:http://acm.timus.ru/problem.aspx?space=1&num=1128
•  » » 11 years ago, # ^ | ← Rev. 2 →   +9 There are more than 2: 312234631218563121632 (change variable names?)31209143119084and there might be more...
•  » » » 11 years ago, # ^ |   -11 I wonder how could you find them?
 » 11 years ago, # |   +19 I have seen Div 1 C problem in Soviet math olympiad in 1979. This problem is "Proof that there always exists answers."
•  » » 11 years ago, # ^ |   +34 http://acm.timus.ru/problem.aspx?num=1128 It is here.
•  » » 11 years ago, # ^ |   +15 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.
 » 11 years ago, # | ← Rev. 2 →   -11 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!?
•  » » 11 years ago, # ^ |   +4 You can easily check it on the status or standings page
 » 11 years ago, # |   +5 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.
•  » » 11 years ago, # ^ |   +3 i was about to ask the same question !!!!
•  » » » 11 years ago, # ^ |   +7 it's not possible in CF :)
•  » » 11 years ago, # ^ |   +4 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..
 » 11 years ago, # |   +43 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
 » 11 years ago, # |   -6 Gotta thank Sereja for the best contest in my whole life. Couldn't be better than this for me! :D
•  » » 11 years ago, # ^ |   +5 It's because You became candidate master and solve five problems?
•  » » » 11 years ago, # ^ |   +23 A contest that was based on Combinatorics and problem solving skills and didn't need hard and famous algorithms to be implemented. A brain challenging one.
•  » » » » 11 years ago, # ^ |   +10 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.
 » 11 years ago, # |   +1 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...
•  » » 11 years ago, # ^ | ← Rev. 2 →   +3 Ignore it, I didn't understand you.
•  » » 11 years ago, # ^ |   0 The same to you. I solved the problem D 5 minutes before contest just because of my carelessness.
 » 11 years ago, # |   0 what happened to your tutorial link?
•  » » 11 years ago, # ^ |   0 The tutorial is written in Russian, it hasn't been translated now. Only Russian vision is visible... So just wait them to translate...
 » 11 years ago, # |   0 http://www.codeforces.com/contest/272/submission/3128898i don't understand the fail of my solution ?
•  » » 11 years ago, # ^ |   +3 As you use C but not C99 you must declare i and j before the loop: int i; for (i=1;...) 
•  » » » 11 years ago, # ^ |   0 Can you give me a small test case where my submission fails. Thanx in advance
•  » » » » 11 years ago, # ^ |   +14 There is a problem: int cnt = 0; ... nans *= ((cnt*(cnt-1))/2); cnt can be equal to 105, so overflow will happen.
•  » » » » » 11 years ago, # ^ |   +3 my bad :( .... should have noticed earlier :D . And thanks a lot Fefer_Ivan :)
 » 11 years ago, # | ← Rev. 3 →   0 By python, I can not solve C in Div I! If anyone know, please post it!
•  » » 11 years ago, # ^ |   0 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.
•  » » » 11 years ago, # ^ |   0 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.
•  » » » » 11 years ago, # ^ |   0 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.