Привет всем!
В понедельник третьего февраля 2014 года в 19:30 по московскому времени состоится Codeforces Round #228 (Div1 + Div2).
Этой мой второй раунд на Codeforces (кликните сюда, чтобы посмотреть предыдущий). Как обычно, в раунде будет семь задач: две — только для Div2, две — только для Div1 и три общие задачи. Точно так же, как и в прошлый раз, главным героем задач раунда будет лиса Ciel.
Благодарю Gerald за тестирование задач и MikeMirzayanov за проект Codeforces и систему Polygon.
Желаю удачи и фана от решения задач!
Распределение баллов будет анонсировано позже. А разбор задач будет опубликован сразу после системного тестирования.
Кроме всего прочего, вчера в Китае отмечали новый год. Поздравляю всех, кто отмечал этот праздник! И, конечно, я очень рад, что именно я автор первого контеста в новом году.
Update1: Приятная новость для участников Петрозаводских сборов. Top 20 участников сборов по итогам этого раунда, которые придут на закрытие, получат футболки от Codeforces.
Update 2: Распределение баллов по задачам стандартное. (500-1000-1500-2000-2500).
Update 3: Приносим извинения, раунд перенесен на 10 минут по техническим причинам.
Update 4: Продолжительность соревнования увеличена на 5 минут.
Update 5: Contest ended, thanks for your participating! I'll post the editorial soon.
Update 6: разбор.
Победители:
DIV1:
К сожалению, никто не решил задачу Е. Решение Egor-a могло пройти тестирование, если бы TL был бы равен 7 секундам, вместо 6. Какая жалость!
DIV2:
Только они решили все предложенные задачи!
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.
На этом контесте я буду пить не чаёк, а яжку
К контесту готов!
И где только вы такие картинки берете?!
Как анонс увидел, сразу сфотался
как ты нашел этот сайт? xD
Я, в отличии от некоторых, зелененьким не был
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.
А что за система Polygon??
https://polygon.codeforces.com/ Там и готовят раунды.
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!
Как решать div2 D — div1 B?
First we need to know how to calculate the number of different shortest paths from vertex 1 to vertex 2: it can be done by dp: dp[1] = 1, dp[v] = sum{dp[t] | dist(1,t) = dist(1,v) — 1}, then dp[2] is our answer.
We need to do dp layer by layer. (first we consider vertexes have distance 1 to node 1, then vertexes have distance 2 to node 1 and so on.) So we can construct the graph layer by layer, and link edges to control the dp value of it.
My solution is construct the answer by binary express: If k is 19, then we need some vertexes in previous layer such that the dp value is 16, 2 and 1. So we just need a way to construct layer with dp value equals to 2^k.
In the first layer, it contains one node: 1, it has the dp value 1. In the next layer, we can construct 2 nodes, with dp value equals to 1. (We use [1 1] to denote it). And the next layer is [1 1 2], then [1 1 2 4], [1 1 2 4 8] and so on. So we need about 30 layers such that gets all 2^k where k < 30. It uses about 500 nodes.
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.
Давайте, что ли, сделайте какую-то систему пожертвований а-ля «Когда codeforces требуется вам, он к вашим услугам; а теперь codeforces нуждается в вас!». Может, хоть это устранит ужасные лаги в конце (почти) каждого контеста. Многие, наверное, пожертвовали бы n рублей, в сумме неплохо бы получилось :)
Great contest..Really enjoyed it Thanks alot
Shut up your trap!
where is the statistics of this round ? :)
Sure :)
Питон в одной из посылок отображался как-то так, со сбитыми отступами. Поскольку это питон, читать это было печально.
Это была 5885959, и это так отобразились знаки табуляции.
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 have2shortest paths, and1-3 1-4 3-5 4-5 5-6 5-7 2-6 2-7so that there' ll be4(2*2)paths,8(2*2*2)paths with only10vertices... It seems that it' s easy to construct a graph with2^nshortest paths. 2. If we devide the numberkinto 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 thatnwon'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
2036 -> 2199 So close... Не заслужил видимо :)
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 = 1000000this 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!