Lewin's blog

2018-2019 ACM-ICPC Pacific Northwest Regional Contest
By Lewin, history, 6 years 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

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

How to solve I and M?

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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).

      → Reply
    • »
      »
      »
      6 years 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?

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
  • »
    »
    6 years 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.

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

      I understood the Convex_combination and that its solution lies inside the convex hull of the points but, why is it like that? Why must the $$$x_i$$$ sum to 1?

      And what is the intuition behind this: $$$(h*C/c,p*C/c)$$$ ?

      Thank you!

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

        That transformation is needed to make taking an object proportional. If it has weight 0 <= x <= 1, then you use x from your total "funds" (I don't remember the exactly story in the problem). Since not spending all the money isn't optimal you'll always spend everything so the sum is 1.

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

          It's much clearer now, thank you for the quick response!

          → Reply
»
6 years 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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve d?

→ Reply
  • »
    »
    6 years 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

    → Reply
  • »
    »
    6 years 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)

    → Reply
    • »
      »
      »
      6 years 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
      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve K?

→ Reply
  • »
    »
    6 years 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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E, and B?

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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

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

      Nice, thank you

      → Reply
    • »
      »
      »
      6 years 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?

      → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the time complexity of B? My time complexity is O(10^9) using prime factorization and inclusion-exclusion and which is I think give TLE. So how to solve this problem? Thanks in Advance.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    I assume that you mean your solution is $$$O(\max(a,b,c,d))$$$ and just iterates up to $$$10^7$$$, $$$10^9$$$ would TLE.

    I never actually figured out why this worked, but during the contest I just observe that the inclusion exclusion only took on values of 0 or 1 and ran fast enough when I put the answers in a char array (but 2-4x slower in an int array)

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

    You can also solve the problem in $$$O(n)$$$ with Möbius inversion and a linear-time sieve.

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

I'm still stuck at F_Rectangles even after reading the editorial. Here it is.

I'm struggling with the lazy propagation part, and dividing the regions etc.. Since I know how to do the standard version without the odd property.

Here is the problem statement:

Spoiler

Any ideas anyone?

→ Reply