Lewin's blog

By Lewin, history, 11 months 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
  • +68
  • Vote: I do not like it

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

How to solve I and M?

  • »
    »
    11 months 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.

    • »
      »
      »
      11 months 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).

    • »
      »
      »
      11 months 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?

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

        Some intuition: let's say there are two undecided positions i and j. They will divide the array in three parts A, B and C in something like this:

        -----A------|i|------B-----|j|-----C-----

        Let's say there is some value Oi which is the greatest optimal value to be chosen to be in position i. The smaller Oi is, the greater is the number of elements to pair with it in part A; the bigger Oi is, the greater is the number of elements to pair with it in part B and C.

        Let's say Oj is the same thing for position j. The only difference is that now the smaller Oj is, the greater is the number of elements to pair with it in part B.

        So, let's say Oj = Oi. If we increase Oj, obviously it will be worse than not increasing, because the greater Oi was, the greater the number of pairs would be made with part B, and Oi is optimal by definition. Now, even worse, the number of pairs made within B is greater if Oj is smaller. Thus, it's always optimal to make Oj ≤ Oi and you can extend this to any number of undecided elements.

  • »
    »
    11 months 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.

»
11 months 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.

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

how to solve d?

  • »
    »
    11 months 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

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

    Similar solution to tfg's Is dp[position of bit (from higher to lower)][number module n][how many ones i've put]. Base case is when pos =  =  - 1, if module is 0, return ones (third dimension). otherwise return 0. transifions is:

    f(p, k, o) = f(p-1, (2^p + k)%n, o+1) + f(p-1, k, o)

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      I am not sure whether i got the question right.I tried two different approaches one similar to osdajigu_. Can't seem to figure out what's wrong .Thanks . Post Edit: Found the issue was taking the wrong modulo number :/

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

How to solve K?

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

    It can be solved by DP. let's focus on minimum expected value, and then its similar for maximum. Be f(mask) = minimum expected value if I have the current mask (1 for available numbers, and 0 otherwise). So, the transition would some something like.

    You have to calculate values of what numbers can I remove such that sum up d, and add that movement to moves[d]. There a few cases to handle, in case you can't make any movement, that will be the base case. Also you have to calculate the probabilitie of get d with 2 dice. For that just do a double nested loop and sum up for i+j, and then divide all (for 2 to 12) by 36.

    Here is the code

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

How to solve E, and B?

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

    E: You have to find the shortest cycle around cell having 'B'. For each cell, consider 2 nodes in the graph, P and Q. Also, consider a line from 'B' to an edge of the grid. For a particular cell, you are on node Q if you have crossed that line an odd number of times in your path. Otherwise, you are on node P. Now, calculate the shortest distance from P to Q for any cell.

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

    problem E can be solved using max-flow(min-cut actually). Lets build the following flow network: for every position on the matrix lets create two nodes(call them entry node and exit node) and add an edge between them with capacity equal to the cost of blocking that position if it has a letter('a', 'b', ...) or INF in case it is the position of 'B' or a dot('.'). The source will be entry node of 'B' and the sink will be an extra node that we will connect with the exit nodes of every position on the borders with capacity equal to INF. Then for every position add an edge between its exit node and the entry nodes of every adjacent position with capacity equal to INF. Then run max-flow algorithm on this graph and that is the answer. What we are actually computing here is the minimum cost to separate the sink from the source(min-cut) which is equivalent to max-flow. The problem is similar to this one http://coj.uci.cu/24h/problem.xhtml?pid=2505 in case you want to practice this approach. Good luck

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

      Nice, thank you

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

      For problem E, why do standard max-flow algorithms (Dinitz and Push-Relabel) run very fast even though the graphs involved have about $$$2nm = 1800$$$ nodes and a similar order of magnitude of edges, while these algorithms take cubic time in the worst case? Is it simply that the test data does not have the worst case, or is there a tighter analysis you can do on grid graphs like these to prove better upper bounds?