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, mruxim, 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!

Happy Birthday!!!

ALL say HappyBirthday No one ask for score distribution :D

Hi. And tomorrow is my birthday. Hope to have a good contest to enjoy my birthday much more. :D

And Happy Birthday you guys. Glad to know it. Wish you bests in whole

LIFE.HF & GL!

I want to participate,but I'm too tired:(

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!!!

Thanks a lot. :D Wish you bests.

Your prev contest was great! (at least for me!) I hope it will be like the prev! How is score distribution?

I was surprised a lot! thank you havaliza :)

Happy birthday gpac. Wish you get rank 1 today. :D

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!!!!

Taxiiiiiii.....

Infinity please.

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:)

happy birthday boys <:-P And special thanks for preparing the contest :-)

A bunch of Problemsetters from IRAN :D

Happy Birthday

Happy Birthday guys :) god bless you !!

wow! More than 3000 registered users :D .

due to iranian setter :D

please tell us about score distribution ?

since it's no announcements about it, i think it's standard

...d

Problem B: jury solution for test 3 1000 0 998 2 503 497

is "222". W T F???

0+2+497=499

499<=500

Oh, i found my mistake :(

Who solved D and how?

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).

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

update a[0]=1 a[1]=5 2 is for n

2 2 3

I think you meant vice versa for case n=2. didn't you?

Fine, we can iterate through all (300^2)/2 situations as well.

Sorry. I was Wrong :|

if n=2 you are logically wrong

because 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.g

let n=2 , a[0]=1 , a[1]=3

the first is the winner and the winning move is subtract 1 from a[1]

I know, mate. Just didn't think about it well.

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.

May you please give further explanation about the O(N^2) bound on losing situations (i,j,k) ?

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).

My submission 3308449

How to solve E?

3306281 0_o

Well, I don't think, this solution will survive system tests :D

Does it work for the numbers (in binary):

1000 , 10 , 10 , 100, 1, 1100

You say it should find 1111 but I don't see how it can.

give 0 to right and give 6 to left it will be 0 ^ 1111 ? Edit:I got it.

Isn't <1,7,2,1> a counterexample for this solution?!!!

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.

oh, your right. thanks.

It can be solved by greedy algorithm using trie.

but dude what isn't it possible to make 63 for this:

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.

I notice a code will get TLE so I make generation to this testcase

so what's wrong he till me Invalid Input

FAIL Input can't contain two or more consecutive spaces, but line 31 (1-based) contains [validator wfval.exe returns exit code 3]

Maybe, you should make "endl" after second "cout"?

but error say Input can't contain two or more consecutive spaces

Maybe you mistook "code generator" and "input" just like me last time.

It is really hard to solve problems in Java, and Petr is really great, because he uses Java and he is the fastest coder.

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

Problem C was very interesting....a lot of people's solutions ( and also my solution!! ) has been hacked

I hacked 2 user with this testcase:

I also hacked with:

:D

I hacked about 9 users with :

0 0

Lol.

I found a hackable solution just before the contest was over. I guess C is the most trick one in this contest.

Very simple problem, but it has some pitfalls.

Why do you have this weird if statement in your code?

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.

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!!

I hoped my soloution had been hacked too, then I could submit the correct one... Grammere jomlam dorost bud??

I'm waiting system testing, for lunch!!! Please, hurry up... :D

Deleted.

Testcase for problem C is to much (about 100 test). Systest will run very low.

there are more than 100 test cases for D problem too

Where is sence to make so many tests for so easy task?..

Here: 3303326

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.

c1*r1 == 0 (mod 2^32), funny mistake!

Great Contest! I realy Liked problems D and E even though i didn't solve them

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 ??

i think you should forgive him and not report this.

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.

thx! very nice contest:)

That was a nice contest, thanks to havaliza and happy birthday to LGM and gpac...

I cant't exactly understand the meaning of problem E ! We are asked to find the maximum of what ? (BitHaval

andBitAryo) what does 'and' mean here?"The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness."

tnx

would u explain about test case 3 ?

2 1000 1000

The sausages can be empty, so give 1000 to BitHaval and nothing to BitAryo :D

tnx, sorry, one more please :D test 8: 4 1 2 4 12 the answer is 15, why?

for example, all to BitHaval: 4 xor 1 xor 2 xor 4 xor 12 = 15

I mean test 8, that is : n = 4 and the numbers are : 1 2 4 12

Oh, sorry. In this case, give 1,2 to BitHaval and 12 to BitAryo.

Oh! I got it now. :|

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.

that was a nice contest thanks to havaliza but why Bitlandians are weird they are amazing

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

Thats not funny I think... :D exactly like the diffrence between visual studio compiler and GNU...

Something i have experienced while using CodeBlock for C++ and G++ compiler !!

When will the plus and minuses appear on the graph???

painting eggs is a very ancient and attractive custom in Iran and the children still do this

Very nice problems. Thanks to authors!

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.

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

Has anyone solved problem 'E' without a trie or with a easier solution to implement ?

I have no idea what this does, but it looks suspicious: http://www.codeforces.com/contest/282/submission/3303893

It seems to be the same ideia using trie. However, the code is a lot more clear and simply.

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 valuer- 1 tom. Now we want to maximize . Notice two things: 1)landmis the only variables sincenis fixed, 2) 0 ≤l≤m≤n. Then just sort the arraysand then for any 0 ≤m≤nuse binary search for digits in the binary representation of to findl. Total complexity is .My submission: 3304910

Thank you a lot ! For me this solution is much easier than author's :)

i think this my solution still wrong, but get accepted http://codeforces.com/contest/282/submission/3309655

because 'is' never change,

and did this solution true after i add is++? http://codeforces.com/contest/282/submission/3312416

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 :)

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.

hmm this is weird thing..happened to one once. let see if someone can explain it

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.

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).

I love this contest.