### cgy4ever's blog

By cgy4ever, 6 years ago, ,

Hello everyone!

Codeforces Round #228 (Div. 1 and Div.2) will start at Monday, 3 February 2014, 19:30:00 MSK.

This is my 2nd round on Codeforces. (Click here to see my last round) , As usual, there will be 7 problems: 2 for Div2, 2 for Div1 and 3 for both. And same with the last round, the main character of all problem will be Fox Ciel.

I would like to thank Gerald for testing, and MikeMirzayanov for the Codeforces project including polygon system.

Good luck and have fun!

The score distribution will be published later. And the editorial will be published right after the system test.

By the way, yesterday is the Chinese new year. So I'd like to say Happy New Year to everyone who celebrate it! And I'm very glad to be the writer of the first round in the new year.

Update1: Good news for participants of Petrozavodsk training camp. Top 20 participants of the camp by this round results will get t-shirts from Codeforces.

Update 2: The score distribution for Both Division is regular (500-1000-1500-2000-2500).

Update 3: We postpone the round 10 minutes by technical reasons (dinner on Petrozavodsk Training Camp), sorry for the inconvenience.

Update 4: We've increased the contest time by 5 minutes.

Update 5: Contest ended, thanks for your participating! I'll post the editorial soon.

Update 6: Editorial.

Winners:

DIV1:

Sadly no one solved E correctly. Egor's solution can pass if the TL is 7 seconds instead of 6, what a pity!

DIV2:

They are the only people who solved all tasks!

• +313

 » 6 years ago, # |   +15 Wow, a new contest. Thanks for preparing problems and I think I will love this contest:) PS: Orz
 » 6 years ago, # |   +37 Hm.. there's also a TopCoder SRM earlier on Monday. I wonder if I will be able to participate in both TC and CF :)
•  » » 6 years ago, # ^ |   +60 Codeforces Round #207 (Div. 1) and Topcoder SRM 594 happened successively and tourist won both of them. Maybe you can try to pull off a similar stunt :D
•  » » » 6 years ago, # ^ |   +49
•  » » » 6 years ago, # ^ |   +14 tourist has registered for both CF and TC contest today. :D
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 unfortunately, he didn't win the SRM! so history will not repeat itself, unless tomek wins this CF round! good luck to him and everyone else!
•  » » » » » 6 years ago, # ^ |   +8 tomek can repeat tourists double. if one of Egor's solutions not pass)
•  » » » » » 6 years ago, # ^ |   +8 You spoke too soon :P
•  » » » » » 6 years ago, # ^ |   0 well, tourist didn't win the SRM, but won the Codeforces round. he had to win one of them!!
 » 6 years ago, # |   +22 Your last contest had nice problems.Thank you for creating another contest.
 » 6 years ago, # |   +13 I'm definitely looking forward to the 1st contest in the Chinese new year! 新年快乐！
•  » » 6 years ago, # ^ |   -17 新年快乐
 » 6 years ago, # |   +1 thx
 » 6 years ago, # |   +13 Problem description was nice (and short too) of your last contest ... Hope it here also ... :)
 » 6 years ago, # |   +26 Your previous contest's problems were awesome, looking forward!..
 » 6 years ago, # | ← Rev. 13 →   -19 We HoPe gEt NeW RaTinG PoiNt aFTer tHiS CoNteST :) .GOOD LUCK eVerYoNe and thanks for this contest cgy4ever MikeMirzayanov Gerald ! (HaPPy NeW YeaR Chinese PeoPLe ;) )
•  » » 6 years ago, # ^ |   +47 What is wrong with ur SHIFT key :)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -9 No, I don't have any problem.i just wanted to make it interesting...
•  » » » » 6 years ago, # ^ |   0 Sorry, misunderstood it :p
•  » » » » » 6 years ago, # ^ |   -17 No problem for me but it caused torrent of downvotes :( ...
•  » » 6 years ago, # ^ |   0 i think that he just wanted to make it appealing..
•  » » » 6 years ago, # ^ |   0 Actucally, to me, it' s a little bit hard to read. (Yes, just to me) Well I don' t learn English very well...
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -11 THIS IS SPECIAL FOR YOU LiuRunky.We Hope get new rating point after this contest :) .Good luck everyone and thanks for this contest cgy4ever MikeMirzayanov Gerald ! (Happy new year Chinese peopLe ;) )
•  » » » » » 6 years ago, # ^ |   +7 Sorry, I apologize for my behaviours before. ThAnKs FoR YoUr FoRgIvEnEsS! Wish you a good luck today.
•  » » » » » » 6 years ago, # ^ |   0 No prob.Don't worry.I hope you will get sufficiently score today :) LiuRunky
 » 6 years ago, # |   +18 Good luck everyone~ This must be a good contest! :)
 » 6 years ago, # |   -43 Мне кажется или все пытаются набрать как можно больше "Вклада".
•  » » 6 years ago, # ^ |   -22 Да, и ты один из них.
 » 6 years ago, # |   +5 GL for every one
 » 6 years ago, # |   +6 two contest in a day! hard but fun! :D
•  » » 6 years ago, # ^ |   -9 Fail(( I've missed TC one
 » 6 years ago, # | ← Rev. 2 →   -9 Lack of div1 rounds didn't let div1 users refuse this contest! 1127 registrants for division 1! Thanks for making this round a both division round ;-)EDIT: 1144 after extra 10 mins!
•  » » 6 years ago, # ^ |   -9 YEAH . Most of them aren't going to participate :D
 » 6 years ago, # |   +93 Don't worry, the round delayed because of dinner on Petrozavodsk Training Camp :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +21 Is the room bug rectified? :)
•  » » 6 years ago, # ^ |   +95 And my dinner!
•  » » » 6 years ago, # ^ |   +118 In Russia there is the saying: War is war, but lunch is on a schedule.
 » 6 years ago, # | ← Rev. 2 →   +8 Funny. MikeMirzayanov says that the round is delayed because of dinner at Petr. Training Camp, and in the official post of the round, because of "technical reason". Or is the dinner the actual technical reason?EDIT: already included above.
•  » » 6 years ago, # ^ |   +44 Petr. Training Camp sounds great =)
•  » » » 6 years ago, # ^ |   0 It certainly does :D I would like to have an uppercase dot character for avoiding such things )))
 » 6 years ago, # |   0 Wow! Is dinner a technical reason? :)
•  » » 6 years ago, # ^ | ← Rev. 3 →   +6 actually dinner is an important reason! :)
 » 6 years ago, # |   -13 I want to rating under color of my eyes... (red) =D
•  » » 6 years ago, # ^ |   +17 :|
•  » » 6 years ago, # ^ |   -15 Can U shut your mouth??????? if you can't Ican do that for U......
 » 6 years ago, # |   0 sta-le-ar in gat mancarea
 » 6 years ago, # |   0 'technical'reason == dinner LOL :D
 » 6 years ago, # |   0 Extra time for "Codeforces Unavailable"?
 » 6 years ago, # |   +6 Sorry for unstable work. It was a real stress test for server!
 » 6 years ago, # |   0 most of the solutions in problem B will fail, also my solution :( for k=10^9 n=1017
•  » » 6 years ago, # ^ |   -8 n is not a paramter I guess
•  » » 6 years ago, # ^ |   +2 Do 10^9 exist as an input in final test cases?
•  » » 6 years ago, # ^ |   +3 Mine doesn't fail for 10^9 but for 999997439. (N comes out to be 1017 :))
•  » » » 6 years ago, # ^ |   +3 And for testcase 268435455 your solution will output graph with 1137 vertexes.
 » 6 years ago, # |   0 Great contest..Really enjoyed it Thanks alot
•  » » 6 years ago, # ^ |   -76 Shut up your trap!
 » 6 years ago, # | ← Rev. 4 →   +26
•  » » 6 years ago, # ^ |   +3 where is the statistics of this round ? :)
•  » » » 6 years ago, # ^ |   +3 Sure :)
 » 6 years ago, # |   0 good contest, good problems
 » 6 years ago, # | ← Rev. 3 →   +24 When will the ratings be updated? UPD : Updated :D
•  » » 6 years ago, # ^ |   +2 I hope never :(
•  » » » 6 years ago, # ^ |   +8 SUFFER!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 its updated only in div2, upd: its updated now
 » 6 years ago, # | ← Rev. 3 →   0 Excuse me, I had an idea about the Div1 B/Div2 D. 1. If we add edges like this 1-3 1-4 2-3 2-4, then we' ll have 2 shortest paths, and 1-3 1-4 3-5 4-5 5-6 5-7 2-6 2-7 so that there' ll be4(2*2) paths, 8(2*2*2) paths with only 10 vertices... It seems that it' s easy to construct a graph with 2^n shortest paths. 2. If we devide the number k into a set of numbers which sum is k, and all the numbers must be 2^i( 0<=i<=32), then we can constuct a graph with paths I mentioned before. It is obvious that n won't be very large. Actually the problem can be solved correctly with this idea, but I' m so stupid that can' t work out
•  » » 6 years ago, # ^ | ← Rev. 5 →   0 your idea is correct,but you have mistake in your implementation also you are using more than 1000 nodes in the graph when binary representation of k contains more than 22 one
•  » » » 6 years ago, # ^ |   0 Actually this idea uses much less than 1000 nodes, the powers of 2 that sum to 10^9 is the number of ones in the binary representation of k, and each power requires 2*i nodes which is a maximum of 2*32, so the total number of nodes is less than 2 + 32*2*32 << 1000. The problem is that dividing the paths into powers of 2 will have paths that are shorter than other paths requiring extra "dummy" vertices to equalize the paths.
•  » » » » 6 years ago, # ^ |   0 2 + 32*2*32 > 1000
•  » » » » » 6 years ago, # ^ |   0 and since each 2^i will have a unique "i" , the sum of "i"s will be (n)*(n-1)/2 ... and 10^9 is < 2^30... sorry, i overestimated
•  » » » 6 years ago, # ^ |   0 what is the easy solution in this way,please someone post how reduce nodes?
•  » » » » 6 years ago, # ^ |   0 I decomposed k into 33 radix, max nodes count becomes approx 800.
•  » » » 6 years ago, # ^ |   0 Ohhh, yes. Thanks, I found my mistake. There will be about 1500 vertices when k is big enough...
•  » » » » 6 years ago, # ^ |   0 My solution with the same idea: http://codeforces.com/contest/388/submission/5889570
•  » » » » » 6 years ago, # ^ |   0 I have checked ur code and found that our general idea is the same, but still don' t understand some details in ur code...
•  » » 6 years ago, # ^ |   0 1-3 1-4 3-5 4-5 5-6 5-7 2-6 2-7How does this graph have 4(2*2) paths? I see only 2*2 paths.
•  » » » 6 years ago, # ^ |   0 4=2*2, not 4*2*2
 » 6 years ago, # |   +10 thanks cgy4ever, you're the best :Dtwo excellent rounds, I'm looking forward to your third one :)
 » 6 years ago, # |   +8 I got different outputs with same code, just one line difference at codeforces. I get perfect output at my pc. Can anyone please explain why this happening? Got WA at problem B(div. 1), and get this problem by reducing lines of my code.
•  » » 6 years ago, # ^ | ← Rev. 7 →   -10 I don't know why this happens, but may be it will be a useful fact that this code: #include #include using namespace std; int main(){ int k,len; cin >> k; k = 1000000; len = (int)pow(1.*k,0.2); k -= (int)pow(1.*len,5.); cout << k; return 0; } gives same results whether "k = 1000000;" commented or not.Then, we can see that result depends on this: k -= (int)pow(1.*len,5.); If we don't use type conversion, we'll get different results, if use — the same anyway. But why? :)
•  » » » 6 years ago, # ^ |   0 yes. Thanks. :)But beyond type conversion, my code is only depend on whether k = 1000000 is commented or not. But, WHY???
•  » » » » 6 years ago, # ^ | ← Rev. 8 →   -8 Finally, I think, the reason is that len*len*len*len*len != pow(len,5.));You can check it easily by cout << ((1.*len*len*len*len*len)==pow(len,5.));Another question is why they're not equal. And how it depends on way of assining 1000000 to k.Oh, of course, this stuff happens only wiht GNU. MSVS works well with all these cases.
•  » » » » » 6 years ago, # ^ |   0 My g++ version is 4.6.3 and two version of my code outputs correctly. Ideone runs g++ 4.8.1 which also outputs 240625. you can check it here
•  » » 6 years ago, # ^ |   -8 MikeMirzayanov, With due respect, will you check it, please??
•  » » » 6 years ago, # ^ |   +15 pow function returns double type result, (not int), so that the floating-point error could be happened. This behavior happened because of you, not server.You can reduce the error by using int(pow(len,5.)+0.5) instead of pow(len,5.).
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -11 Once I change //k = 1000000 this line, server is calculating in another way? HOW? How pow(len, 5) produce different result on same server when k is injected value manually?
•  » » » » » 6 years ago, # ^ |   +4 Pow arguments will be automatically casted into double, so there is no difference between int arguments or floating-point number arguments.If len is enough small, Pow(len,5) can still return wrong result. Why? Example, len=10. Your expectation is 100000, but the function could return 99999.99999. Because you wrote: int(pow(len,5)), 99999,9999 will be casted and became 99999.I don't know how statement k=1000000 affected to pow function. Your problem is not in this statement, you need to use more safe power function. Built-in pow function doesn't work too fast, and if arguments are enough large, errors will be caused surely.If you still want to use pow and other function returning floating-point result, when you cast, you must write something like this: n = int(f(x)+0.5).
•  » » 6 years ago, # ^ | ← Rev. 2 →   +14 "Problems with floating point numbers — the most often reported non-bug". GCC usually use wider floating-point types to compute expressions that can be computed at compile-time, which is permitted by C++ standard.
 » 6 years ago, # | ← Rev. 2 →   +2 Great contest for me... there were short description to make me known quickly what actually problem wanted... And the translation was awesome.... easy to understand...I'm really waiting for your next contest... :) Great ... Hats off ... :) cgy4ever
 » 6 years ago, # | ← Rev. 4 →   0 cgy4ever if possible prepare contest regularly , you are totally awesome . All problem setters should learn from you how to make an interesting round :D
 » 6 years ago, # | ← Rev. 3 →   0 What a great Contest. Great and clear description.but I just crack 1 problem. :'(
 » 6 years ago, # |   -6 Problems are short and clear to understand
 » 6 years ago, # |   -6 So stupid mistake in problem div2 B. I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.
•  » » 6 years ago, # ^ |   +3 A better phrase:I will never submit a code without some own tests as long as my programming intuition is not on its heights.
 » 6 years ago, # |   +1
 » 6 years ago, # |   -8 I'm sorry, but I can't find what is wrong with my code for Problem C Div1 Submission:5886576 I'm trying to find the card with maximum number one can take ( in each step ) Is there something wrong in my implementation or....?
•  » » 6 years ago, # ^ |   +5 Greedy doesn't work in this problem here is test that you will fail 2 1 2 3 1 100 1 
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -8 OH! What a pitiful mistake.....thanks!
 » 6 years ago, # |   0 How comes the Dp relation in Div2 Problem D that dp[v] = sum{dp[t] | dist(1,t) = dist(1,v) — 1}? I am not able to get it. Could someone please explain?
•  » » 6 years ago, # ^ |   0 If we have dk - 1[v] which contains the count of the shortest paths with length k - 1 from some s vertex to another vertex then it is easy to get the count of the shortest paths with length k.
 » 6 years ago, # |   -20 I think that test 7 in the problem B is wrong. Can anybody explain me?
•  » » 6 years ago, # ^ |   0 Problem B Div 2 ?
 » 6 years ago, # |   +3 Awesome round! I was Candidate Master before but now I am Master. At a point I was on the 7th place with A and C, and that felt really great. However, I couldn't maintain that wonder, but still, great problems and great round!
 » 6 years ago, # |   0 Congratulations! codeforces, I appreciate everything that you have done for us. we're gonna have to work together here!