lewin's blog

By lewin, history, 11 days ago, In English,

I recently added the div 1 regional to the gym here. You can virtual participate at any time.

Solutions are available on the contest website if you want to look at them up afterwards here (soon...). Feel free to discuss problems afterwards.

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

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve I and M?

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

    I:There will be an optimal solution in which all the added numbers are in nonincreasing order. Use this to formulate an O(n2k) dynamic program and then optimize using divide and conquer trick or convex hull trick.

    M: I'm unsure about the solution, but apparently it can be proven that you spend all your money on at most two people. Then some sort of ternary search should work.

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      For M, my team's solution was to map the soldiers to (x, y) points (budget*potency/cost, budget*health/cost) and then the goal becomes to maximize x * y. So then you build the convex hull of those points.

      That way, it's only ever optimal to combine soldiers that are adjacent along the convex hull. The reasoning behind that is if you tried to merge more than 2 soldiers, you'd effectively be drawing a line between two segments on the convex hull (and of course that segment lies strictly inside the hull) and the product of any (x, y) on that segment will never be greater than some (x, y) product along the outer segments of the hull.

      So it's not really a proof but there's some intuition behind why you only combine 2 soldiers (also other solutions don't seem to use convex hull at all).

    • »
      »
      »
      26 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There will be an optimal solution in which all the added numbers are in nonincreasing order.

      I'm having trouble convincing myself of this. Do you have any proof or good intuition on why it's true?

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

    M: Transform (c, h, p) to (h * C / c, p * C / c). The answer is a combination x1 * v1 (vi is (hi, pi)) + x2 * v2 + ..., you take that vector and take x*y. But that combination has other constraint, x1 + x2 + ... + xn == 1 and xi is in [0, 1] so it's a convex combination (https://en.wikipedia.org/wiki/Convex_combination). This means that you can take the convex hull and solve the problem for the vertices and edges and it will have the greatest answer.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve M with c++? It seems like there is a precision problem. My python code using (exactly) the same logic got AC.

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

how to solve d?

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

    dp[number of digits filled in][this number is k modulo m] or dp[n][k] can transition to dp[n+1][2*k] and dp[n+1][2*k+1]. dp[n][k] = (number of ways to get to this state from [0][0], sum of 1's of these ways). answer is dp[bits][0].second

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve K?