Блог пользователя cgy4ever

Автор cgy4ever, 10 лет назад, По-английски

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

389A - Fox and Number Game

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 - Fox and Cross

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 - Fox and Box Accumulation / 388A - Fox and Box Accumulation

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 - Fox and Minimal path / 388B - Fox and Minimal path

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 - Fox and Card Game / 388C - Fox and Card Game

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 - Fox and Perfect Sets

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 - Fox and Meteor Shower

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

Разбор задач Codeforces Round 228 (Div. 1)
Разбор задач Codeforces Round 228 (Div. 2)
  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -35 Проголосовать: не нравится

      Maaan is it so hard to COPY ?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        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.

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Nice problemSets @cgy4ever , although I misunderstood the problem-B 389B - Fox and Cross upto 1 hrs :(

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

does anyone have a better solution for div2 C problem?

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I have a different idea on D div1 388D - Fox and Perfect Sets 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.

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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

»
10 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Can someone please explain solution of Div2-D. Thanx

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Объясните, плз задачу див.1 С (непонятна стратегия)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Объясните пожалуйста стратегии игроков в див1 С. Спасибо

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

fox and card games is a great problem.thanks!

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Problem! I really enjoy it.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      is this any algorithm

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thank you.