zxqfl's blog

By zxqfl, 7 months ago, In English,

Here are the authors of the problems:

I'd like to thank the Codeforces team for their help, particularly KAN, who was the tester for this round.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial of Canada Cup 2016
 
 
 
 
  • Vote: I like it  
  • +86
  • Vote: I do not like it  

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem E:

find the next coin that Alfred will use (this can be done in O(1) with O(c) pre-processing)

But how can this be done? I don't see the way... :(

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

    Keep an array a such that a[i] gives the most valuable coin that is not worth more than i dollars.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Oh, that's smart. But I should fast modify this array every time I try new answer, shouldn't I? So should I use something like segment tree or is there simpler solution?

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

        Just check whether this coin would be better than the coin you get from performing the array lookup. There's only 1 coin that needs to be added, so it's still O(1).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      so it means, value 100 wud b in a[100]?? but in that case wont it be a wastage of space, all the other locations wud b empty?

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I can't understand proof for problem E.

Can someone help me with some different explanation?

Appreciate the help!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me neither. Can someone kindly explain again ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Problem E:

    Imagine you have N coins. First you put a frequency array for each coin and also a lookup array where NEXT[c] = (greater coin that does not exceed c), both can be done in O(N) precomputation. The thing is this will help us simulate the algorithm in , starting with C (total cost) we can get NEXT[C] and subtract all the coins possible from C this is done with min(FREC[NEXT[C]], C / NEXT[C]). The thing is that all the coins subtracted in each step are different. Since they are different, it is not POSSIBLE to have subtracted more than different number without exceeding C. This can be seen assuming the worst case of numbers subtracting which will sum up to C or more. So our simulation is efficient. Now we need to run the simulation with each coin. The thing is, giving only one coin will give the same result than giving multiples (proof below). So we can run the simulation with each possible coin from 1 to C.

    Proof for needing only one coin: If you remove coins in order -> S - c1 - c2 - x - c3 - c4 - c5 - y - c6... then it is proven that instead of subtracting x in step three we can subtract x+y and he will pick the same set of coins. We know for sure that S - c1 - c2 - x - c3 - c4 - c5 >  = y + c6..., accommodating this expression we have S - c1 - c2 - x - y >  = c3 - c4 - c5 - c6... and also choosing y before will not add another coin between y and c3, because the sum at that point is even greater. With this we proved that the set of coins will be the same giving him x+y or (x and y).

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

Editorial for problem D seems to be missing, where can i find it?

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

    You can simply simulate the process. Limak will always try to disqualify the team which has higher number of balloons than him and which can be disqualified with the least cost (cost = weight_of_team — no_of_balloons + 1). Put all the teams with more balloons than Limak's team in a priority queue and keep disqualifying the best choice. When you disqualify a team, the count of Limak's balloons decreases so you may need to push more teams in the priority queue (this can easily be done by maintaining a global sorted list of teams based on non-increasing order of total initial balloons, and you simply need to pop from the back). Do this process until no more teams can be disqualified. The final ans is 1 + minimum size of priority queue during all these steps. I used binary search in my code but it is not needed.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Am I the only one who don't understand the samples in problem F ?
can someone please explain it ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here are the optimal moves, I will leave the task why is this optimal to you.

    Test1: Alice takes [1,4], Bonnie takes [3,1]

    Test2: Alice takes [4], Bonnie takes [0], stack one remains untouched.

    Test3: Alice takes [0], Bonnie takes [10].

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

In problem F, case a + b < c + d, I still don't understand why we can change the stack to a photo with value (a - d, d - a) if a > d, and (c - b, b - c) if b < c.

I know the reason of a - d and b - c but d - a and c - b seem to be confusing to me.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In the a > d case, this is equivalent to deleting the photo and adding a - d to the final answer. Probably I should have written that in the editorial instead as it would be clearer. The method of substituting a different photo just results in slightly shorter code.

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

Hello, i got question regardings problem D.

I've had idea to solve it using Heap, my idea was to sort the array and to add all teams to the heap that have more balloons then i do..After i pop out of heap i down count my balloon to current — deleted_one[y] — deleted_one[x] + 1.After i do that i go down the array to find new position for my team.New position would be (total balloons — deleted_so_far — current_position — 1) and after i do that i re add elements to heap again starting from that position to position i was previously on , untill there is nothing in heap or (y-x) > then my balloons...I've stress tested my solution 100 times with some AC code and it always showed correct answer but i get WA on test 6... Can someone help me out ?

Code in C : http://codeforces.com/contest/725/submission/22164899

Cheers

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi. I am confused somehow regarding Div.2 problem A. If the ball starts at position i, then it should hit bumpers from position i or from position 1?