Geothermal's blog

By Geothermal, history, 4 years ago, In English

A — Determinant

Just perform the requested computation. There really isn't much to do here.

Time Complexity: $$$O(1).$$$ Click here for my submission.


B — Quizzes

A simple brute-force simulation works here. Iterate over the characters of $$$S$$$ from left to right, adding one to the answer if the current character is an o and subtracting one if it's an x (while ensuring that the score never drops below zero).

Time Complexity: $$$O(N).$$$ Click here for my submission.


C — Super Ryuma

The key observation is that the answer will always be at most three. We will provide a constructive proof. Suppose that we want to go from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$. In our first move, we move to any point $$$(x_3, y_3)$$$ such that $$$x_3 + y_3$$$ has the same parity as $$$x_2 - y_2.$$$ Then, we will finish with two diagonal moves. We want to construct a point on one diagonal containing $$$(x_3, y_3)$$$ and another containing $$$(x_2, y_2).$$$ Thus, we seek a point $$$(x_4, y_4)$$$ with $$$x_4 + y_4 = x_3 + y_3$$$ and $$$x_4 - y_4 = x_2 - y_2.$$$ Some quick algebra confirms that this system has a solution as long as $$$x_3 + y_3$$$ and $$$x_2 - y_2$$$ have the same parity. So, we can move from $$$(x_1, y_1)$$$ to $$$(x_3, y_4)$$$ to $$$(x_4, y_4)$$$ to $$$(x_2, y_2)$$$, as desired.

Now, we can do casework to figure out when we can finish the problem in fewer moves. Obviously, a zero-move solution exists only if the two points are equal. We can use the described conditions to determine whether a one-move solution exists. A two-move solution exists by similar logic to the above if $$$x_1 + y_1$$$ has the same parity as $$$x_2 - y_2.$$$ Otherwise, a solution consisting of two diagonal moves cannot exist (since moves along diagonals maintain the parity of $$$x+y$$$), so we instead brute-force over all possible moves to cells within three units and check if a one-move solution exists starting at any of those points. If so, then we have a two-move solution. Otherwise, we've exhausted all possibilities, at which point we know that three moves is the best possible solution.

Time Complexity: $$$O(1).$$$ Click here for my submission.


D — Increment of Coins

We use Dynamic Programming. Let $$$dp_{ijk}$$$ be the expected number of operations necessary, supposing that we start with $$$i$$$ gold coins, $$$j$$$ silver coins, and $$$k$$$ gold coins. Then, if $$$i, j,$$$ or $$$k$$$ equals $$$100$$$, we know $$$dp_{ijk} = 0.$$$ Otherwise, we have

$$$dp_{ijk} = 1 + \frac{i}{i+j+k} dp_{(i+1)jk} + \frac{j}{i+j+k} dp_{i(j+1)k} + \frac{k}{i+j+k} dp_{ij(k+1}.$$$

Then, our answer is $$$dp_{ABC}.$$$

Time Complexity: $$$O(N^3),$$$ where $$$N$$$ is the number of coins needed to end the game. Click here for my submission.


E — Third Avenue

We represent this problem as a graph. First, add an edge between every two vertices adjacent in the grid. Then, we might be tempted to add edges between every pair of vertices marked with the same letter, but this could result in $$$O(N^2M^2)$$$ edges in the worst case. So, instead, we create a new helper vertex for each letter. Then, every cell marked with a letter has an edge of length zero to its letter's helper vertex, and each letter's helper vertex has an edge of length one to each vertex marked with that letter. This ensures that each vertex has a path of length one to each other vertex marked with the same letter while creating just $$$O(NM)$$$ edges in the graph.

Now, what's left is a fairly simple 0-1 BFS problem. There are a number of ways to implement this; I think the easiest is probably to use a deque, pushing vertices reached from an edge of length $$$0$$$ to the front of the deque and edges of length $$$1$$$ to the back. (This ensures that the crucial property that we visit vertices in increasing order of distance is maintained.)

Time Complexity: $$$O(NM).$$$ Click here for my submission.


F — Programming Contest

We use a meet-in-the-middle approach. Split the array $$$A$$$ into two halves. Then, construct sets of all total times that can be constructed by solving some set of the problems within each half-array. (There will be $$$2^{N/2}$$$ elements in each set.)

For each element $$$X$$$ of the first set, find the greatest element of the second set less than or equal to $$$T - X$$$, and let this element be $$$Y$$$. Note that $$$Y$$$ is the maximum amount of time we can spend on problems from the second half-array, given that we spend $$$X$$$ minutes on problems from the first half-array. Then, our answer is the maximum value of $$$X+Y$$$ over all possible choices of $$$X$$$.

Time Complexity: $$$O(N 2^{N/2}).$$$ Click here for my submission.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you for the tutorial Geothermal. Can you please explain the problem D mathematically? I mean i want to know how you understood it was a DP in the first place. Thanks in advance :)

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

    Imo, it is experience of having solved many similar problems over the years. Experience cannot be explained, you must experience it yourself, Keep solving problems. Ofcourse, there are small hints there, like $$$N \le 100$$$, which allows $$$O(N^3)$$$ solutions, but those are again, only things you learn after practicing.

    As for the Mathematics behind it, let's denote each state as a tuple of $$$3$$$ numbers, $$$(A,B,C)$$$ which represents your bag containing $$$A$$$ gold coins, $$$B$$$ silver coins, and $$$C$$$ bronze coins. Now, if you are at a state $$$(A,B,C)$$$, you have $$$3$$$ possibilities to move ahead, either you pick a gold coin, the probability of which happening is $$$\dfrac{A}{A+B+C}$$$ and then you reach state $$$(A+1,B,C)$$$, and in doing so you used $$$1$$$ move, or similarly the other cases.

    So, denoting $$$E_{A,B,C}$$$ as the required expected value, we have

    $$$ E_{A,B,C} = \dfrac{A}{A+B+C}(E_{A+1,B,C}+1) + \dfrac{B}{A+B+C}(E_{A,B+1,C}+1) + \dfrac{C}{A+B+C}(E_{A,B,C+1}+1) $$$

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

      Ya, I was also looking at an O(N^3) solution and kind of looked at a DP approach as well but couldn't understand the states and their transition. As you said, i believe Practice is the only way to master that. Also, thank you for taking time to show the math behind the problem, it is really helpful. :)

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

    Essentially, I realized quickly that there were only $$$N^3$$$ states (which, with $$$N=100$$$, is relatively tractable), and that the expected number of operations required from each state can be computed quickly based on answers for a few other configurations. That almost always suggests that a DP approach is the way to go.

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

    There is also a BFS solution..basically they mean same thing though! you can watch Gabriel Wu's solution here..https://www.youtube.com/watch?v=wnYpGt72S0w&t=1119s

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I found this submission for F https://atcoder.jp/contests/abc184/submissions/18333004

It does not use meet-in-the middle, instead does a more or less simple dfs. The exec time is much better. Is this caused by weak tests, or is it really the better aproach?

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

    I'm actually not sure whether this solution can be hacked--I'm fairly certain the asymptotic complexity is still $$$O(N 2^N)$$$, in spite of the optimizations used, but under the limitations given in the problem, I suspect it would be fairly difficult (though perhaps possible) to write a countercase.

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

      TLE's (more than 5 seconds in Atcoder custom invocation, both under GCC and Clang) on the test provided by this generator.

      Of course, this test is not even remotely close to the worst possible, it was just the first thing that came to my mind after reading the submission and it already worked.

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

Thanks for the editorial. In question E, I have used {0,i} for ith helpher vertex (eg for 'a' it will be {0,0}) and then used 0-1 bfs but I am getting WA on only one testcase. I am not able to figure out what's wrong in my code, so please can anyone help me to find out where am I getting wrong ?

My Submission