### MinakoKojima's blog

By MinakoKojima, 5 years ago, ,

Hello there!

Codeforces Round #172 will take place on Sunday, March 10th at 19:30 MSK(23:30 CST).

This is my second time participating in prepration a Codeforces Round. Last time assist with WJMZBMR is an unforgettable experience. This time, the hardest problems were created by Jiatai Huang(CMHJT) and others by me and Yuping Luo(roosephu).

Testers are Sevenkplus, WJMZBMR, pashka and Seter.

We gratefully acknowledge Gerald Agapov(Gerald) for his help in giving advise about the problems, Delinur for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

Here let me express my personal thanks to the Codeforces community, which has given me so much gleamy idea in the past two years.

Believe it or not, Codeforces has kept her feet in China's ACM community since last year. AFAIK, some of the hardest problems have been used as this year's Winter Camp homework for our National Olympiad in Informatics.

Also thanks to watashi, ftiasch and xlk. Discussing problem with all of you, has inspired me a lot.

500 — 1000 — 1500 — 2000 — 2500.

We are going to use a standard score distribution in both divisions.

The problemset is a little bit easier than last time, but we still believe, getting all of those five problems accepeted will be a challenging mission even for an seasoned International Grandmaster. The problemset has been marriaged with variety flavor. Take a glance over all five problems before going to coding might be a wise strategy.

UPD:

The contest is over, congratulations to the winners:

Div1:

Div2:

Congratulation to tclsm2012, who also solve the problem D!

We feel so pity to al13n, your last optimization for problem D is wrong. Problem D has a O(mklogn) algorithm. And we are extremely sorry to Jacob, your solution for problem E can pass most of the random tests but actually is wrong.

Jacob... can you explain your solution for us :)

We need collect some feedback about this round .. So the editorial will appear after a period of time.

UPD:

I used to hate those guys who set problems, but didn't write editorial at all! But when things turn to myself, I found it is really difficult to cover all cases. Anyway, it has been done.

•
• +186
•

 » 5 years ago, # |   +26 Very early announcement! Excellent!
 » 5 years ago, # |   +5 QAQ..
•  » » 5 years ago, # ^ |   0 123
 » 5 years ago, # |   +7 ymm
 » 5 years ago, # |   +38 Believe me . It will be a very interesting round. So , good luck and have fun
•  » » 5 years ago, # ^ |   -20 you have no chance to attend this contest. look at me!!!!!!! = = TAT(it's terrible to zhuangbi)
•  » » » 5 years ago, # ^ |   0 ... No .. The problem has been substituted ... Actually he didn't know what the finally problem it is. ..
•  » » » » 5 years ago, # ^ |   0 So you mean that he is going to participate???
•  » » » » » 5 years ago, # ^ |   0 Uw...That depends on himself ..
•  » » » » » 5 years ago, # ^ |   +4 Surely I will not participate......
•  » » » 5 years ago, # ^ |   +3 Ooooooooch , man ~ Are you crazy?
 » 5 years ago, # |   0 They are saying that the hardest problems were created.I think it's going to be interesting!!!
 » 5 years ago, # | ← Rev. 2 →   +7 I think it will be interesting round with 9 creators :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 ... Only setters and testers have saw the problems.)
•  » » » 5 years ago, # ^ |   -10 What about translator?!:) She translated and she didn't see the problems?! WOW...Perfect:)
•  » » » » 5 years ago, # ^ | ← Rev. 6 →   +1 Well, you are right .. Delinur isn't going to participate the contest after all .. We'll try our best on the confidential work of the problems, to ensure the competition run fairly. You can trust us on this point, seriously ~~ ... )
•  » » » » » 5 years ago, # ^ |   0 Thx...I hope that in this contest will not be users like xiao_dao or xiaodao_50216 like previous contest (I mean rng_50216) :)
•  » » » » » » 5 years ago, # ^ |   +10 ... And like peter50216?
•  » » » » » » » 5 years ago, # ^ |   0 Noo...i didn't mean peter50216 and rng_58...I mean only rng_50216...He registered 39 hours ago...before Round #171...
•  » » » 5 years ago, # ^ |   0 Maybe 4 problem-setter
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 ... Why not participate ? .. (I am definitely sure you will lost your red handle after this round.) Uw, actually we are short of men right now... How about helping us test one or two of them? 　(′▽〃)
•  » » » » » 5 years ago, # ^ |   +16 xiaodao: you should protect your solutions:these solutions are look very similar:On codeforces: 3158774 3157931On codechef: codechef1 codechef2
•  » » » » » » 5 years ago, # ^ |   +3 Micro Mezzo Macro Flation -- Overheated Economy haha I love C too.
 » 5 years ago, # |   +11 That's how you announce a serious contest, not 2 hours before the competition! I wish everyone did the same.
 » 5 years ago, # |   +15 it seems i am the only one holding a yellow handle among all the problem setters..lol
•  » » 5 years ago, # ^ |   +11 lol.. I think you can easily become red if you're willing to.
•  » » » 5 years ago, # ^ |   +1 yes, maybe, but not this time, because he isnt participating :D
•  » » 5 years ago, # ^ |   +17 And you have created the hardest problem I've ever seen...lol
•  » » 5 years ago, # ^ |   +10 Because I'm the lost thing lol
•  » » 5 years ago, # ^ |   +9 your avatar ... Can't look directly <_<
 » 5 years ago, # |   0 I'm wondering if I miscalculated or scheduled time for this round conflicts with TCO qualification round 1C?
•  » » 5 years ago, # ^ |   +6 TCO round is scheduled for Saturday, not for Sunday.
•  » » » 5 years ago, # ^ |   +8 Ouch... probably, I should sleep more. Thanks!
•  » » 5 years ago, # ^ |   0 No , it doesn't . TCO round 1C is on Saturday March 9th and codeforces round 172 is on Sunday 10th March .
•  » » 5 years ago, # ^ |   +8 We intended to set on Saturday .. .
•  » » » 5 years ago, # ^ |   -13 So is it going to be on Saturday which is today or on Sunday???
•  » » » » 5 years ago, # ^ |   +7 Why can't you read the topic before asking such questions?
•  » » » » » 5 years ago, # ^ |   +6 or see the timer on top-right part of the page, which shows how much is left till the contest.
 » 5 years ago, # | ← Rev. 2 →   +14 oh,I wasn't aware of this page because it's not on the top...and the discussing members & testers seems very great!! I believe the round will be an interesting one
 » 5 years ago, # |   +22 It would be an interesting contest :)
 » 5 years ago, # |   +2 Just wish CMHJT get well quick.^_^
 » 5 years ago, # |   0 Big Fans !
•  » » 5 years ago, # ^ |   0 I wish you can get fully accepted
 » 5 years ago, # |   -65 Пишите по русскому!
 » 5 years ago, # |   +7 I smell a lot of mathematics.
•  » » 5 years ago, # ^ |   +1 Hmm... Can you explain why?
•  » » » 5 years ago, # ^ |   0 He is right about that
 » 5 years ago, # | ← Rev. 3 →   +29 Haha WTF ??? ! Picture
•  » » 5 years ago, # ^ |   +4 whahahah lol
 » 5 years ago, # |   +9 I don't know it's my browser problem or nhandi graph really have logical problem ? btw it's a beautiful bug !
•  » » 5 years ago, # ^ |   +9 There is the same problem with my graph.
•  » » » 5 years ago, # ^ |   +5 Wow you guys have interesting graphs!!!
•  » » » 5 years ago, # ^ |   +5 and also rubanI think anybody participate in code forces rounds #170 & #171 simultaneously have same problem . maybe for a little mistake in set history of code forces #170
 » 5 years ago, # |   +11 Great! Wish we have a great night!
 » 5 years ago, # |   +10 Wish you all one more "Share it!" in your profile page :)
 » 5 years ago, # |   0 ym..
 » 5 years ago, # | ← Rev. 3 →   -11 Again 865 participants in Div 1. The record was not broken!:D
 » 5 years ago, # |   +56 Div. 1 A is boring...
•  » » 5 years ago, # ^ |   +24 Div. 2 C is boring, too...
•  » » » 5 years ago, # ^ |   -35 Is it joke? Don't you know, that those problems are same?
•  » » 5 years ago, # ^ |   +11 why boring? I've spent about an hour without any result :(
•  » » 5 years ago, # ^ |   0 But you had not solved it, right?
•  » » » 5 years ago, # ^ |   0 Could somebody explain me, how to solve it without formulas divination?
•  » » » » 5 years ago, # ^ |   0 For example, you can divide shaded figure into 8 triangles.
 » 5 years ago, # |   +20 I absolutely don't like this contest.
 » 5 years ago, # |   +9 The problems were really hard. Didn't like this contest.
 » 5 years ago, # |   +43 Should swap Div1.A and Div1.B
•  » » 5 years ago, # ^ |   +19 Well, I think B was harder conceptually to find algorithm, but A was harder to implement, and edge cases = annoying, also takes quite some time to solve on paper.
 » 5 years ago, # |   +1 I think it's so hard for div 2
 » 5 years ago, # | ← Rev. 3 →   0 some ideas about D div 2 (B div 1)? I wrote rmq and rmq1 for the second maximum, but i didn't invent something faster than n*n*logn...
•  » » 5 years ago, # ^ |   0 I think author's solution has O( n * log( 10^9 ) ) complexity
•  » » » 5 years ago, # ^ |   +30 There is easy O(n) solution using stack to find first next greater number for each number.
•  » » » » 5 years ago, # ^ |   0 What a shame, I thought it is O(n^2) and didn't solve this problem...
•  » » » » » 5 years ago, # ^ |   0 me too ! :|
•  » » » 5 years ago, # ^ |   0 There's an O(N) solution based on all nearest smaller values. I think it's a shame the constraints weren't higher.
•  » » » » 5 years ago, # ^ |   0 10^5 is enough to forbid O(n^2) solution
•  » » 5 years ago, # ^ |   +5 I was thinking about this too, but N^2 for N = 10^5 is too slow for sure...
•  » » 5 years ago, # ^ |   0 I use only one rmq, each time fix a max, find second max in left and right, then recursively on each side. which gives O(n * log(n) * log(n)) algorithm. http://codeforces.com/contest/281/submission/3284484
 » 5 years ago, # |   +5 Problem Standard in DIV-2 was A,B,D,E,E :S
•  » » 5 years ago, # ^ |   +8 more like A,C,E,E,E i thinknearly solved B at the end, maybe if 2 or 5 more minutes :(
•  » » » 5 years ago, # ^ |   0 B wasn't so difficult, you can try all bs from 1 to n-1 in limit...
•  » » » » 5 years ago, # ^ |   0 in my solution, i try from n to 1, so that it will replace the previous denominator if it has same rate of errorhere is my submission which is accepted (after the contest :P) http://codeforces.com/contest/281/submission/3284962
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Correctly is A, B, D, D, E.
 » 5 years ago, # |   -15 I love xxx :))I think this contest had too much mathmatical problems :|
 » 5 years ago, # |   +4 Nice problems, thanks for the contest. I almost solved C, but maybe next time...
•  » » 5 years ago, # ^ |   0 My C was almost correct, I had to try to solve it immediatelly after B and not try to solve D first...
 » 5 years ago, # | ← Rev. 2 →   -9 It's the first time I send my uncompiled code in DIV2 A Time -> 1:12 :D
•  » » 5 years ago, # ^ |   +6 Keep us informed.
•  » » 5 years ago, # ^ |   -20
•  » » » 5 years ago, # ^ |   0 Big useless images make me cry.
 » 5 years ago, # |   +23 Why doesn't system test start?
•  » » 5 years ago, # ^ |   +2 Soon ...
 » 5 years ago, # |   +5 too much mathematics, A (div2) is nothing but a fun, and others are harder for div-2 contestants.
•  » » 5 years ago, # ^ |   +6 Div2 B is rather easy
•  » » » 5 years ago, # ^ |   0 isn't it a ternary search problem?
•  » » » » 5 years ago, # ^ |   +1 No need, you can try every denominator and binary search to find the numerator.
•  » » » » » 5 years ago, # ^ |   0 i did it, and get wa on 6th pretest, then i checked for numerator, numerator+1, numerator-1 for every denominator. i m sure of getting system failure :(
•  » » » » » 5 years ago, # ^ |   +4 or you can calculate numerator directly in O(1)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +6 It was not necessary,easy math in O(N) :)
•  » » » » 5 years ago, # ^ |   0 A bruteforce setting the denominator and approximating the numerator in small iterations passes the test.CODE
 » 5 years ago, # |   -10 why system test is not stated yet? a lot people are going to have system failure on B (div-2) i guess.
 » 5 years ago, # |   -23 В-div2 — это тернарный поиск ?
•  » » 5 years ago, # ^ |   -11 я бинпоиск отправил, претесты прошел:)
•  » » » 5 years ago, # ^ |   -12 А как ты делал ? У меня идея была такая — для каждого знаменателя от 1 до n считать тернарником минимальное значение модуля, а потом из всех выбрать минимум.
•  » » » » 5 years ago, # ^ |   -10 Да, нужно было перебирать значение знаменателя искомой дроби, а числитель, при фиксированном знаменателе задается единственно, что позволяло решать задачу за O(n)..
•  » » » 5 years ago, # ^ |   -6 систесты не прошел:) WA тест 33
•  » » 5 years ago, # ^ | ← Rev. 2 →   -12 перебор по знаменателю спокойно проходит. Числитель при известном знаменателе находится по простой формуле.UPD. систесты прошло
•  » » 5 years ago, # ^ |   -6 Я тупо перебрал знаменатель. числитель выбирал один из int((i * a + 0.0) / b) и int((i * a + 0.0) / b + 0.5) сравнивал если меньше погрешность запоминал числитель и знаменатель. Самое главное если погрешность равна, а знаменатель меньше запомнить опять числитель и знаменатель.
 » 5 years ago, # |   0 when starts testing?
 » 5 years ago, # |   0 Interesting, systests didn't start and I moved from 255. to 254. ...
 » 5 years ago, # |   +68 The problemset is a little bit easier than last time. I wonder how hard the problems were last time.
•  » » 5 years ago, # ^ |   0 :D
•  » » 5 years ago, # ^ |   0 Even tourist solved only A&B....
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 No, he did A B C in 33 minutes and is 7th.Edit: Sorry, I talk about current contest.
•  » » 5 years ago, # ^ |   +5 I think it's harder than last time, this time the Problem E is too hard to have an correct solution,but the Problem C is simpler.
 » 5 years ago, # |   +15 Good problems! tnx! :)
 » 5 years ago, # |   +2 I hope, there won't be 50 tests in A div.2, or else the system testing will be too long. For such a trivial problem 10 test cases are more than enough.
 » 5 years ago, # |   +9 This is the hardest contest i ever participate... But i like the Problem Div.2 B.I spend almost two hours with so excitement.(Though i can't solve it yet.)
•  » » 5 years ago, # ^ |   +5 Just enumerate the denominator....you can calculate numerator quickly...O(deno) You may find it interesting if you have noticed Python's Fraction.limit_denominator method...O(log deno)
•  » » » 5 years ago, # ^ |   0 Fraction.limit_denominator fails the tests :(http://www.codeforces.com/contest/281/submission/3278048
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +6 maybe you can try Fraction(x, y) to construct a fraction x/y >>> fractions.Fraction(6/7) Fraction(7720456504063707, 9007199254740992) >>> fractions.Fraction(6,7) Fraction(6, 7) 
•  » » » » » 5 years ago, # ^ |   0 Accepted :| "Easy come, easy go" :'( Thanks alot
 » 5 years ago, # |   +1 Thanks for interesting problemset, but it was hard)
 » 5 years ago, # |   +52 Oh damn, my E solution failed on test 101...
•  » » 5 years ago, # ^ |   +37 I'm so sorry...Your solution was totally wrong but accept all the random testdata...So I generated the test 101...
•  » » » 5 years ago, # ^ |   +26 Turns out you don't need to be a contestant in order to challenge solutions. ;)
•  » » » » 5 years ago, # ^ |   +23 He is responsible for the problem E bcz the writer is in hospital ...
•  » » » » 5 years ago, # ^ |   +10 In fact I'm one of the testers lol..I've mentioned it but got too much negative feedback so it's hidden T_T..
•  » » » » » 5 years ago, # ^ |   +1 Can you explain then what kind of test is that (testing log doesn't show much)?
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Just random data with N=6000,B-A<=1000...I didn't have thought I could make your solution WA but finally I did it..Thanks to my random data generator..Your solution got 3 WA in 10 with this kind of data.
•  » » » » » » » 5 years ago, # ^ |   +34 Hm, let me get this straight — you've added a test to fail Jacob's solution during or after the contest?
•  » » » » » » » » 5 years ago, # ^ |   0 During ... actually we want let him know about that during the contest but we can't ... His solution seems strange for us ..
•  » » » » » » » » » 5 years ago, # ^ |   -13 Did you add test 52 for problem C too?
•  » » » » » » » » » 5 years ago, # ^ |   +9 No..
•  » » » » » » » » » 5 years ago, # ^ |   +8 I only make 50 tests for Problem C.I think the test 51&52 is add by challenge.The successful challenge will be check by system and if the hacked solution can pass systest, then that test will be added
•  » » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I misread your answer, sorry.
•  » » » » » » » » 5 years ago, # ^ |   +3 Please forgive a tester without experience..Next time I'll make data not too weak...T_T
•  » » » » » » » 5 years ago, # ^ |   +44 I think it's not good to add tests using participant solution.
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +20 Believe or not,we have prepared 4 data by this generator and rest by weak generators,and he passed them all.But when we use this generator for 6 more data,he got WA in 3 of 6...This is my first time to prepare problems for CF,I only made 12 large data in 100 T_T...
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +42 .. Did you have a gmail?. I'll send it to you as a gift :)
•  » » » » » 5 years ago, # ^ |   +5 I think the challenge work is up to contestants, and if a tester like you challenge someone, you should at least show him a message during the contest warning that you've challenged him. Seems to be kinda unfair.
•  » » » » » » 5 years ago, # ^ |   +30 So If a wrong solution didn't get challenged then it would be considered the same as the correct one? I think it is more unfair. the basic rule in Contests like CF or TC is that the solution should be CORRECT to get the scores, if the solution is indeed wrong, then it shouldn't passed of course. You may think that the test data is weak. but It is really hard to consider all possible algorithm to generate all anti-test. As today's case, his solution is indeed an wrong greedy. A experienced coder like Petr will find this is wrong and won't try that, but if some one simply come up with it without proof and accepted, isn't that kind of unfair?
•  » » » » » » » 5 years ago, # ^ |   -7 Yes, you're right. But at least you should warning him during the contest, so he'll be able to see what's wrong or either find the correct solution.
•  » » » » » » » » 5 years ago, # ^ |   +19 Umm, we indeed thought of things like that but don't know how. but anyway the systems only says that he pass the pretest,that doesn't mean anything else.passing pretest also has the chance of failing.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 6 →   +11 Unfortunately there are a lot of obviously "wrong solutions" which pass system tests and got accepted. (See this, for example http://www.codeforces.com/blog/entry/5947#comment-113634 ) Of course one needs to be lucky to get points for those, but by challenging a particular one you don't give any chance to its author. Did you prove that all other submissions of all of the problems produce correct output for any valid test case? What solution is considered to be correct is an interesting question. As I know, if we use only subset of a functional language, we can indeed prove that the outputs of it and the correct one are identical for all possible inputs from given range efficiently. We can even write a checker for this. However, for CF/TC problems and procedural languages I always thought that solution is correct if it passes system tests.
•  » » » » » » » » 5 years ago, # ^ |   +5 If wrong solution's passing is because of good luck then isn't wrong solution's being challenged because of bad luck?:) I apologize for this but I won't discard test 101.I believe rating second,learning first.Correct solution for E is magical and worth learning.Why don't we look forward to it instead of stuck in a wrong solution?:)
•  » » » » » » 5 years ago, # ^ |   +8 I'd like to do so but I can't..because I don't know how to touch with him..I apologize for our weak data at the beginning :) In fact this kind of data(N=6000 B-A<=1000) his solution can accept 7 in 10~
•  » » » » » » » 5 years ago, # ^ |   -9 I'd like to know is this the first time when tests were added during contests or is it a common practise? Maybe it's a question not to you, but to Gerald
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 I think DIV1 B has weak tests too. just run 3284652 or 3283083 with test like this: 100000 100001 99999 99997 ... 1 ... 99996 99998 100000 
•  » » » » » » 5 years ago, # ^ |   +24 It's so strange for a contest with so many problem setters and problem testers (with high ratings) that has weak data in three problem out of seven. (Div1 B, C, E)
•  » » » » » » » 5 years ago, # ^ |   -12 What is the problem with tests to the task C?
•  » » » 5 years ago, # ^ | ← Rev. 5 →   +23 For me this is unfair. One could use a random generator with a fixed seed (say, 123467) and it is always possible to find a specific test to fail this kind of solutions. Solutions using randomized algorithms based on some random assumptions (say, there are less then 100 tests) do not have to work for 100000000 tests you can generate on your own using full contest time and prepared generators to fail them.
•  » » 5 years ago, # ^ |   +17 We're so sorry about this ...... )
•  » » » 5 years ago, # ^ |   -12 That doesn't make sense. If you're sorry, then you think you did something wrong. If you did something wrong, correct it. Is no one able to correct the results in this special case, considered unfair by many members, maybe majority?
•  » » » » 5 years ago, # ^ |   +16 If you're sorry, then you DON'T necessarily think you did something wrong.people often say they are sorry when they learn someone who they just asked after had died for example )
•  » » » » » 5 years ago, # ^ |   0 Yes, you do think you did something wrong. In your example you did that accidentally, and if you could, you would withdraw your hurting words. But you can't do anything, so you say sorry. Please don't limit yourself to saying sorry when you can revert something you did. Just do it.
•  » » » 5 years ago, # ^ |   0 Now I it's apparent that you made right decision and everybody's happy. You had little time to make this decision, but you did it right. Even Jacob would be unhappy to win with incorrect solution. So you needn't be sorry :) I am sorry for my harsh words.
•  » » 5 years ago, # ^ |   +10 Cool A solution BTW.
•  » » 5 years ago, # ^ |   +10 it's my fault... better to say my heart trouble..?
 » 5 years ago, # |   -34 kapec b-shka u mnogih upala
 » 5 years ago, # |   +2 I hope the editorial be published soon, like the announcement!
 » 5 years ago, # | ← Rev. 2 →   0 What's up with B? number of failed after test 10 ~ number of succeeded So, the thing is that pass rate for is well near 50%Guys, is 10^-6 realistic for Python float?
•  » » 5 years ago, # ^ |   0 my God, hash somehow blowed the text up!So, the thing is that pass rate for is well near 50%
 » 5 years ago, # |   0 How to calculate eps in Bdiv2?
•  » » 5 years ago, # ^ |   0 I tried to use 1e-12 as EPS, but solution was challenged. Without EPS handling solution passed system tests.
•  » » 5 years ago, # ^ |   +1 In order to avoid using float number in problem B(div2), you may can use stern-brocot tree, I think.
•  » » » 5 years ago, # ^ |   0 Or just implement your own fraction class.
 » 5 years ago, # |   +63 Oh, okay
•  » » 5 years ago, # ^ |   -16 bugs in topological sort.
•  » » 5 years ago, # ^ |   0 -74 in round #171 and your overall rating increases. lucky :)
 » 5 years ago, # |   +12 http://www.codeforces.com/profile/Obaidasee last 4 contest in my rating graph!!! (funny BUG) :P
 » 5 years ago, # |   -24 Who added test 52 for problem C? It doesn't look like prepared test case and it failed 4 people including me, because of wrong calculation of a node depth in a tree. I don't think it was a main challenge in this task and it was the last test...
•  » » 5 years ago, # ^ |   0 Well, I mean, the problem didn't say the edges had to go a certain way?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -8 Yes, but I'm just interested if test 52 is one of the successful hacks or it was also added by organizers during the contest to make solutions of 4 people fail.I think that it might be the successful hack made at 1:58:14, that was added to the system tests — what a fuc.ing bad luck...
•  » » » » 5 years ago, # ^ |   +1 Wait, does this work like topcoder such that successful hacks get added to the system tests?
•  » » » » » 5 years ago, # ^ |   +1 yes.All successful hack would be added in sys-test.
 » 5 years ago, # |   -14 tourist isn't codeforces target after this contest =(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +62 hahahah
•  » » » 5 years ago, # ^ |   +13 tourist rating also goes below 3000 in div 146. coincidentally writers was same.
 » 5 years ago, # |   0 @Admin ....my solution of D is showing Skipped final test....Is there any problem in system testing.?
 » 5 years ago, # |   0 problem b div2 test 33's answer is 1/1 but i think 2/2 , 3/3 , 4/3 are another solutions of it. :( a lot of contestants failed on test 33
•  » » 5 years ago, # ^ |   +1 If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.
•  » » » 5 years ago, # ^ |   0 why i forgot that????? :|
•  » » » » 5 years ago, # ^ |   +3 Why are you asking this question to ME? :D
 » 5 years ago, # | ← Rev. 3 →   0 WTF? this solution gives answer 4/3 on test#33 7 6 3 why it got AC?UPD: Link: http://codeforces.ru/contest/281/submission/3277121 UPD2: I compiled this code in VS 2012
•  » » 5 years ago, # ^ |   0 What solution are you talking about?
•  » » » 5 years ago, # ^ |   0 can u tell me the meaning of Skipped final test.?
 » 5 years ago, # |   +1 Waiting for comprehensive editorial from you, xiaodao ^_^
 » 5 years ago, # |   +12 I don't know what to say... just look at this link : http://codeforces.com/bestRatingChanges/220401
 » 5 years ago, # |   0 [user:xiaoda] why is it showing skipped in final testing?? please reply..
•  » » 5 years ago, # ^ |   0 Try to send a personal message
•  » » 5 years ago, # ^ |   0 I didn't know ... > < 。。。
 » 5 years ago, # |   -8 Great Problems , Fantastic Contest , Amazing System Tests , Brilliant Announcements. :)
 » 5 years ago, # | ← Rev. 2 →   0 I have an answer about test case#31 B Div2 (99997 99999 99996):Why the answer should be 49999/50000,if 49998/49999 is a better result, and is "nearest" to 99997/99999 ???just try to use calc, and you will see it:99997/99999 = 0,99997999979999799997999979999849998/49999 = 0,99997999959999199983999679993649999/50000 = 0,99998
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 You're right.I think if this round will be retested a lot of solutions will get accepted, and my too.
•  » » » 5 years ago, # ^ |   0 Nope)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 99997/99999 — 49998/49999 = 0,00000000020000600014000300006249999/50000 — 99997/99999 = 0,000000000200002000020000200002You're wrong, dude.
 » 5 years ago, # |   0 Can someone explain in details how problem D div2 is solved ? Thank you.
•  » » 5 years ago, # ^ |   0 Avoid floating point calculation totally, use long long etc i.e. x/y < a/b iff x*b
•  » » » 5 years ago, # ^ |   0 I was talking about D :)
•  » » » » 5 years ago, # ^ |   0 lol,you can use stack to get next max after a number using stack.O(n) algo.
•  » » » » » 5 years ago, # ^ |   0 I saw the solutions, I just wanted theoretical explanation.
•  » » 5 years ago, # ^ |   +5 I solved it choosing the 'easy' way, ommiting any special XOR properties. We can see that there are only O(n) candidates which we should check e.g. pairs (f, s) such that TwoHighest(l..r) = (f, s).Let's get some f and find the nearest, higher s on the right: f s that some TwoHighest(l..r) = (f, s'), because if range (l..r) contains both f and s', then it contains s, but fleft way.For each number, we find nearest higher number on the left and right. Then check every candidate(pairs (i, right(i)), (i, left(i))) and print the maximum result.How to find nearest higher number on right(left): Have the stack A after proceeded(0..f-1) numbers(top(lowest)->down(highest)). When we get S[f] = x, we look at A, erase every S[s] < x and set Right[s] = x.
 » 5 years ago, # |   +1 wow i only solved A for 498 points (should have solved B too, i made a very silly mistake) and my rating increased by 140! my sincerest thanks to whoever assigned the new ratings! :) :P
•  » » 5 years ago, # ^ |   0 Aren't they assigned automatically?
•  » » 5 years ago, # ^ |   0 i'm not sure, but my point was thanks to the administrators who are in charge of assigning ratings after contests, as my rating increased drastically after solving just one problem!
 » 5 years ago, # |   +10 Just curious, is there also an O(n) solution if in div2.D, the "lucky number" of S[l..r] is defined as the xor of the maximum number and the minimum number in S[l..r]?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 Curious about it too.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 http://ideone.com/vix2hLSadly, on the contest I didn't see O(n), I was writing inner loop with break on bigger number found. 5 minutes after contest i've wrote this 67-line(it was simply real_i before, and it was O(n^2) on 6 1 2 3 4 5 6 test).Sorry for bad grammar in ideone comments. I think I should go to bed nao~.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Uh, I've misread question, sorry.I guess minimum xor maximum is O(N^2). Suggest this input: 6 1 2 3 4 5 6. You need to xor 1 with 2 3 4 5 6. Then you need to xor 2 with 3 4 5 6, then you need to xor 3... You can't skip any of them.
•  » » » 5 years ago, # ^ |   0 I thought about this too. But I wonder if there are any mathematical properties can be explored in XOR operations to improve performance.
•  » » » » 5 years ago, # ^ |   +5 I think xor in this problem is like "function of two args, returns some predictable number, which is not really dependent on size of args". So large_num xor large_num doesn't allways equals large_num, and you need to cound all xor's to get the answer.But if there's some magical properties, it will be nice if someone explain.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I guess there's an O(n) solution, as my one was O(n) and failed test #13 which offered a special case.Let's denote our two target values as Big and Small.The idea is following: at first assume that there are two numbers in the whole sequence with different positions of the first '1'in the binary form. Then the two target values should differ in that 'first-1' position. That means, that the Big has to have the first '1' at the same position as the max value of the sequence does. That means that we should look for the Big only among such values, and the Small among the rest. So, we just take the sequence as a set of intervals [ Big?, Small?, ... , Small? ] and [ Small? , ... , Small?, Big? ] and check every one of them for linear time. Total length of those intervals is less than 2n.The last case, which I personally failed, is when all values have the same 'first 1'position. In this case.... well, at least one could subtract a corresponding degree of 2 from each one start again.You can reference my code, it's rather short)
 » 5 years ago, # |   0 1D's TL should have been 3s..Then the obvious O(k^2logn) solution would get TLE.
 » 5 years ago, # |   +9 tutorial for 1C,1D and 1E in Chinese https://www.13331.org/420.html
•  » » 5 years ago, # ^ |   +1 Chinese..... = =|||||
 » 5 years ago, # |   0 Well the contest was great!!! Thanks for the problem setters.
 » 5 years ago, # |   +3 He is an iranian : http://codeforces.com/bestRatingChanges/6073 Faghat bara inke ma ham ye commenti dade bashim .... :D
 » 5 years ago, # | ← Rev. 2 →   +5 There's also an issue during testing:The Problem D has the correct solution O(mklogn) , but the constant is not small. It also has an small constant approach O(mk^2logn).During test I suggest that the TL shouldn't be very large because the O(mk^2logn) solution may pass it.But indeed the difference between slow Java O(mklogn) and fast C++ O(mk^2logn) is minor. So if we want Java solution passed, we can't keep C++(mk^2logn) solution TLE. As a result, some competitor passed it by an straight forward O(mk^2logn) solution, which is not really expected.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +17 So you should set k <= 100 and increase time limit and no problem...Edit: Or you should stress test it until you find such a test that it gets TLE.
•  » » » 5 years ago, # ^ |   0 Actually during the contest,only liouzhou_101 got AC. not too bad..
•  » » » » 5 years ago, # ^ |   +3 Above all, Orz Shenben WJMZBMR && Chairman Fotile... I'm sorry for that my solution is O(m·k^2·logn) with highly optimized. In fact, I have no ideas about a O(mklogn) solution. Just waiting for the tutorial...
•  » » » 5 years ago, # ^ |   +8 actually in standard solution,it takes O(logn) per update,O(klogn) per query. So limiting the sum of k to 10^5 would be ok.
 » 5 years ago, # | ← Rev. 3 →   +73 Now, since some people were asking for my solution of E, I'll describe briefly the main idea.First of all let's build a mechanical system that would solve the given problem. The system consists of: particles with coordinates y[i] along one axis. deformable string, connecting those particles to points x[i]. Their potential energy would then be (x[i] — y[i])^2 hard links, connecting adjacent particles (y[i] to y[i+1]) to enforce (a <= y[i+1]-y[i] <= b) walls, preventing particles from violating constraints (1 <= y[i] <= q) Now the problem is to model this system and find its equilibrium. The key point is to add particles one by one. Apparently particles can only interact via hard links (item 3 in system description), so new particle can either drag some of the previous particles down or up, forming a "critical interval" (with difference between adjacent y's being equal to a or b). In my solution I simply iterate through the length of the critical interval to find the moment, when it stops interacting with preceding particles.I honestly believe, that overall my solution is correct, but most likely I missed something when accounting for wall-particle interactions. There is an obvious question arising about uniqueness of mechanical equilibrium in the described system, but in my opinion there isn't any constraint that could lock the system in a local minimum.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +19 Attention to this data: 2 24480023 3888 4569 628100 637054 Your solution gives correct answer: 630292.500000 634861.500000 9614112.500000 But when n=3: 3 24480023 3888 4569 628100 637054 637264 It gives wrong answer: 630292.500000000 634861.500000000 639103.000000000 12996033.500000000 `It seems you don't put forth your strength to drag first two particles down :)I read your code and believe that without "derivative" it can hardly be correct..I insist that your solution was a kind of wrong greedy idea because you only focus on "critical interval",and it may not be always right.If I haven't understood your idea correctly,can you explain it again for me? Sorry for my bad English. (>_<) BTW,I used to think your solution only works when all the delta is close to A or B,but it proves to be incorrect :) And your idea is a bit close to our correct one.
•  » » » 5 years ago, # ^ |   0 It seems I haven't properly dealt with the case when one critical interval shares one particle with another one. In that case verifying the equilibrium for that particle becomes more complicated.
•  » » » » 5 years ago, # ^ |   0 Whatever,you are the hero in this round! :) Can you forgive me for what I have done?
•  » » » » » 5 years ago, # ^ |   +19 From my point of view, that was absolutely valid in this particular case to do what you did.Since it was a clear flaw in my implementation, that test should've been there prior to the beginning of the contest (just for the reason that it's clearly rather special case) as well as many similar tests (say, a test with answer "+a +b +a +b ... "). Your only fault was to rely on random test generator instead of manually finding some interesting cases.
•  » » » » » » 5 years ago, # ^ |   +8 It's so kind of you!Thanks!Now I feel much better :)
•  » » » 5 years ago, # ^ |   +11 Fixed.3314820
 » 5 years ago, # |   0 Well, I think the problems were very nice and easy to understand. Good job! ;)
 » 5 years ago, # |   +1 For div1 B...I tested the case#3 on my PC and the answer is correct,but the result is different on CF..
•  » » 5 years ago, # ^ |   0 You can try comparing double numbers as fractions with equal dominators.
•  » » » 5 years ago, # ^ |   0 Div1..not Div2
 » 5 years ago, # |   +12 When will be the tutorial published?
 » 5 years ago, # |   +5 Can someone give me a hint on problem DIV1 C (Div2 E)
•  » » 5 years ago, # ^ |   +2 I can tell you that the answer is the sum of 1.0/depth[v] for all vertexes in graph.
•  » » » 5 years ago, # ^ |   0 Why is that correct?
•  » » » » 5 years ago, # ^ |   +10 The answer is the sum of probabilities of direct removal of each vertex. Let's observe that in order to remove a specific vertex from the tree, you need either to remove it directly, or to remove one of its parents. All these choices are equiprobable, and their count is depth[v], so the probability of direct removal is 1 / depth[v].
•  » » » » » 5 years ago, # ^ |   0 why__ "The answer is the sum of probabilities of direct removal of each vertex." and why " the probability of direct removal is 1 / depth[v] but not 1/n
•  » » » » » » 5 years ago, # ^ |   0 it is explained here.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 If that is correct, then the answer to example #2 should be 1+1/2+1/3=11/6 instead of 2, right??Edit: Forget it, I see my mistake now
•  » » » » 5 years ago, # ^ |   +7 Using mathematical induction, suppose, that it is valid for some graph, ExpMoves = Sum{1/deep[i]}. Let add a leaf with deep V. The added leaf can be choosed with 1/V prob. So in case of 1/V prob the answer is ExpMoves + 1. And in case of (V-1)/V prob the answer remains ExpMoves. So, expected moves after adding a leaf: ExpMoves' = ExpMoves * (V-1) / V + (ExpMoves + 1) / V = ExpMoves + 1/V.
 » 5 years ago, # | ← Rev. 2 →   0 How to solve E(Sequence Transformation)? I think I have found an O(n^2) dp solution,but got TLE on test case 8,how to opatimization
•  » » 5 years ago, # ^ |   0 http://codeforces.com/blog/entry/6952I'll tell you the method in detail, but you need tell me how to solve this .. ( ⊙ o ⊙ )http://www.spoj.pl/problems/NOTOKNOT/———————————————— Generally .. There are 2 different ways to solve this problem so far... One is use a datastrcuture to maintain the derivative function ... Another way is doing a dp algorithm base on a prove.