cgy4ever's blog

By cgy4ever, 11 years ago, In English

You can find the editorial and my solutions here: https://github.com/cgy4ever/CF228

389A - Лиса и игра с числами

First we know that: in the optimal solution, all number will be equal: otherwise we can pick a and b (a < b) then do b = b — a, it will make the answer better.

Then we need an observation: after each operation, the GCD (Greatest common divisor) of all number will remain same. It can be proved by this lemma: if g is a divisor of all number of x[], then after the operation, g is still the divisor of these numbers, and vice versa.

So in the end, all number will become the GCD of x[].

Another solution that can pass is: While there exist x[i] > x[j], then do x[i] -= x[j]. We can select arbitrary i and j if there exist more than 1 choice.

389B - Лиса и крест

Let's define the first # of a shape is the cell contain # that have the lexicographical smallest coordinate. Then the first # of a cross is the top one.

Then let x be the first # of the given board. (If the board is empty, then we can draw it with zero crosses.) x must be covered by a cross, and x must be the first # of the cross. (You can try 4 other positions, it will cause a lexicographical smaller # in the board than x)

So we try to cover this x use one cross, if it leads some part of the cross covers a '.', then there will be no solution. If not, we just reduce the number of # in the board by 4, we can do this again and again.

389C - Лиса и коробки / 388A - Лиса и коробки

We need some observation:

  1. There exists an optimal solution such that: in any pile, the box on the higher position will have a smaller strength.

  2. Let k be the minimal number of piles, then there exists an optimal solution such that: The height of all piles is n/k or n/k+1 (if n%k=0, then all of them have the height n/k).

We can prove them by exchange argument: from an optimal solution, swap the boxes in it to make above property holds, and we can ensure it will remain valid while swapping.

Then for a given k, we can check whether there exist a solution: the i-th (indexed from 0) smallest strength needs to be at least i/k.

So we can do binary search (or just enumerate, since n is only 100) on k.

389D - Лиса и минимальный путь / 388B - Лиса и минимальный путь

First we need to know how to calculate the number of different shortest paths from vertex 1 to vertex 2: it can be done by dp: dp[1] = 1, dp[v] = sum{dp[t] | dist(1,t) = dist(1,v) — 1}, then dp[2] is our answer.

We need to do dp layer by layer. (first we consider vertexes have distance 1 to node 1, then vertexes have distance 2 to node 1 and so on.) So we can construct the graph layer by layer, and link edges to control the dp value of it.

My solution is construct the answer by binary express: If k is 19, then we need some vertexes in previous layer such that the dp value is 16, 2 and 1. So we just need a way to construct layer with dp value equals to 2^k.

In the first layer, it contains one node: 1, it has the dp value 1. In the next layer, we can construct 2 nodes, with dp value equals to 1. (We use [1 1] to denote it). And the next layer is [1 1 2], then [1 1 2 4], [1 1 2 4 8] and so on. So we need about 30 layers such that gets all 2^k where k < 30. It uses about 500 nodes.

389E - Лиса и игра в карты / 388C - Лиса и игра в карты

First let's consider the case which all piles have even size. In this case, we can prove: in the optimal play, Ciel will gets all top most half cards of each pile, and Jiro gets the remain cards.

We can prove by these facts: Ciel have a strategy to ensure she can get this outcome and Jiro also have a strategy to ensure this outcome. (For Jiro this strategy is easy: just pick the card from pile that Ciel have just picked. For Ciel it's a little bit harder.)

Why we can conclude they are both the optimal strategy? Ciel just can't win more, because if she played with Jiro with above strategy, Jiro will get the bottom half of each pile.

Then we come back with cases that contain odd size piles. The result is: for odd size pile, Ciel will get the top (s-1)/2 cards and Jiro will get the bottom (s-1)/2 cards. Then what about the middle one? Let's denote S is all such middle cards. Then we define a reduced game: In each turn, they pick one card from S. The optimal play for this game is easy: Ciel gets the max one, and Jiro gets the 2nd largest one, and Ciel gets the 3rd largest one and so on.

We can prove Ciel have a strategy to get: all top half parts + cards she will get in the optimal play in the reduced game. And Jiro also have a strategy to get: all bottom half parts + cards he will get in the optimal play in the reduced game. And these strategy are optimal.

388D - Лиса и идеальные наборы

A perfect set correspond to a linear space, so we can use base to represent it. We do the Gauss–Jordan elimination of vectors in that set, and can get an unique base. (Note that we need to to the all process of Gauss–Jordan elimination, including the elimination after it reached upper triangular)

And we can construct the bases bit by bit from higher bit to lower, for a bit:

  1. We can add a vector to the base such that the bit is the highest bit of that vector. And at this time, all other vector will have 0 in this bit.

  2. Otherwise we need to assign this bit of each vector already in the base. If now we have k vector, then we have 2^k choices.

And when we do this, we need to know what's the maximal vector in this space. It's not hard:

  1. If we add a vector, then in the maximal vector, this bit will be 1.

  2. Otherwise, if we don't have any vector in base yet, then this bit will be 0. Otherwise there will be 2^(k-1) choices results in this bit of maximal vector will be 0, and 2^(k-1) choices results in 1.

So we can solve this task by DP bit by bit.

388E - Лиса и метеоритный дождь

All tasks beside this are very easy to code. And this one focus on implementation.

We can represent the orbit of each meteor by a line in 3D space. (we use an axis to represent the time, and two axis to represent the position on the plane.)

Then the problem becomes: we have some lines in 3D space (they are not complete coincide), find a largest clique such that each pair of lines touch at some point.

We need this observation: If there are 3 lines in the optimal clique, and these 3 lines are not share a common point, then all line in this clique will on a plane.

By using this observation, we only need to consider 2 cases:

  1. All lines in the clique have a common point.

  2. All lines in the clique are on the same plane.

Both are easy tasks in theory, but it needs some coding.

There are two ways:

  1. Use integer anywhere. Note that the coordinates of intersection can be rational number, but can't be irrational, so we could do this. We can use some way to encode the plane, direction.

  2. Use floating number. To count same number of points, we can sort (x, y, z) by using the following compare function: if (abs(A.x — B.x) > eps){return A.x < B.x} otherwise { if(abs(A.y-B.y)>eps){return A.y < B.y} otherwise return A.z < B.z}.

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

| Write comment?
»
11 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Thank for timely editorial. I think Markdown is better when publish something on Github. Isn't it?

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

    Yes, I'm working on it. :)

    The website seems to be not stable at this time. So I post them in other sites to ensure all people can see it.

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

      Maaan is it so hard to COPY ?

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

        Sorry for the delay.

        When I was submitting my post that contains the editorial, it always returns "Codeforces is now unavailable." so I just can't post it.

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

Nice problemSets @cgy4ever , although I misunderstood the problem-B 389B - Лиса и крест upto 1 hrs :(

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

due to my slow internet speed i can not see your editorial on github because my country internet has problem with https!

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

does anyone have a better solution for div2 C problem?

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

    Have a look at mine 5878414

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

    I don't know if this is a better way but I didt in the contest.

    Start making a pile with the low strength and while possible, look for a box that can support at least 1 box, then at least 2 boxes, 3, etc, repeat it while you have boxes.

    My solution: 5879464

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

      Greedy is also a nice solution.

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

388C — Fox and Card Game This problem is good magic

»
11 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

hii everyone,in Div II E,I can't understand why the optimal play for JIRO is to take the bottom most card from the same pile from where CIEL is picking?should not it try to pick the maximum value among all bottom most card at it's every move??

Please someone explain why the strategy presented in the editorial is optimal.

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

    Ok, I'm afraid I do not have a rigorous proof for this. I'll just explain to you why I think it is right.

    First of all, we need to understand that both Ciel and Jiro are smart. Now, whenever it is Ciel's turn, he will pick the "best pile" and try to take everything from that pile and then move on to the next "best pile". Jiro knows that his friend Ciel is smart, so he will try to stop him from taking everything. This can be done only if he picks from the same pile that Ciel does.

    But your question is — what if there is a different pile whose bottom-most card is much better than the bottom-most card of the pile from which Ciel is picking right?

    My answer to this is that, this situation will never arise. Because if there is such a pile, then Ciel will try to take that card in the first place and therefore, Ciel will be picking from the same pile that Jiro will want to pick from.

    Am I making sense? Or is there a flaw in my argument?

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

      Yes I'm also thinking along the same line.Both are playing optimally and if Ciel is chosing any pile then jiro knows that this pile has better cards in the botttom half.So he won't choose ciel to take the advantage and vice versa.

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

I have a different idea on D div1 388D - Лиса и идеальные наборы but I failed on getting some relations in one step.

Let M be the maximum element in set S . Then if S is a perfect set, its elements should have all bits equals 0 on positions in M's binary representation(otherwise there must exist another element bigger than M). So let cnt = (number of 1's in binary repersentation of M), then the number of perfect sets which has M as its greatest element is determined by cnt . Well, this is the step I can't come up with a solution(actually the target is to find the number of perfect sets which has 2^cnt-1 as its greatest element).

Then the last step is simple. We can apply something like doubling algorithm on the problem.

We are asked to find the number of perfect sets with all the elements not greater than N . Let's suppose N+1 is a power of 2 then its easy to calculate how many numbers not greater than N has cnt = 1,2,...m where m is the length of N in binary representation. That's just simple combinatoric number C(n,i) (1<=i<=n) . And if we have done the previous step, it's easy to get the result.

Then think about common cases of N . Let's take the highest bit of N and since all above bits are determined, the number of 1's will just add a constant value. So calculate this part and subtract that highest bit of N and do the same thing on remaining value of N , until N=0 . At that time we will get the correct answer.

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

dp[1] = 1, dp[v] = sum{dp[t] | dist(1,t) = dist(1,v) — 1}, then dp[2] is our answer. What's v means? what's '|' means? What's dp[v] means?

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

    v — vertex, answer for which we are getting at this moment, | — means "such as", dp[v] — number of ways from 1 vertex to this one

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

Can someone please explain solution of Div2-D. Thanx

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

    You can think about binnary. Such as (13)10=(1101)2=((1+(2+0)*2)+1)*2+1

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Here's my implementation of the editorialist's explanation of Div-2 D / Div-1 B: 45480077. I implemented the layers as [1], [1, 1], [2, 1, 1], [4, 2, 1, 1] and so on.

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

Very good contest and nice editorial. Hope from now on I see more contests from you.

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

Did anyone come up with a DP solution for Div.2 C/ Div.1 A?

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

Объясните, пожалуйста, разбор задачи "388D — Fox and Perfect Sets" на пальцах. Как-нибудь без Гаусса и базисов.

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

fox and card games is a great problem.thanks!

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

Can anyone explain div2 C question? I did not understand the editorial.

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

    s[i]>=i/k -> k*s[i]>=i There are i boxes' strength smaller than i-th box. So we need to check if the boxes before i-th can be held.

    (I don't know whether I have understood correctly...)

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

Great Problem! I really enjoy it.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In 388C, I'm having a hard time understanding why Jiro's optimal strategy would be to pick the pile Ciel just picked. Why not pick a pile which has a better bottom part than the one Ciel is picking? According to some comments, Ciel would then pick from the second pile-what if another pile has a much better top part? Could someone please help? I saw this problem first 6 months ago, and I had a hard time understanding why this greedy is correct; I saw this problem again today and am having trouble with it again, with no progress.

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

    Let's consider such a two-piles situation:

    111100

    001111

    is better for Ciel.

    "1" means this card is picked by Ciel,while "0" by Jiro.

    We know that better for Ciel means worse for Jiro.

    So if

    111100

    001111

    is better than

    111000

    000111

    for Ciel.

    Then when Ciel picked the first three cards from pile 1,Jiro can just pick the last three cards from pile 1 and finally lead to the result:

    111000

    000111

    which is not better for Ciel.

    Generally, if the final result is not balance(half from top and half from bottom) while balance is better than such result for Jiro, Jiro has the ability to adjust it to be balance.So do Ciel.

    Therefore,it reaches balance.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

@cgy4ever, github link shows 404 error(Page not found). Kindly fix it.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the DIV1B problem with simple recursion and Divide and Conquer.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me some examples of the similar problems to DivC?? I think this problem is very nice for train brain xD

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

I know I am very late but can someone pls explain to me div 2C/div1A. Thanks in advance...

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

    https://codeforces.net/contest/388/submission/83605110 Here you go, if you don't get it feel free to ask

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

      is this any algorithm

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Well you can call it a greedy algorithm, when we try to apply greedy by placing the heaviest block in bottom, a little problem occurs because of blocks of same strength for example in case of 10 2 2 1 1 0 0
        If you try to apply greedy by choosing the strongest block
        10 2 2 1
        1 0
        0
        = 3 heaps
        Which is wrong answer as sometimes we lose opportunity to create lesser heaps, as in this case if we use the second 2 to make another heap we can do better
        10 2 1 0
        2 1 0
        = 2 heaps
        So I apply greedy in the reverse direction by picking the smallest strength brick and placing below it the next smallest brick, this way the optimal number of heaps will be formed as in above example
        choose 0, then you need >= 1, choose 1, then you need >= 2, choose 2, then you need >= 3 choose 10
        repeat until you have chosen all the bricks
        If you don't get anything, feel free to ask :)

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

          Thanks, It helped me to understand your solution idea. And finally, I solved this one.

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

      thank you.