havaliza's blog

Codeforces Round #173 (Div. 2)
By havaliza, 11 years ago, In English

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!

  • Vote: I like it
  • +279
  • Vote: I do not like it

Comments Comments (108)
| Write comment?
»
11 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Happy Birthday!!!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    ALL say HappyBirthday No one ask for score distribution :D

    → Reply
»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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!

→ Reply
»
11 years ago, # |
  Vote: I like it -21 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I was surprised a lot! thank you havaliza :)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Taxiiiiiii.....

        Infinity please.

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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.com/bestRatingChanges/213901:)

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A bunch of Problemsetters from IRAN :D

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Happy Birthday

→ Reply
»
11 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Happy Birthday guys :) god bless you !!

→ Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

wow! More than 3000 registered users :D .

→ Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

please tell us about score distribution ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
← Rev. 9   Vote: I like it -11 Vote: I do not like it

...d

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

is "222". W T F???

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who solved D and how?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      2 2 3

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My submission 3308449

    → Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    3306281 0_o

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        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.

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be solved by greedy algorithm using trie.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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<<a<<endl;
cout<<a;

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]

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I hacked 2 user with this testcase: 

    111
000
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I also hacked with:

      1
0

      :D

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

      I hacked about 9 users with :

      0 0

      Lol.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Very simple problem, but it has some pitfalls.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there are more than 100 test cases for D problem too

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Here: 3303326

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -40 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    i think you should forgive him and not report this.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

thx! very nice contest:)

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    "The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness."

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      tnx
      would u explain about test case 3 ?

      2 1000 1000

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! I got it now. :|

      → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thats funny. I solved my solution using Delphi compiler: http://codeforces.com/contest/282/submission/3302945 The same code, using FPC: http://codeforces.com/contest/282/submission/3311282

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Very nice problems. Thanks to authors!

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I love this contest.

→ Reply