pkhaustov's blog

Codeforces Round #273 (Div. 2)
By pkhaustov, 10 years ago, translation, In English

Hi, everyone!

Regular Codeforces round #273 for participants from the second division will take place on 16 October, 19:30 MSK. Participants from the first division are able to participate out of the contest.

Problem setter: pkhaustov (Khaustov Pavel, Russia, Tomsk, Tomsk Polytechnic University)

Special thanks to Codeforces team and, in particular, Maxim Akhmedov (Zlobober) for help in round preparations and Maria Belova (Delinur) for translations.

Participants will be given five problems and two hours to solve this problems.

Points distribution: 500-1000-1500-2000-2500

UPD: +10 minutes to start

Good luck!

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

Comments Comments (185)
| Write comment?
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Zlobober has contribution +125. But why he isn't in top contributors?

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

Bad luck to everyone , because I want to be first at ranking. I gotta have the only good luck in participants.

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

It seems like it would be a lot of programming with no math

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

    You meant a lot of math with no programming right? Because that's two different things.

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

      So I guess no math this time :(

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

        insert sad music here

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

          I believe you mean: insert *happy music here

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

    Wow, apparently other people share my ideas as well :o

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

    As it turns out, all problems are math (with some programming)...

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

      REVENGE!!!

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

      Also, I noticed that usually when competitive programmers say "mathematics", they mean "number theory" :P

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

        Combinatorics (counting) is also common. I think D is combinatorics?

        Other fields of mathematics are hard to use in computer programming. I once made an algebra/geometry problem of sorts (given three points on plane, find a line that minimizes the sum of distances from the points to the line), but those kinds of problems are hard to find.

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

          Sure, dp/greedy are all combinatorics and so, are essentially mathematics. The point I was trying to make is that many people don't accept this and according to them, mathematics problems means problems involving numbers and equations. So, if some such guy says that some contest was full of math problems, it means that it was full of number theoretic or elementary algebra problems.

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

    you know you are in a math oriented contest when memory of your first 3 solutions is 0 Kb.

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

    Most of programming doesn't involve math at all: look what typical job postings say.

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

Looked to become Blue Coder

:D

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

GOOD LUCK & HAVE FUN!!!

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

With the timing of this round, does it mean we won't have a gym training this week or it will be moved to another day?

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

Your last contest had nice problems.

Thank you for creating another contest.

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

Hello. This is my second contest on Codeforces and strangely, I don't get an option to register for this round. Any idea why it's so?

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

    Registration will be opened later (see on Contests tab).

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

I'm registering the first :P

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

Thank you for earlier registration opening! ;)

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

How do I get contribution scores? Thanks.

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

    by not getting downvotes

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

      no, by getting upvotes

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

        No, by getting ~1.5 times more upvotes, than downvotes.

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

          from here

          Your contribution number will increase depending on the evaluations you get — I don't reveal the function, but it'll increase quickly at the beginning, and then the process will gradually become slower. I plan to experiment with the function from time to time, searching for the most suitable variants.

          so I guess only MikeMirzayanov knows the exact answer to this question.

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

            Thank you very much!

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

          THX~

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

        THX~

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

      THX~

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

    Strangely nobody has answered your question in details. To get contribution scores you can try to:

    • write editorials for the round which do not have any.

    • prepare a CF round or at least a gym contest. Announcement might bring a lot of contribution points, though it depends on the announcement.

    • post some funny jokes on CF. This seems to be the most effective way but you need to stay on-topic while posting the jokes.

    • maybe write some good programming related articles here? Didn't try this one though.

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

Please give the score distribution just 20 mins left.

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

Delayed

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

Delay :/

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

Those who cannot remember the past are condemned to repeat it. By Dynamic Programming How many up votes for Dynamic Programming??

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

I registered for the contest but still couldn't submit as if I wasn't registered. This has happened with my friend once too. Some bug. admin please fix! -_-

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

Problem C = a bunch of hacks.

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

How to solve D?

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

    You find the maximum possible height (approximately ) and do dynamic programming: DP[h][r] = the number of possibilities to build the tower with height h and using r red blocks (and h * (h + 1) / 2 - r green blocks).

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

      I saw some faster solution. This one looks easy to TLE(Although I used this one and locked)

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

      so O(r * sqrt(r)) will pass? :O

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

      h <= 900 r <= 2 * 10^5, long long dp[900][2 * 10^5]. Won't it be a memory or time limit?

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

        The recurrence only uses the previous line, so we don't have to keep the whole matrix.

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

          dynamic line-by-line needs only O(max(g,r))memory

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

      Can it be solved using the no. of partition possible for a number.summing from the maximum possible red to minimum possible red using constraints of green balls ?

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

    R and G are 2e5 so number of levels are at most 600 ! It can be solved like Knapsack problem !

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

      could you explain what kind of knapsack?

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

        DP[i][j] :: How many ways exist that we choose some level between 1 to i and sum of levels widths be j ...

        DP[i][j] = DP[i-1][j] + DP[i-1][j — i];

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

          when i tried to store dp[i][j] i got memory limit error. it is possible to use only dp[j] vector. And h times recalculate values.

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

      R+G <= 4e5

      number of levels < 900

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

        You are right, but it is not important ! 1e3 * 2e5 = 2e8 and is fast enough.

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

I have never seen so many hacks.

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

    Because you have participated in so many contest, right?

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

      Haha, I have participated in some contest, but I forgot that handle! So I had to register a new one.

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

I made 12 successful hacks for problem c, but my own solution is wrong. Ridiculous.

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

Would someone please tell how to solve D !

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

    try to formulate a top-down DP solution that takes O((r+g)*h), this will give you MLE, then try to formulate the same DP bottom-up, this will require only O(r) in space and runtime of O((r+g)*h), if you see my code you will see both approaches

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

how to solve problem D?

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

C hack case?

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

I'm seeing people in top 10 (including unofficial participants) which had a wrong answer of test 3 of problem A!

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

    case 0 0 0 0 0

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

    it is easy to forget about 0 case, ant first time I had fogotten too/

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

    Yeah, I'm one of them. It's so easy to miss the non-zero requirement. Wish they hadn't put this case in pretests for another gazillion of hacks ;d

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

How to solve E? (Quite interesting problem)

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

Thank you pkhaustov for the round. I especially enjoying hacking the solutions of C! Apparently the pretests were rather weak.

Unfortunately, this seems to cause some agression among the contest participants who happen to get hacked... after hacking this guys solution, I got this "friendly" message, of which I can't even understand the half:

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

    LOL ! He's translating the same message into different languages !! what a guy :/

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

Why admin has block the page that we can see contest's history of each member?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Duplicate comment. Please ignore.

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

Hints for problem D:

Let h denote the maximal height made.

  • Main observation: h <= sqrt(rleft + bleft).
  • Trivial dp will be to maintain currrent h, rleft and gleft.
  • It can be optimizied to dp(h, rleft) because gleft is a redundant parameter.
  • Then optimize space by making observation that h is dependent on h — 1.
  • Complexity h * (r + g).
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so overall complexity would be O(r.sqrt(r)) ? I didnt't realise that would pass, so i didn't code it up :\

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

      It's the same for me :/ I thought about this algorithm, and I said "Meh, this doesn't work" because I saw the limit of r as 10^9.

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

    that was exactly what i did, but received RTE ): no idea why.. EDIT: not exactly, i used a map to store answer, instead of optimizing space.

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

    This should be O(10^8) which i think it should give TLE :D

    However I am surprised because (10^8) gives MLE but don't give TLE :D

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

    the first observation is false (and the reason I got RTE during contest). For r = g = 2 * 105, H = 793. My upper limit for H was 700, using 800 should result in TLE instead of RTE :D

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

      it should be , as if we could use all of them and obtain a height h we'd have

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

Whoa ! what a speed of system testing !

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

Terrible!! What such a hack attempts :D

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

This is the shortest solution for C problem that I ever wrote !!!

sol = min(sum / 3, t[0] + t[1])

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

    Can you please explain the solution? I can't get it till now. Thanks

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

      Max number is sum / 3. I thought in the idea to form groups taking 2 items from the bigger one and taking only one item from the lower groups each time. Using this way if sum / 3 is bigger than the sum of the 2 lower values then it means that I can get only a + b (sum of the two lowest values) taking 2 from biggest value and 1 from any lower value. I am thinking in a mathematical proof but this was my approach.

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

    you are right

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

    you forgot to sort t =)

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

    I solved it using the same solution .. do you have a proof of correctness?

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

      No, I don't have a proof. I saw that the max number is sum / 3 and then I thought in the idea to form groups taking 2 items from the bigger and taking only one item from the lower groups each time.

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

    Hi can you please explain it? Thanks :)

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

    assume t[0] <= t[1] <= t[2]. and sum = t[0] + t[1] + t[2].

    best case would be sum / 3. because no matter what we do we will always be left with sum % 3 balloons. now when can we get sum / 3 tables and when we can not:

    case 1: if 2 * (t[0] + t[1]) <= t[2] than it is obvious that we can not get more then t[0] + t[1] tables because at each table at least 1 balloon is subtracted from t[0] + t[1], and by taking 2 from t[2] and 1 from t[0] + t[1] at each turn we can get exactly t[0] + t[1] tables.

    case 2: if 2 * (t[0] + t[1]) > t[2]. let's prove that we can get sum / 3 tables in such case. by tactic taking 2 from t[2] and one from max(t[0], t[1]), t[0] + t[1] will not become zero before t[2] becomes zero, which means that at some point t[2] will become at most max(t[0], t[1]). and at that point difference between t[2] and max(t[0], t[1]) will not be more than 2. no we know that max(t[0], t[1], t[2]) — second_max(t[0], t[1], t[2]) is not more then 2. we can use this as an invariant. tactic taking 2 from max and one from second_max does not change invariant. now suppose we have some choosing tactic, we are stuck when we have situation like this a 0 0 where a >= 0 or 1 1 0. if a <= 2 it means choosing was optimal because no matter what we do we will be left with sum % 3 ballons. and second finish(1, 1, 0) is also optimal by same reason. answer in both cases will be sum / 3. according to our invariant we will not be left with a 0 0 with a > 2 because if a > 2 then our invariant does not hold. so we now that our choosing was optimal and answer is sum / 3.

    now what min(sum / 3, t[0] + t[1]) does is exactly checking if 2 * (t[0] + t[1]) <= t[2]. because if t[2] >= 2 * (t[0] + t[1]) (case 1) then sum / 3 = (t[0] + t[1] + t[2]) / 3 >= (t[0] + t[1] + 2 * (t[0] + t[1])) / 3 = t[0] + t[1]. so min(sum / 3, t[0] + t[1]) will be t[0] + t[1] (exactly answer to case 1).

    if t[2] < 2 * (t[0] + t[1]) (case 2) then sum / 3 = (t[0] + t[1] + t[2]) / 3 <= (t[0] + t[1] + 2 * (t[0] + t[1])) / 3 = t[0] + t[1] so min(sum / 3, t[0] + t[1]) will be sum / 3 (exactly answer to case 2).

    hope it was helpful :D

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

      Do you think we can extend it to any for any number of colors? In the contest I came up with this formula for 2 numbers i.e. min((r+g)/3,r). You have proved it for 3 numbers. Can it be extended for 4,5,6,7...?

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

        Any takers?

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

        Yes, I think it can be extended. Everything is the same, we only check if max is more then 2 * (sum — max).

        sorry for late replay.

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

      Thanks sb-man , Was having a hard time finding explanations for old problems......:P

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

      This comment deserves a thousand up-votes.

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

TLE on test 11 in D cuz I used long long int. Changed it to int AC. -_-

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

Gotta appreciate the fast system tests & rating updates at the same time. Usually one of them only occurs that fast :D

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

in cf 273 div 2 , I have submitted problem A,B,C. but I got no verdict for problem B . in my submissions it is written "skipped" !! whats the problem ?? can anyone plz help me !! http://codeforces.net/submissions/kifayat

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

Heh, solved 3 problems and became blue!!! It have surprised me!

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

    I solved 3 problems and became purple and I am not surprised :D

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

Question about E) How comes the number "11" to not be a wavy number? I cannot find the definition like two adjacent digits should be different..

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

    Read the problem statement. It says: "A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits." For the first and last digits the adjacent digit if exits should also be strictly larger or strictly less than the digit. "strictly larger" or "strictly less" does imply that two adjacent digits should be different. Hence the number "11" cannot be a wavy number.

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

      "for any digit of its decimal representation except for the first one and the last one..."

      So 11, ignoring the first and last digits, becomes an empty string; all of its digits are (vacuously) strictly more or less than the adjacent digits. Of course, this is definitely an oversight on their part.

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

        Completely agree, the statement is wrong, 11, 22, 33,..., 99 are wavy numbers.

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

        After loosing a lot of time, I had to assume that 11, 22, ...,99 are not wavy in order to get the problem accepted. What disappointing.

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

questions was very easy and interesting.

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

Can anybody tell me concepts in problem A and B

my solution : http://codeforces.net/contest/478/my

Constantly getting wrong answer.

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

How to solve C? Pleas with proof

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

    if you wont i will send my solution. my solution is to short. i think you will uderstand

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

    First of all take the maximum if it is >2*(sum of other two) then answer will be (sum of other two) because for every element taken of rest two take 2 elements of maximum. now suppose max<= 2*(sum of other two) then answer will be (sum of three)/3. you can observe this by take the balls greedily.

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

      This is your algorithm, but what is your proof?

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

        Easy to noticed there are only 2 case of arrangements, RRG and RGB. Use the second one when number of colors "balanced" enough, and the first one to the rest. Then consider if all arrangement is first scenario. So, you have (a[1] + a[2]) triples, and use 2 * (a[1] + a[2]) from the a[0]

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

thanks a lot to KhaustovPavel for contest.

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

Your last contest and this contest has nice problems.

Thanks a lot pkhaustov . you are a good designer(problem).

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

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

Can D be solved without dynamic programming? (like a combinatorial formula)

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

    it looks like can, but difficult to understand and to find a formula.

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

    It looks like it's related to the problem of integer partitions — the number of ways to make a tower using R red blocks is the number of ways to write R as a sum of unique positive integers. I got stuck writing a solution like this, but it seems doable.

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

      that's wrong, because you don't need to use all the blocks

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

        You're right — so the full solution would be to find how many different numbers of red blocks you can use to make a tower and sum these partitions for each number.

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

huy guys. could you tell me what I dont understand in task A (yeah I know its simple)?? I feel depressed because of it :(

JS: (fails on test 3)

var N = readline().trim().split(" ").map(function(x){return parseInt(x);}); var sum = 0; for(var i=0; i < N.length; i++){ sum+=N[i]; } if (sum%5 != 0) {print(-1);} else {print(sum / 5);}

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

    if sum==0 the answer is -1 to. Because all values need to be positive.

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

    problem says non zero coins were placed as bet so if all input was zero then you should print  - 1

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

When does the Editorial be showed?

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

Problem E seems very interesting, could anyone give a hint?

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

Can I get the explanation for problem C? I don't understand the logic behind it.

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

lol my B (http://codeforces.net/contest/478/submission/8257290) failed because js arithmetics check in js console: 499967831017438365 * 2 / 2

output: 499967831017438340

:)

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

we are waiting for editorials!

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

Oh! The solution is in Russian while my Russian is very poor. I'm looking forward the solution in English. And I hope that the author can offer us the solution in English.

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

It was a great contest!!

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

Where can i find editorial of this contest?

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

I don't know why haven't the editorial been added until now .

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

My English editorial for this round.

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

    Anyone having trouble understanding Div 2 C should try this Editorial.

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

for Problem C , can someone explain this test: 100500 100500 3 Answer : 67001

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

why in the hell the editorial are not available

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

Sorry for the necro-post.
I posted an english explanation to problem D here. Since the original blog is in Russian, it does not show up in the English version of codeforces, hence my comment here.

→ Reply