### MinakoKojima's blog

By MinakoKojima, 7 years ago,

Greeting!

Codeforces Round #259 (Div. 1 and Div. 2) will take place on August 1st, 19:30 MSK.

Setters are: sevenkplus, xlk and me.

Testers are: vfleaking, GuyUpLion, ztxz16 , CMHJT and Trinitrophenol.

Many thanks to Gerald for his help in giving advise about the problems. And we gratefully acknowledge MikeMirzayanov and his team, who bring us the world best competitive programming platform!

Tonight, you will come to Equestria and help our Friendship Princess — Twilight Sparkle to solve those intractable challenges one after another.

Twilight Sparkle is a main protagonist of the series — My Little Pony: Friendship Is Magic.

She is a female unicorn pony who transforms into an alicorn and becomes a princess in the third season of the series. She has a cutie mark of a 6-pointed magenta star with a white one behind it and 5 more smaller ones at each end of the magneta star.

Of course, I guarantee not knowing the storyline and setting won't hold you back from solving these problems~

##### UPD

In Div. 1, scores for each problem will be 500-1000-1500-2500-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2000-2500.

##### UPD

Contest is over! Congratulations to the winners! Here are the top 6 in Div.1 division:

And here are the top 6 in Div.2 division:

Editorial is here.

• +462

 » 7 years ago, # |   +66 Of course, we guarantee knowing those background storyline and setting won't help you to solve any of our problems.A pedantic note: I think you should instead guarantee that not knowing the setting won't hold you back from solving these problems. The reason is knowing this particular background might bring to your life some friendship which -- as we all know -- is magic. And noone should doubt that magic can help them solve tough problems.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +12 Exactly! Thank you for remind me this! ~
•  » » » 7 years ago, # ^ |   +15 oh. another chinese round ~
•  » » » » 7 years ago, # ^ |   +21 Codeforces Round #254 (Div. 1)Codeforces Round #FF (Div. 1)Codeforces Round #257 (Div. 1)Codeforces Round #259 (Div. 1)Chinese Div1 got a Ultra kill!! Someone stop it :D
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Maybe they're going to do a rampage.
•  » » » » » » 7 years ago, # ^ |   0 haha but , I DON'T WANT TO LOSE RATING :((((
•  » » » » » » 7 years ago, # ^ |   0 But the next step is Monster Kill...
•  » » » » » » » 7 years ago, # ^ |   0 why it's not first blood
•  » » » » » » » 7 years ago, # ^ |   0 GIFF EZ CONTEST
•  » » » 7 years ago, # ^ |   0 Horses are aliens :)
•  » » 7 years ago, # ^ |   +19 I don't know whether it is also that popular in other countries, but in Poland it is very common to name function returning least significant bit a "MAGIC". int MAGIC(int n) { return n - (n & (n - 1)); } So, are you suggesting that this function will help? Maybe some Fenwick trees :P?
•  » » » 7 years ago, # ^ |   +3 Why not n&-n?
•  » » » » 7 years ago, # ^ |   +25 I hate this n&-n thing xd. That is very strongly depending on system of representing it in a computer. Everyone who knows what is a binary system can agree with my version but to get your version work we need some kind of weird arrangement how to represent negative numbers and fact that it's working is rather a funny coincidence. n&-n is easier to remember, but n — (n & (n — 1)); is easier to come up with on your own and much more reasonable in my opinion.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 (never mind, I messed up)
•  » » » » » 7 years ago, # ^ |   0 Your argument is true but almost all softwares&&hardwares use the same way to represent negative. So using n&-n is OK i think. And more important n&-n works faster and because it's a very basic operation, say in Fenwick trees this trick proved to be helpful.
•  » » » 7 years ago, # ^ |   +28 In China, It's called the lowbit.
•  » » » 7 years ago, # ^ |   +3 One my friend names functions MAGIC, MAGICMAGIC, variables — temp, temptemp :)
•  » » » » 7 years ago, # ^ |   +2 Deducing from that style of coding — is his rating greater than 1500? I wouldn't expect that :P.
•  » » » » » 7 years ago, # ^ |   +25 How about this style of coding? ;)
•  » » » » » » 7 years ago, # ^ |   +3 I just wonder why he doesn't use a swap() function... Even  gives one easy-to-use template
•  » » 7 years ago, # ^ |   0 In many cases, the background is related with incredible and strange story. Thus, I always drop into puzzled condition.
 » 7 years ago, # |   +88 I hope it will help me :3
•  » » 7 years ago, # ^ |   +9 Awesome 0.0
•  » » 7 years ago, # ^ |   +3 God bless you.
•  » » 7 years ago, # ^ |   +48 Floppy disks o_O?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +4 Are those collector's items? Or diy things?
 » 7 years ago, # |   +45 Wait, just one pwny? You guys haven't figured out how to stack pwnies like how you stack cows yet?
•  » » 7 years ago, # ^ |   +10 Maybe they want to create more contests like that :P.
•  » » » 7 years ago, # ^ |   +14 they have already stacked up 4 contests. this is the fourth consecutive Div-1 round organized by a Chinese coder. :) let us see how long they can keep it going!
 » 7 years ago, # |   +5 I won't solve these tasks if Rarity doesn't appear.
 » 7 years ago, # |   +84 Python will help me.
•  » » 7 years ago, # ^ |   0 it looks like a horse — -?lol
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 It is so cute!(● ◡ ●)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +14 Python haven't helped me. Maybe, these problems are better to solve with FiM++. Or with better brains.
•  » » » 7 years ago, # ^ |   0 comft.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 The tambourine with ponies hasn't helped me too. Maybe, my place is in Div2.
 » 7 years ago, # |   +24 why not 21:00 start?
•  » » 7 years ago, # ^ |   +15 For the glory of satan of course !
 » 7 years ago, # |   +16 Oh yes!! There seems to be MLP FiM problem set!I'm looking forward to compete this round as Equestrian (see my profile).I'm waiting for The Wonderbolt characters' problem...
•  » » 7 years ago, # ^ |   0 What is "MLP FiM" short for?
•  » » » 7 years ago, # ^ |   +23 Seems to be My Little Pony: friendship is Magic.
•  » » » » 7 years ago, # ^ |   0 THX for explanation~!
 » 7 years ago, # |   +15 Most recent Div.1 CF Round authors are from China. Chinese people seem to have many ideas to write problems :)
•  » » 7 years ago, # ^ |   +3 That's because we can finally have a long long holiday AND MORE IMPORTANT some people think setting a CF round is a lot of fun XD
 » 7 years ago, # |   +10 I believe this round will be very wonderful. I can't wait to join the round. MinakoKojima, you are my idol..（^ω^）
•  » » 7 years ago, # ^ | ← Rev. 4 →   +12 ...
 » 7 years ago, # |   +8 orzzz! Have got ready to become green again...
•  » » 7 years ago, # ^ |   0 Why don't you try to look on the bright side?
 » 7 years ago, # |   0 It would be so great if start time of this Chinese-author round were to changed earlier to usual Chinese round time 21:00.
 » 7 years ago, # |   +18 Firstly — next Chinese contest, secondly — brony contest. Gotta get outta from here xD. I won't be surprised if I see 5x3000 pts :D.
•  » » 7 years ago, # ^ |   +5 It might be with dynamic scoring :D
•  » » 7 years ago, # ^ |   +12 And then, Div 2 gets 3x3000pts problems, which will frighten off the news to Codeforces. ~
•  » » » 7 years ago, # ^ |   0 OK, show them some mercy. Problem A may be 2500 pts (Div1) only.
 » 7 years ago, # |   +65 My daughter loves Twilight Sparkle. Every night I have to watch My Little Pony with her. I hope to get a good result in this round. I would like to show to my little daughter that my name has the same color of her Twilight Sparkle.
•  » » 7 years ago, # ^ |   +14 My best wish to you. Also give my regards to your lovely daughter~
 » 7 years ago, # |   +6 Good luck & AC for fun!
 » 7 years ago, # |   +16 Going to participate in the Div. 1 contest for the first time! Want to have a good experience! May the Almighty help me and all thanks goes to him!
•  » » 7 years ago, # ^ |   +4 Good luck!
•  » » » 7 years ago, # ^ |   +6 Thanks and hope will see you in Div 1 in the next contest after today. Though I might be in Div 2 that time. :)
•  » » » » 7 years ago, # ^ |   +5 thx 4 ur wish, let's fight 4 the goal of div 1 together! good luck again! ：）
•  » » » » 7 years ago, # ^ |   +1 WOWOWOWOWOWOWOWOW Its unbelievable that i m purple now!~ thx 4 ur hope ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :)
•  » » » » » 7 years ago, # ^ |   0 Feeling happy to see that! Congratulations! I should be in Div 2 from next contest, but I could not even get a chance to submit a solution! Had no idea to make a solution.However, best of luck for the next contests! :)
 » 7 years ago, # |   +9 It seem to appear problems as "the one that don't know ******(an algorithm name) will FST!"
•  » » 7 years ago, # ^ |   +6 Don't worry. The one, who don't know ***, won't pass the pretest.
•  » » » 7 years ago, # ^ |   0 Thx for the strict pretest~
 » 7 years ago, # |   -15 I think Chinese problem setters are supposed to adjust the start time to fit Chinese participants even if only in one round.
•  » » 7 years ago, # ^ |   -12 Still 0 vote? Well, poor Chinese deserve it.
•  » » 7 years ago, # ^ |   0 MinakoKojima and I often go to bed late (2:00 AM ?) and get up late (10:00 AM ?).
•  » » » 7 years ago, # ^ |   +1 For me, 10:00 AM is early)
•  » » » 7 years ago, # ^ |   0 ?
 » 7 years ago, # |   +7 It's typical Chinese Round! God bless us.
 » 7 years ago, # |   0 =.=,Why the contest is so late?
 » 7 years ago, # | ← Rev. 2 →   0 Why can't I register for Codeforces Round #259 (Div. 1)?
•  » » 7 years ago, # ^ |   0 Your contest rating must be above 1700 in order to register for Div. 1 contests.
•  » » 7 years ago, # ^ |   +4 Div 2 (especially Chinese Round Div 2) is more suitable for you.
 » 7 years ago, # | ← Rev. 4 →   0 Chinese round again... but why not 17:00 MSK T_TBtw I hope I can improve my rank to CM after this contest :D
•  » » 7 years ago, # ^ |   0 (Maybe they need to have supper, but problem setter don't need to sleep early.)
 » 7 years ago, # |   0 It seems that setter xlk and tester GuyUpLion are the same person.
•  » » 7 years ago, # ^ |   +28 Maybe I'm wrong, but their names are Ke Bi and they are from Shijiazhuang.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 They are definitely different people. Just one of them didn't tell us his true name.
•  » » » » 7 years ago, # ^ |   +17 Hmm, I guess one of them is Ke's girl friend.
•  » » » » » 7 years ago, # ^ |   +52 Thank you for not guessing one is Ke's boy friend.
•  » » 7 years ago, # ^ |   +5 If you use your true name, I can also register the same account as you.Why don't you think that is a common name? (Actually, it's a rare last name in China.)
•  » » » 7 years ago, # ^ |   0 Thank you for your clarification.
•  » » » » 7 years ago, # ^ |   +13 XD
 » 7 years ago, # | ← Rev. 2 →   +30 Thanks MinakoKojima , xlk & sevenkplus for arranging the round. We hope more DIV1 rounds from you :)
•  » » 7 years ago, # ^ |   +17 It's a typical Chinese round.
•  » » » 7 years ago, # ^ |   +5 What is the characteristics of a "typical Chinese round" ??
•  » » » » 7 years ago, # ^ |   +9 Hard problems (usually due to hard math) and weaker pretests than usual.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Hard math is better than very long code,do you think so?I also think that passing the Chinese pretests is skimble-skamble
•  » » » » » » 7 years ago, # ^ |   +7 When you can solve a problem, less code is a plus. When it's Chinese level hard, most people can't solve it, so it doesn't really matter how much code it needs :D
•  » » » 7 years ago, # ^ |   0 This time our pretests seem to be strong.
 » 7 years ago, # |   +84 Thank you for spoilers about 3rd season in announce =/
 » 7 years ago, # |   0 MLP
•  » » 7 years ago, # ^ |   +14 why so serious?
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 lol here
 » 7 years ago, # |   0 if there was not any xiaodao in the world, it would be "Codeforces Round #59" you are maker of half of my contest life:P
 » 7 years ago, # |   +3 Hope me can finish 2 problems in this round!
•  » » 7 years ago, # ^ |   0 As a bad resault,I only finish one problem
 » 7 years ago, # | ← Rev. 2 →   0 i just registered for this contest, and guess what i saw! i think these three accounts are all the same person, and if found out they should be banned! EDIT: it appears that the "real account" of this person has commented on OP about 10 minutes ago.
 » 7 years ago, # |   -38 Извеняюсь за вопрос а эта строчка егодня вам придется посетить Equestria и помочь очень дружелюбной принцессе, Twilight Sparkle, решить несколько задачек. такая и должна быть?
•  » » 7 years ago, # ^ |   0 А что не так? Сегодня вы посетите Equestria и поможете решить несколько задачек очень дружелюбной принцессе по имени Twilight Sparkle
 » 7 years ago, # |   0 the magantastar and the white star are going ot perform magic for the sake of gearld.
 » 7 years ago, # |   0 I don't take medicine today，so I feel that my name is green QAQ I hope I can solve one problem designed by Chinese
 » 7 years ago, # |   +18 I think that it's the first codeforces round which tested by gray coder))
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Grey? Where? #EDIT: Found it.
•  » » » 7 years ago, # ^ |   +4
•  » » 7 years ago, # ^ |   +1 Maybe that will be helpful for the setters to judge whether the Div2 problems set by them are of proper difficulty and not too difficult.
•  » » » 7 years ago, # ^ |   +10 In this case, i need blue tester for div1))
 » 7 years ago, # |   +11 tourist is the last registrant, thereby marking his name for all to see in the next 3ish minutes.
•  » » 7 years ago, # ^ |   +3 but he didn't participate :(
•  » » 7 years ago, # ^ |   0 but in today's MemSQL Start[c]UP 2.0 — Round 2, he did the exact opposite thing. :D
 » 7 years ago, # |   +10 I am going to sleep. Remaining problems is very hard.
•  » » 7 years ago, # ^ |   +14 what if one of ur Pretests passed submissions gets Hacked?
•  » » » 7 years ago, # ^ |   +13
•  » » » 7 years ago, # ^ |   +11 A trade-off between early sleeping and submission's safety.
•  » » » » 7 years ago, # ^ |   +14 looks like you made a good choice. all ur submissions got Accepted. also, it must have been a nice surprise when u woke up and saw that u became Grandmaster. congrats. :)
•  » » » » » 7 years ago, # ^ |   0 tks
 » 7 years ago, # |   +8 Awesome contest!! Thanks MinakoKojima , sevenkplus and xlk :D
 » 7 years ago, # |   +13 how to solve Div-1 B?
•  » » 7 years ago, # ^ | ← Rev. 3 →   +4 DP[i][mask] for each i = 1 .. n calculate min answer from 1 to i by using mask of prime numbers. if we choose for b[i] not prime number we can call b[i] = p[x1] * p[x2].... so it's mask of primes.
•  » » » 7 years ago, # ^ | ← Rev. 4 →   0 Oh what a nice solution. I was thinking of a completely different Solution 7320838 during contest.Too bad that i couldn't find my bug in contest :(
•  » » 7 years ago, # ^ |   +3 dp[i][mask] is the answer for the first i numbers if the numbers we used divide only the prime numbers from mask.
•  » » 7 years ago, # ^ |   +3 Here is a short explanation.You have to notice that it is a Bitmask DP problem. There are 16 primes less than 58. So keep a mask of 2^16, representing the primes used before. Then start a dp with states dp(pos,mask). In each position, you can place from 1-60. You can however only place a number if and only if it contains primes that have not been used before. Otherwise you can get gcd > 1.Just take the minimum configuration. Later print your path.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -14 But you can't choose 100 pairwise primes less than 58. Don't downvote if I'm wrong. We are all here to learn.Edit: NVM, forgot about 1s.
 » 7 years ago, # |   +12 Found few people in my room who used this for solution of Div1 A : pow ( m, n ). Instant hack with test case ( 100000, 100000 ) :p That really boosted my ranking :D
•  » » 7 years ago, # ^ |   +3 i tried to hack two participants who used pow function to find xy, but it returned Unsuccessful hacking attempt. :( any idea why?
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +17 JuanMata You can not hack your friends :PYou were just simply looking at power function. I was using power function differently. My code has expressions of the form pow(x/y, n). It would have failed if I would have done pow(x, n) / pow(y, n).
•  » » » 7 years ago, # ^ |   +1 We generally don't use pow cause of precision error. But since we are working with double here and the judge is going to ignore 10^-4 error anyways, I guess precision no longer becomes a issue anymore. I managed to hack cause they were trying to find pow(10^5,10^5), which is a large number and will given INF or NAN.
•  » » » 7 years ago, # ^ |   +9 It depends on how one uses it. I used pow as well. Except I had pow(x, y) only, where 0 <= x <= 1, which is why I don't get overflow, unlike if I was to use pow(m, n).
•  » » » » 7 years ago, # ^ |   0 yes, i got it. but what i mean is, doesn't pow(x,y) take to run?
•  » » » » » 7 years ago, # ^ |   0 I think it is doable in O(log y) time.
•  » » » » » » 7 years ago, # ^ |   0 i know we can implement finding in . but i was referring to the pow function provided by .
•  » » » » » 7 years ago, # ^ |   +14 pow(x,y) uses an expansion ...so a coprocessor (in short, a part of processor that conducts some funny operations, including computations on floating point numbers) needs to do exp (ex), ln () and mul (x·y) operations. Each of them can be done in a matter of dozens of CPU clock ticks.
•  » » » » » » 7 years ago, # ^ |   0 In VC++ pow(x,y) with integer y refers to binary exponentiation template inline _Ty _Pow_int(_Ty _X, int _Y) throw() {unsigned int _N; if (_Y >= 0) _N = (unsigned int)_Y; else _N = (unsigned int)(-_Y); for (_Ty _Z = _Ty(1); ; _X *= _X) {if ((_N & 1) != 0) _Z *= _X; if ((_N >>= 1) == 0) return (_Y < 0 ? _Ty(1) / _Z : _Z); }} 
•  » » » » » » » 7 years ago, # ^ |   +3 This code — an terrible nightmare for the hacker... 0_0
•  » » » 7 years ago, # ^ |   0 why do you expect pow function for fail ?
•  » » » » 7 years ago, # ^ |   0 when we take (10^5)^(10^5) in denominator i thought it will work in python. so tried to write in python, but got only runtime errors (i had not used python before)
•  » » » » » 7 years ago, # ^ |   0 Yeah... python can handle pretty large numbers, but it's still slow working with them. That's why you get TLE's if you do the unsimplified formula.
•  » » 7 years ago, # ^ |   0 How to solve Div 1-A?
•  » » » 7 years ago, # ^ |   +6 The probability that no value is bigger that x is equal to . It means that probability that max value is equal to x is equal to (probability of not getting >x) — (probability of not getting >x-1). Then you can compute the expected value.
•  » » » » 7 years ago, # ^ |   0 I got the formula...But I could not translate it into code..as the constraints were too high.
•  » » » » » 7 years ago, # ^ |   +3 Programming languages usually have a routine to compute the powers of floating-point numbers very fast.E.g. in C++ you can compute as follows: result = pow((double)x/m, n); You can assume it works in constant time.
•  » » » » » 7 years ago, # ^ |   0 C++ has a useful function: pow(base,exponent), which is fast enough.
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   +21 We can simplify the formula as:
•  » » » » » 7 years ago, # ^ |   0 could you explain this simplification?
•  » » » » » » 7 years ago, # ^ |   0 There is a chance that maximum will be  ≤ k. Consider sequence 1, 2, ..., m: probability for each k to be the max is minus probability that every less value would be the maximum, so . Then multiply by value to get the expected value and you should get something along these lines.
•  » » » » » » » 7 years ago, # ^ |   0 I just realized telescoping series in this sum. Anyway, thanks
•  » » » » » » 7 years ago, # ^ | ← Rev. 7 →   +8 Sorry, duplicated and deleted. See below.
•  » » » » » » 7 years ago, # ^ |   +13 It can be derived like this:also:
•  » » 7 years ago, # ^ |   0 are you serious? http://codeforces.ru/contest/453/submission/7310927
•  » » » 7 years ago, # ^ |   0 Well, this guys did this: p = (i) / (double)m; p = pow(p, n) Since, p <= 1, pow ( p, n ) will not overflow. pow ( m, n ) however will overflow.
•  » » » » 7 years ago, # ^ |   0 Ac-93 probably meant that you included a (quite long) segment tree implementation in an easy math task :D
•  » » » » » 7 years ago, # ^ |   +3 firstly, the code is submitted by Ac-93 himself. secondly, he is not invoking those functions anywhere in main. i don't see anything wrong with having segment tree implementation as part of one's template.
 » 7 years ago, # |   +29 Thank you for the contest and for the great tasks!If I would give feedback on the tasks, I would say that I disliked that the graph is not guaranteed to be connected in Div1 C/Div2 E. This, in my opinion, was a restriction with a single purpose in mind — let's invent some edge cases, which is the purpose I heavily dislike. If the graph is connected, there are no edge cases at all (and it is always possible to construct a path). Now, because this is not guaranteed, I had to add a bunch of "edge case" code — find out which vertex to start DFS from (rather than starting from any with single component), check if there is only 1 connected component etc. With a single component I felt that the task actually had short and clean solution in code. Was it really necessary to do this?Furthermore, because the authors didn't include any test with answer -1 in pretests, I had wasted an hour worth of points before someone hacked me and I found the lack of outputing -1 in my code. Sure, this is completely my fault. But one of the point of pretests is to check the format of the output (like if there are mutiple possible string outputs — have them all in pretests), and in this case -1 was never tested. Is it fair to penalize people who accidently mistyped this constant?
•  » » 7 years ago, # ^ |   +14 Sorry for that, acknowledged.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Furthermore, because the authors didn't include any test with answer -1 in pretests, Wait, what?I don't mind the possible disconnectedness, especially because the "if there's no answer" in the statement worked as a good hint, but the pretests definitely should've taken care of that. I also didn't really try hacking C because I thought the only special case was included in the pretests... I wonder how many people were in a similar situation.Well, as I said above: weaker pretests than usual. Although in a different way than I meant :D
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +8 Yeah, I didn't paid too much attention to the hint "if there's no answer", because I see authors putting this in even if there is always solution, to hide that fact, because it might make the task easier.But to highlight my point about disconnectedness, here is the difference between my original code and the accepted version. Sure, it certainly doesn't make the task bad — I liked it very much, but this code was in my opinion unnecessary and brought nothing to the solution of the task except edge cases. Before the whole code was: read the graph, run DFS, output the answer. Now we have extra steps: find the vertex to start from, check that there is no 1 in array after DFS.And yeah, there were different approaches to this problem, in which having unconnected graph only brought 1 line modification.
•  » » » » 7 years ago, # ^ |   0 My modifications were much simpler, it's mostly just rewriting "0" to "i" in a big chunk of code.
 » 7 years ago, # |   0 DIV1 A and DIV1B?
•  » » 7 years ago, # ^ | ← Rev. 12 →   0 Div1A -> Calculate seperately the number of times:1 would be maximum , 2 max ........ m would be maximum Number of times 1 max = 1 Number of times 2 maximum = 2n — 1 Number of times i maximum = in — ((i - 1)n)So Expected value = Mix m^n with the numerator and you can get the answerI made the mistake of not mixing m^n with the numerator
•  » » » 7 years ago, # ^ |   0 I think you missed an "i" in the expected value expression.
•  » » » » 7 years ago, # ^ |   0 Thanks for correcting me .Please can anyone tell me how do I post mathematical symbols here ?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +4 \sum_{i=1}^m i * \frac{i^n — (i-1)^n}{m^n}
•  » » » » » » 7 years ago, # ^ |   0 Thanks
•  » » » » » » 7 years ago, # ^ |   0 This was my mistake! I also did summation from 1 to n. Output for given cases did not match. I did not think of debug. I thought approach was wrong. Then I saw the solutions...Saw the same error again (here).So, change the summation from 1 to m
•  » » » » » » » 7 years ago, # ^ |   0 No that's not why I coded it wrong . I took summation from 1 to m but did not merge the denominator: m^n with the numerator . Thus I thought that it would overflow and did not do anything about the problem .
 » 7 years ago, # | ← Rev. 2 →   0 a
•  » » 7 years ago, # ^ |   +1 gcd(6,8)=2
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 a
 » 7 years ago, # | ← Rev. 2 →   +32 Task C is good, but I think it would be better to set that the input graph is connected. (The other part is not very interesting).Task D is also good, but I think the TL is a bit tie. I managed to pass the pretest by code optimization.Task E seems to be the harder version (force to do it online) of this task: http://hihocoder.com/contest/challenge1/problem/2I think it is not a good idea to use it here since it has already used in previous contests. For example, since I know I can't even code solution for the eaiser task, I just skip this task and focus on D, it gives me some advantages.Overall it is a good contest, thank you all writers and testers!
•  » » 7 years ago, # ^ |   +13 C is by me. It would be a bit unnatural to constrain the graph to be connected. Also, Egor gets WA because of this. :D
•  » » » 7 years ago, # ^ |   +58 And this is why I disliked the absence of this restriction in the first place in the comment above. The whole idea in the solution is run on a single connected component, then you added unnatural expansion (unnatural to the solution rather than unnatural to the statement, and I probably don't even agree that this constraint in the statement is unnatural) to allow graphs to be not connected, so that there are now some edge cases/extra work to do. And as you wrote Egor failed because of this.Seems to me that you're pretty happy with that. I believe authors should be happy when people fail their task with a wrong solution, rather than solving it correctly and failing on the edge case. But maybe that's just me.Don't get me wrong, I still liked the task and the contest. As cgy4ever I just feel it could have been even better with that restriction.
•  » » » » 7 years ago, # ^ |   +11 Sometimes we need to left something to hack, and sometimes we cover the tricky part by constraints or give such case in examples.For me, I only left it to hack if the task is very easy or a bit classic. If I'm the writer of this task, I will cover that trick cases, because this task itself is challenging, if someone get the solution but fail by that stupid trick then it is huge lost (Getting the solution is a challenging thing, so he should get points by this).
•  » » » 7 years ago, # ^ |   0 actually, Egor's solution 7313057 failed on a much easier case than where answer was -1. :D (but you are right about graph not being connected)
•  » » » » 7 years ago, # ^ |   0 It's all about connectedness, so it doesn't matter.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +29 Every problem setters should maximize following fraction: Interesting ----------- Frustrating To make problems better.
•  » » » 7 years ago, # ^ |   +27 Well, of course I should be more attentive to details, no doubt about this. But I always thought that it is just a good taste for problemsetter to include sample with answer "Impossible" or such if there is such case. I know that at the very least TopCoder requires a thing
•  » » 7 years ago, # ^ | ← Rev. 2 →   +17 I know it is bad, that's why I put it in the middle night~ Princess Luna, can you hear me?
 » 7 years ago, # |   +4 Slowest system testing I've ever seen....only 4 submission are being judged at the same time!
•  » » 7 years ago, # ^ |   +18 I am amazed that you have done 62 contests but haven't seen slower system testing. The system testing is slow because there are too many test cases for problem A. We apologize for this.
•  » » » 7 years ago, # ^ |   0 I suppose it's some technical problem...because in every contest I see almost 10 submissions that are being judged simultaneously
•  » » » 7 years ago, # ^ |   0 there cant be more that 50 cases!
 » 7 years ago, # |   +3 Oh LOL, DIV2C/DIV1A was damn simple, and I messed it up %)
 » 7 years ago, # |   +45 Good problems — 9/10Having disconnected graph in C was not something to complain about-1 because two very hard problems for a single match is too much
•  » » 7 years ago, # ^ |   0 I was right because I gave up and slept early.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 Honestly, I would disagree with the statement "very hard problems", at least with E. It was pretty complicated, I must say, but if you carefully broke down the problem into smaller ones, it became quite straightforward (i.e. no superclever observations and tricks were needed), although implementationally demanding. Of course, it is only my opinion :) And I didn't manage to find a (obvious) bug before the end of the contest, but still it was not "very hard".
 » 7 years ago, # |   0 I could find a way to find the expected number for div1 A but I couldn't implement it because I don't know how to avoid overflow my idea like this:let prob[i] be the probability that the max number is i (for all i from 1 to M) then I compute the expected number.let dp[i] be number of sequences with length N and every element between 1 and i and max number is i.dp[i] = i^N-(sum(dp[j]) for every 1<=j
•  » » 7 years ago, # ^ |   0 My first solution was hacked because of the overflow problem, but it's fairly easy to derive the solution that doesn't overflow if you had already come up with the one that does :)7318172
 » 7 years ago, # | ← Rev. 2 →   0 my submission for problem E (Div 2) is giving WA on pretest 4.But when after the contest i tried the test case it's giving correct answer on my system as well as ideone. This is the ideone link :- http://ideone.com/EWR4KA my codeforces submission :- http://codeforces.com/contest/454/submission/7320400 can somebody tell me the reason behind it ??
•  » » 7 years ago, # ^ |   0 Can't see any differencies, there's the same (incorrect) answer at ideone, isn't there?18 3 2 1 2 4 5 7 5 10 5 4 8 4 9 4 3 6 3
•  » » 7 years ago, # ^ |   0 there is no edge from 4 to 3
•  » » 7 years ago, # ^ |   0 ohh i am extremely sorry i didn't know what i was thinking. I misinterpreted output for the answer in the submissions. Sorry for the trouble and thanks.
 » 7 years ago, # |   0 Quite unfortunate that my Div1-B solution passed all pretests :'(
 » 7 years ago, # |   +1 i saw a few AC submissions in my room for Div-1 A, which printed . can anyone please provide a proof for this?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +16 the answer is .
•  » » » 7 years ago, # ^ |   0 Am I too dumb or is it really not that obvious how the left hand side can be rewritten as the right hand side?
•  » » » » 7 years ago, # ^ |   0 don't worry, u were not the only one. :D here is the explanation. :)
•  » » » » » 7 years ago, # ^ |   0 Thank you! :)
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 JuanMata i don't think the limit of summation will be till m, it will be till m-1 and also instead of first term m+1 shouldn't m be there?
•  » » » 7 years ago, # ^ |   0
•  » » 7 years ago, # ^ |   0 Have a look at this comment. http://codeforces.com/blog/entry/13247#comment-180671. If you simplify it, it will result in your formula.
•  » » 7 years ago, # ^ |   +17 The sum telescopes to
•  » » » 7 years ago, # ^ |   0 excellent explanation, thanks very much :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Are you sure it is m + 1 in your formula?. There is only one way of getting the maximal element (in n consecutive trials) equal to one, then there are 2n - 1 ways of getting the maximal element equal two, 3n - 2n ways of getting the maximal element equal to 3, and so on. The total number of possibilities is, of course, mn. Then the expectation is calculated in the following way:
•  » » » 7 years ago, # ^ |   0 In formula by JuanMata the summation is till m. Notice that the last term is (m/m =1) so it will cancel the previous 1 . This will leave the formula given by ericxu0.PS: There is a small typo in you formula , the summation should be till m-1 not n.
 » 7 years ago, # |   +16 Div1-B, Nice problem!
 » 7 years ago, # |   0 For Div.2 problem B: http://codeforces.com/contest/454/problem/B My Submission: http://codeforces.com/contest/454/submission/7316030 It fails on pretest 6. If I'm right, here is an equivalent test: 5 4 1 2 3 5 How this array can be sorted using the given move? If my test is not equivalent, please update me with a correct one that I can trace. Thanks.
•  » » 7 years ago, # ^ |   0 I dont think that it is equivalent. Here is a test case which your code fails. 3 1 2 1.
 » 7 years ago, # |   0 How to solve Div2-C ?
•  » » 7 years ago, # ^ |   0 Look at exmath89's post for the expression to evaluate. To evaluate this expression, for everything in the summation, calculate it with exponentiation by squaring. Then, sum these up and subtract from m to get the answer.
•  » » » 7 years ago, # ^ |   0 Thank you
 » 7 years ago, # |   0 I try to hack 7313853 during contest with test case : 100000 100000 1 2 3 4 .... 99999 It checks all the states , with == operation for deque (99999 times for a 100000 size deque) ... My hacking of TLE was unsuccessful...Now it has been TLE on case 41 , With a equal N , but using repetitive number 1...Isn't it Weird ? I mean are we hacking Deep until STL Codes ? :D
•  » » 7 years ago, # ^ |   +17 The == operator only has to look until it finds a single mismatch -- so for 99999 of those equality comparisons, it exited after looking at just the first element of both deques. The system test case was TLE because it had to look through all of those 1s before finding a mismatch :)
•  » » » 7 years ago, # ^ |   0 Yes but i was not thinking of The STL implement, i thought its Linear so it should fail.I mean my testcase should do some hacks to make STL deque Linear in case of hacking this submission. It was a bit unusual for me.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +6 STL is evil in some way... Believe me, after IPSC 2014 there will be "HashSetKiller" programs, like already exist JavaQuickSortKiller! p.s. one problem in this year's IPSC is to hack C++ and Java hashset program to let them get TLE in not very large test case, and there even exists a input that could hack both programs! (See HARD version of that problem)
•  » » » 7 years ago, # ^ |   0 That's Cool!!I will check more in the STL implements.
 » 7 years ago, # |   0 Ratings are updated!
 » 7 years ago, # |   -8 I was 45 minutes late, but still +71 rating.Thanks for great problems.
 » 7 years ago, # |   +8 Forgive me if I'm a bit retarded in that subject, but were 50 points always deducted for submissions that fail on a sample test, but not on a 1st test? I thought that rule of not deducting 50 points for submission failing 1st sample test applies to all samples.
•  » » 7 years ago, # ^ |   +5 It applies only for the first sample, I can't get the point of this though.
•  » » » 7 years ago, # ^ |   +3 I can't get the point of this though it is mainly to check that output format exactly matches with what the checker expects. this is especially useful in problems like this one.
•  » » » 7 years ago, # ^ |   0 This way you are not penalized in case of your submission failing due to wrong output format, or if you simply chose wrong file to upload/ wrong problem to submit against.It can be said that you pay for your own carelessness, but anyway prevention of that sort of mistakes is pretty sweet. I guess you've just never submitted wrong file on a contest ;)
•  » » » » 7 years ago, # ^ |   0 Well I believe that it won't hurt if all the samples are included :D
•  » » » » » 7 years ago, # ^ |   +3 Completely agree with you. In this contest, I got two WA on pretest 2 in div1C, which was one of the samples, directly costing me 100 points.Though I didn't pass the system test anyway :(
•  » » » » » » 7 years ago, # ^ |   +3 The point is that you should test the samples. The reason why first sample isn't penalized is I believe to avoid penalties for technical stuff (like how to deal correctly with packages in Java, for example) rather than avoid penalizing for WA1.
 » 7 years ago, # |   -8 Someone please tell how to solve div1C?
 » 7 years ago, # |   -37 May I ask you to do your next contest in "Adventure Time" setting? It's very nice too :).
•  » » 7 years ago, # ^ |   +30 may i ask you not to post such large photos in comments? they are not so nice. :(
•  » » » 7 years ago, # ^ |   +3 I didn't knew that CF posts pictures in their full size. My first picture-upload :(
 » 7 years ago, # |   +43 Following this success, I will make my next round with Pokemons!
 » 7 years ago, # |   +3
 » 7 years ago, # |   0 Thanks for the awesome problemset. Unfortunately I missed this round :-(.
 » 7 years ago, # |   +2 OFF TOPIC THOUGH: I just came to remember this author MinakoKojima for some special reason. some days ago I was trying to learn link cut tree and found her blog:- http://www.shuizilong.com/house/archives/spoj-9577-dynamic-tree-connectivity/Thank you MinakoKojima for your contribution to the community.
 » 7 years ago, # |   +4 +122 rating. I love ponies, also this is surely great contest!
 » 7 years ago, # |   -39 The new Editorial is available here.
 » 7 years ago, # |   0 Can you give me solution for this round? Thank u.
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # | ← Rev. 2 →   +6 Div-2 A solution using regexp (language: Perl): longer, shorter.
 » 7 years ago, # |   +14 Wrong picture guys. When Twilight is solving problems she looks different: