### havaliza's blog

By havaliza, 8 years ago,

Hi all! :{

We're glad to invite you to participate in Codeforces Round #173 prepared by A.K.Goharshady, LGM and me (havaliza). I want to thank Gerald, MikeMirzayanov and Delinur who helped us to prepare the round on this platform. And thanks to Dani1373, hhoomn, MrM, MMJ and xorfire who tested the problems and helped us a lot.

Today is LGM's birthday and yesterday was gpac's birthday. Happy birthday to you guys! ^.^

Hope you enjoy today's round and have lots of fun. :)

Update. The editorial is out!

• +279

 » 8 years ago, # |   +70 Happy Birthday!!!
•  » » 8 years ago, # ^ |   +2 ALL say HappyBirthday No one ask for score distribution :D
 » 8 years ago, # |   +22 Hi. And tomorrow is my birthday. Hope to have a good contest to enjoy my birthday much more. :DAnd Happy Birthday you guys. Glad to know it. Wish you bests in whole LIFE.HF & GL!
 » 8 years ago, # |   -21 I want to participate,but I'm too tired:(
 » 8 years ago, # |   +34 Happy birthday to you guys(lgm,gpac,S.HASHEMI)!!! ^.^ and also Congratulations to havaliza,keivan,fab,dani1373 ,because of being selected for IOI team of IRAN for next year!!! hope you win 4 gold medals for IRAN!!!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +6 Thanks a lot. :D Wish you bests.
 » 8 years ago, # |   +4 Your prev contest was great! (at least for me!) I hope it will be like the prev! How is score distribution?
 » 8 years ago, # |   +22 I was surprised a lot! thank you havaliza :)
•  » » 8 years ago, # ^ |   +2 Happy birthday gpac. Wish you get rank 1 today. :D
•  » » » 8 years ago, # ^ |   0 Happy Birthday to you too! I hope you have the best day of your life and have a professional contest. Let's go to infinity and beyond it!!!!
•  » » » » 8 years ago, # ^ |   +2 Taxiiiiiii.....Infinity please.
•  » » » 8 years ago, # ^ |   -6 Happy birthday to you guys:)I hope you also will get present from codeforces like me)I had birhtday in 25.02 and codeforces gave me +61:) http://codeforces.ru/bestRatingChanges/213901:)
 » 8 years ago, # |   0 happy birthday boys <:-P And special thanks for preparing the contest :-)
 » 8 years ago, # | ← Rev. 2 →   0 173 cool number , because it is number my school ))
 » 8 years ago, # |   +3 A bunch of Problemsetters from IRAN :D
 » 8 years ago, # |   +6 Happy Birthday
 » 8 years ago, # |   -10 Happy Birthday guys :) god bless you !!
 » 8 years ago, # |   +11 wow! More than 3000 registered users :D .
•  » » 8 years ago, # ^ |   -11 due to iranian setter :D
 » 8 years ago, # |   +7 please tell us about score distribution ?
•  » » 8 years ago, # ^ |   +4 since it's no announcements about it, i think it's standard
 » 8 years ago, # | ← Rev. 9 →   -11 ...d
 » 8 years ago, # |   0 Problem B: jury solution for test 3 1000 0 998 2 503 497is "222". W T F???
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 0+2+497=499 499<=500
•  » » 8 years ago, # ^ |   0 Oh, i found my mistake :(
 » 8 years ago, # |   0 Who solved D and how?
•  » » 8 years ago, # ^ |   -10 For n=1 the situation is clear. For n=2 (two non-zero integers) if a[0]=a[1], first player wins, elsewhere he loses. For n=3 (three non-zero numbers) there are (300^3)/6 possible situations (excluding permutations of those), and for each of them we can calculate if the first player wins or loses in O(1).
•  » » » 8 years ago, # ^ |   0 in testcase 2 1 5 your solution is wrong. because first player can make situation 1 2 which is bad for the second player and first will win
•  » » » » 8 years ago, # ^ |   0 update a[0]=1 a[1]=5 2 is for n
•  » » » 8 years ago, # ^ |   +1 2 2 3
•  » » » 8 years ago, # ^ |   0 I think you meant vice versa for case n=2. didn't you?
•  » » » » 8 years ago, # ^ |   0 Fine, we can iterate through all (300^2)/2 situations as well.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 Sorry. I was Wrong :|
•  » » » 8 years ago, # ^ |   0 if n=2 you are logically wrongbecause if a[0]!=a[1] you said that second is winner but the first player can make a move that makes also a[0]!=a[1] then and become the second then he is winner , so how become both first and second winners?e.glet n=2 , a[0]=1 , a[1]=3the first is the winner and the winning move is subtract 1 from a[1]
•  » » » » 8 years ago, # ^ |   +5 I know, mate. Just didn't think about it well.
•  » » 8 years ago, # ^ |   +11 Use dp[i][j][k] to stand for whether (i,j,k) is a state in which the first person will win. It can be easily proved that the number of (i,j,k) such that dp[i][j][k] is false is O(n^2). We can use dp[i][j][k]=false to update dp[i+t][j+t][k+t] dp[i+t][j][k] dp[i][j+t][k] dp[i][j][k+t]. And it takes O(n). So we can get an O(n^3) solution by this way.
•  » » » 8 years ago, # ^ |   0 May you please give further explanation about the O(N^2) bound on losing situations (i,j,k) ?
•  » » » » 8 years ago, # ^ |   +11 Because if (i,k,j) is false than (i',j,k) is true when i'>i, which means the number of tuples (i,j,k) that is false is O(1) for each pair (j,k).As there is O(n^2) such pair (j,k), it is obvious that the number of tuples (i,j,k) that is false is O(n^2).
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 My submission 3308449
 » 8 years ago, # |   +10 How to solve E?
•  » » 8 years ago, # ^ |   +30 3306281 0_o
•  » » » 8 years ago, # ^ |   0 Well, I don't think, this solution will survive system tests :D
•  » » » » 8 years ago, # ^ |   -8 Does it work for the numbers (in binary):1000 , 10 , 10 , 100, 1, 1100You say it should find 1111 but I don't see how it can.
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +1 give 0 to right and give 6 to left it will be 0 ^ 1111 ? Edit:I got it.
•  » » » 8 years ago, # ^ |   +4 Isn't <1,7,2,1> a counterexample for this solution?!!!
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +2 No, since it's permitted take <1,7> and <1> for 7 points.<1,1,2,2,4,4,8,8,16,16> breaks it, though.
•  » » » » » 8 years ago, # ^ |   0 oh, your right. thanks.
•  » » 8 years ago, # ^ |   0 It can be solved by greedy algorithm using trie.
•  » » » 8 years ago, # ^ | ← Rev. 4 →   0 but dude what isn't it possible to make 63 for this: 6 13 21 3 61 1 2 but judge says 62.I mean we can give 0 to right and 6 to the left .Than the pleasure will be 111111^0=63 ?Edit: I got it.
 » 8 years ago, # |   0 My C is soo going to fail.
 » 8 years ago, # | ← Rev. 2 →   0 I notice a code will get TLE so I make generation to this testcase string a=""; for (int i = 0; i < 1000000; ++i){ a+='1'; } cout<
•  » » 8 years ago, # ^ |   0 Maybe, you should make "endl" after second "cout"?
•  » » » 8 years ago, # ^ |   0 but error say Input can't contain two or more consecutive spaces
•  » » 8 years ago, # ^ |   0 Maybe you mistook "code generator" and "input" just like me last time.
 » 8 years ago, # |   0 It is really hard to solve problems in Java, and Petr is really great, because he uses Java and he is the fastest coder.
•  » » 8 years ago, # ^ |   +1 Come on mate , This should have been well thought before taking petr as prefix in your handle. Now you are expected to code in Java :P
 » 8 years ago, # | ← Rev. 2 →   +5 Problem C was very interesting....a lot of people's solutions ( and also my solution!! ) has been hacked
•  » » 8 years ago, # ^ |   +4 I hacked 2 user with this testcase: 111 000 
•  » » » 8 years ago, # ^ |   +5 I also hacked with: 1 0 :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +12 I hacked about 9 users with :0 0Lol.
•  » » » 8 years ago, # ^ |   +5 I found a hackable solution just before the contest was over. I guess C is the most trick one in this contest.
•  » » 8 years ago, # ^ |   +1 Very simple problem, but it has some pitfalls.
•  » » 8 years ago, # ^ |   0 Why do you have this weird if statement in your code? if ( yek1 >= ceil((float)yek2/(float)2) ){...} After some analysis you will know that one can construct every string(except a '0'-string that consists only of '0's), iff we have at least one '1' in our string.
•  » » » 8 years ago, # ^ |   0 Yes, I think i was very lucky that my solution has been hacked, because my algorithm has a lot of bugs and finally I found the answer!!
•  » » » » 8 years ago, # ^ |   0 I hoped my soloution had been hacked too, then I could submit the correct one... Grammere jomlam dorost bud??
 » 8 years ago, # |   +4 I'm waiting system testing, for lunch!!! Please, hurry up... :D
 » 8 years ago, # | ← Rev. 2 →   0 Deleted.
 » 8 years ago, # |   0 Testcase for problem C is to much (about 100 test). Systest will run very low.
•  » » 8 years ago, # ^ |   0 there are more than 100 test cases for D problem too
•  » » 8 years ago, # ^ |   0 Where is sence to make so many tests for so easy task?..
•  » » » 8 years ago, # ^ |   +17 Here: 3303326
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +2 It's bad example. If you know right solution — ( put "YES" only if '1' exists in both strings or doesnt exist in both ) you can make about 10-20 tests to check all the solutions. But not 100.
•  » » » » 8 years ago, # ^ |   +11 c1*r1 == 0 (mod 2^32), funny mistake!
 » 8 years ago, # |   +7 Great Contest! I realy Liked problems D and E even though i didn't solve them
 » 8 years ago, # |   -40 Today during the contest I got two messages from MIT_1996 who was in my room, asking for help in problem B with algorithm. Where should I report ??
•  » » 8 years ago, # ^ |   +13 i think you should forgive him and not report this.
•  » » 8 years ago, # ^ |   +11 You could have asked where to report a dishonesty without saying the name of the competitor in public chat. Is not a good practice to a shame people for such reasons in front of all.
 » 8 years ago, # |   +7 thx! very nice contest:)
 » 8 years ago, # |   -10 The problems are easy. Good contest
 » 8 years ago, # |   +1 That was a nice contest, thanks to havaliza and happy birthday to LGM and gpac...
 » 8 years ago, # |   0 I cant't exactly understand the meaning of problem E ! We are asked to find the maximum of what ? (BitHaval and BitAryo) what does 'and' mean here?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 "The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness."
•  » » » 8 years ago, # ^ |   0 tnxwould u explain about test case 3 ?2 1000 1000
•  » » » » 8 years ago, # ^ |   +6 The sausages can be empty, so give 1000 to BitHaval and nothing to BitAryo :D
•  » » » » » 8 years ago, # ^ |   0 tnx, sorry, one more please :D test 8: 4 1 2 4 12 the answer is 15, why?
•  » » » » » » 8 years ago, # ^ |   0 for example, all to BitHaval: 4 xor 1 xor 2 xor 4 xor 12 = 15
•  » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 I mean test 8, that is : n = 4 and the numbers are : 1 2 4 12
•  » » » » » » » » 8 years ago, # ^ |   0 Oh, sorry. In this case, give 1,2 to BitHaval and 12 to BitAryo.
•  » » » 8 years ago, # ^ |   0 Oh! I got it now. :|
 » 8 years ago, # |   +4 very good contest but I think test 26 from problem D should be in pretest , so many person got WA due to this test , thanks.
 » 8 years ago, # |   +9 that was a nice contest thanks to havaliza but why Bitlandians are weird they are amazing
 » 8 years ago, # |   +4 Thats funny. I solved my solution using Delphi compiler: http://codeforces.ru/contest/282/submission/3302945 The same code, using FPC: http://codeforces.ru/contest/282/submission/3311282
•  » » 8 years ago, # ^ |   +1 Thats not funny I think... :D exactly like the diffrence between visual studio compiler and GNU...
•  » » » 8 years ago, # ^ |   0 Something i have experienced while using CodeBlock for C++ and G++ compiler !!
 » 8 years ago, # |   +4 When will the plus and minuses appear on the graph???
 » 8 years ago, # |   +1 painting eggs is a very ancient and attractive custom in Iran and the children still do this
 » 8 years ago, # |   +3 Very nice problems. Thanks to authors!
 » 8 years ago, # |   +6 Happy birthday to all of you guys (gpac, LGM and S.HASHEMI)!!! and I hope that we get 4 Gold medals from havaliza, dani1373, fab and keivan!The contest was very cool! Thank you for problems.
 » 8 years ago, # |   +1 This is now 4 hours after contest but ratings had not changed yet... when does it want to change?? And I am right here in the site since the contest started... :D
 » 8 years ago, # |   0 Has anyone solved problem 'E' without a trie or with a easier solution to implement ?
•  » » 8 years ago, # ^ |   0 I have no idea what this does, but it looks suspicious: http://www.codeforces.com/contest/282/submission/3303893
•  » » » 8 years ago, # ^ |   0 It seems to be the same ideia using trie. However, the code is a lot more clear and simply.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +5 Well, what I did was following: I replaced the given array by an array, where . BTW, The given array was a[1..n], I just added the 0th element to indicate we didn't give the first person anything to eat. Now imagine we gave the first person a piece [0..l] (it is equivalent to [1..l]) and the second — [r..n]. Then the tasty value of this is . We can replace the value r - 1 to m. Now we want to maximize . Notice two things: 1) l and m is the only variables since n is fixed, 2) 0 ≤ l ≤ m ≤ n. Then just sort the array s and then for any 0 ≤ m ≤ n use binary search for digits in the binary representation of to find l. Total complexity is .My submission: 3304910
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +3 Thank you a lot ! For me this solution is much easier than author's :)
 » 8 years ago, # |   0 i think this my solution still wrong, but get accepted http://codeforces.com/contest/282/submission/3309655because 'is' never change, and did this solution true after i add is++? http://codeforces.com/contest/282/submission/3312416
 » 8 years ago, # |   0 Please don't delay publishing the editorial for this contest. thks
 » 8 years ago, # | ← Rev. 2 →   +8 Problem D was a nice DP problem. I calculated the losing scenarios offline and found a formula for it. Then just applied the formula and solve the problem in O(1). It was very fun. Problem E was a very nice problem too. I scratched my head for a little while to make it run in time, until I thought of building a trie, and I really like building tries :)
 » 8 years ago, # |   +1 Thanks for really interesting problems! But what mean's verdict Skipped? My solve of problem C — XOR and OR received Accepted in final tests. I see Skipped and only two solved problems today.
•  » » 8 years ago, # ^ |   0 hmm this is weird thing..happened to one once. let see if someone can explain it
 » 8 years ago, # |   0 I was actually shocked that problem B had a greedy solution to it. I was trying so hard to partition the numbers :P. But after end of competition when i saw some solutions which had got accepted i was surprised and confused. But then i came up with an inductive proof for the greedy method. Had fun. Will have to improve myself.
•  » » 8 years ago, # ^ |   +3 I thought about knapsack problem,but when i saw many accepted code I wrote greedy solution.Now i know why this solution is correct(with an inductive proof,as you say).
 » 8 years ago, # |   +10 I love this contest.
•  » » 8 years ago, # ^ |   0 I also ))