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!
Wow, a new contest. Thanks for preparing problems and I think I will love this contest:) PS: Orz
Hm.. there's also a TopCoder SRM earlier on Monday. I wonder if I will be able to participate in both TC and CF :)
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
tourist has registered for both CF and TC contest today. :D
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!
tomek can repeat tourists double. if one of Egor's solutions not pass)
You spoke too soon :P
well, tourist didn't win the SRM, but won the Codeforces round. he had to win one of them!!
Your last contest had nice problems.
Thank you for creating another contest.
I'm definitely looking forward to the 1st contest in the Chinese new year! 新年快乐!
新年快乐
thx
Problem description was nice (and short too) of your last contest ...
Hope it here also ... :)
Your previous contest's problems were awesome, looking forward!..
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 ;) )
What is wrong with ur SHIFT key :)
No, I don't have any problem.i just wanted to make it interesting...
Sorry, misunderstood it :p
i think that he just wanted to make it appealing..
Actucally, to me, it' s a little bit hard to read. (Yes, just to me) Well I don' t learn English very well...
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 ;) )
Sorry, I apologize for my behaviours before. ThAnKs FoR YoUr FoRgIvEnEsS! Wish you a good luck today.
Good luck everyone~ This must be a good contest! :)
Мне кажется или все пытаются набрать как можно больше "Вклада".
Да, и ты один из них.
GL for every one
two contest in a day!
hard but fun! :D
Fail(( I've missed TC one
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!
YEAH . Most of them aren't going to participate :D
Don't worry, the round delayed because of dinner on Petrozavodsk Training Camp :)
Is the room bug rectified? :)
And my dinner!
In Russia there is the saying: War is war, but lunch is on a schedule.
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.
Petr. Training Camp sounds great =)
It certainly does :D I would like to have an uppercase dot character for avoiding such things )))
Wow! Is dinner a technical reason? :)
actually dinner is an important reason! :)
I want to rating under color of my eyes... (red) =D
:|
Can U shut your mouth??????? if you can't Ican do that for U......
sta-le-ar in gat mancarea
'technical'reason == dinner LOL :D
Extra time for "Codeforces Unavailable"?
Sorry for unstable work. It was a real stress test for server!
most of the solutions in problem B will fail, also my solution :( for k=10^9 n=1017
n is not a paramter I guess
Do 10^9 exist as an input in final test cases?
Mine doesn't fail for 10^9 but for 999997439. (N comes out to be 1017 :))
And for testcase 268435455 your solution will output graph with 1137 vertexes.
Great contest..Really enjoyed it Thanks alot
Shut up your trap!
where is the statistics of this round ? :)
Sure :)
good contest, good problems
When will the ratings be updated? UPD : Updated :D
I hope never :(
SUFFER!
its updated only in div2, upd: its updated now
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 have2
shortest paths, and1-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 only10
vertices... It seems that it' s easy to construct a graph with2^n
shortest paths. 2. If we devide the numberk
into a set of numbers which sum isk
, and all the numbers must be2^i( 0<=i<=32)
, then we can constuct a graph with paths I mentioned before. It is obvious thatn
won't be very large. Actually the problem can be solved correctly with this idea, but I' m so stupid that can' t work outyour 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
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.
2 + 32*2*32 > 1000
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
what is the easy solution in this way,please someone post how reduce nodes?
I decomposed k into 33 radix, max nodes count becomes approx 800.
Ohhh, yes. Thanks, I found my mistake. There will be about 1500 vertices when k is big enough...
My solution with the same idea: http://codeforces.net/contest/388/submission/5889570
I have checked ur code and found that our general idea is the same, but still don' t understand some details in ur code...
1-3 1-4 3-5 4-5 5-6 5-7 2-6 2-7
How does this graph have 4(2*2) paths? I see only 2*2 paths.
4=2*2, not 4*2*2
thanks cgy4ever, you're the best :D
two excellent rounds, I'm looking forward to your third one :)
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.
I don't know why this happens, but may be it will be a useful fact that this code:
gives same results whether "k = 1000000;" commented or not.
Then, we can see that result depends on this:
If we don't use type conversion, we'll get different results, if use — the same anyway. But why? :)
yes. Thanks. :)
But beyond type conversion, my code is only depend on whether k = 1000000 is commented or not. But, WHY???
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.
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
MikeMirzayanov, With due respect, will you check it, please??
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.).
Once I change
//k = 1000000
this line, server is calculating in another way? HOW? Howpow(len, 5)
produce different result on same server when k is injected value manually?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).
"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.
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
cgy4ever if possible prepare contest regularly , you are totally awesome . All problem setters should learn from you how to make an interesting round :D
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.
A better phrase:
I will never submit a code without some own tests as long as my programming intuition is not on its heights.
Other stuff
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....?
Greedy doesn't work in this problem here is test that you will fail
OH! What a pitiful mistake.....thanks!
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?
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.
I think that test 7 in the problem B is wrong. Can anybody explain me?
Problem B Div 2 ?
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!
Congratulations! codeforces, I appreciate everything that you have done for us. we're gonna have to work together here!