Geothermal's blog

By Geothermal, history, 3 weeks ago, In English,

A — Circle

The area of a circle with radius $$$r$$$ is $$$r^2 \pi$$$, while the area of a circle with radius $$$1$$$ is $$$\pi$$$. The answer is thus $$$\frac{r^2 \pi}{\pi} = r^2$$$, so we can simply print $$$r \cdot r$$$.

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


B — Echo

First, the answer is obviously no if $$$N$$$ is odd. Otherwise, we can directly check whether the strings created by the first and last halves of $$$S$$$ are the same. One way to do this is to iterate over all positions $$$i$$$ from $$$0$$$ to $$$\frac{N}{2}-1$$$ (remembering that the positions in a string are zero-indexed) and check whether position $$$i$$$ stores the same character as position $$$i + \frac{N}{2}$$$. If this isn't the case for some $$$i$$$, the answer is no. If, on the other hand, this holds for all $$$i$$$, the answer is yes.

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


C — Average Length

The key to this problem is the C++ STL next_permutation function. (Some other languages may have similar methods; some do not.) If you aren't familiar with this function, running next_permutation(vec.begin(), vec.end()) rearranges the elements in the vector vec into the next lexicographically higher permutation, returning true if this was possible or false if vec is already in its lexicographically highest possible arrangement (which occurs when it is sorted in decreasing order). The function runs in $$$O(N)$$$.

We can use this function to generate all possible permutations of $$$N$$$ elements in $$$O(N \cdot N!)$$$. Then, for each permutation, we can easily compute the distance between each consecutive pair of points and add them to the answer. Finally, we divide the answer by $$$N!$$$ to get our average and print it.

If you're using a language that doesn't support a function like this: first of all, you should probably learn C++, but secondly, there are also other ways to generate the permutations. One fairly simple way to do this is recursive backtracking, storing an array containing the elements used so far in our current permutation and iterating over all possible remaining elements. This can be implemented efficiently, but even an extremely inefficient implementation runs in $$$O(N^3 \cdot N!)$$$, which, given $$$N \leq 8$$$, should run in time.

Runtime: $$$O(N \cdot N!)$$$. Click here for my submission.

Fun fact: There's also an $$$O(N^2)$$$ solution to this problem relying on a slightly more clever insight. Note that element $$$i$$$ will appear immediately before element $$$j$$$ in $$$(N-1)!$$$ of our permutations, since there are $$$N-1$$$ ways to position $$$i$$$ and $$$(N-2)!$$$ ways to arrange the remaining $$$N-2$$$ elements. Thus, we can add the distance from point $$$i$$$ to point $$$j$$$ multiplied by $$$\frac{1}{N}$$$ to our answer, since it will appear in $$$\frac{1}{N}$$$ of our permutations. The total sum over all ordered pairs $$$(i, j)$$$ with $$$i \neq j$$$ is our answer.


D — Knight

First, note that $$$X+Y$$$ must be a multiple of three for any paths to exist, since both of our moves increase the sum of our coordinates by $$$3$$$. If this does not hold, the answer is zero. Then, we must take $$$K = \frac{X+Y}{3}$$$ moves. Suppose that we take $$$N$$$ moves that increase our coordinates by $$$(2, 1)$$$ and $$$K-N$$$ moves that increase our position by $$$(1, 2)$$$. Then, in order to reach $$$X$$$ as our x-coordinate, we must have that $$$2N + K-N = X$$$, so $$$N = X - K$$$. Then, we must take $$$K - N$$$ moves that increase our position by $$$(2, 1)$$$. Note that if $$$X-K$$$ or $$$2K-X$$$ is less than zero, we obviously cannot make a negative number of moves in one direction, so our answer is zero. (This will occur if one of $$$X$$$ and $$$Y$$$ is more than double the other.)

Now, note that the order of our moves doesn't affect our final outcome. Thus, we need to make $$$K$$$ moves, of which $$$N$$$ are one type and $$$K-N$$$ are the other. The number of ways to do this is simply $$$\dbinom{K}{N}$$$, or, in terms of our original variables, $$$\dbinom{\frac{X+Y}{3}}{\frac{2X-Y}{3}}$$$, which is our answer. The choose function can be computed in $$$O(X+Y)$$$.

Runtime: $$$O(X+Y)$$$. Click here for my submission. The logic I used is slightly different from what was described here, but it is ultimately equivalent to this solution.


E — All-you-can-eat

We employ dynamic programming. One key insight here is that the timing condition is equivalent to eating some dishes that take a total of no longer than $$$T-1$$$ minutes, followed by one final dish whose time constraint doesn't matter.

Let $$$dp[i][j][k]$$$ be the greatest happiness we can achieve if we've eaten dishes taking a total of $$$i$$$ minutes to consume and we've taken some subset of the first $$$j$$$ dishes. $$$k$$$ is $$$1$$$ if we've already taken a dish and ignored its time constraint and $$$0$$$ if not. Then, we can transition from $$$dp[i][j][k]$$$ to $$$dp[i+A_i][j+1][k]$$$ or, if $$$k = 0$$$, to $$$dp[i][j+1][1]$$$, and add $$$B_i$$$ happiness in the process. Additionally, since we can waste time, skip a dish, or not bother to eat an extra dish with no cost, we can also transition to $$$dp[i+1][j][k]$$$, $$$dp[i][j+1][k]$$$, or $$$dp[i][j][k+1]$$$ with no happiness increase. Of course, each $$$dp$$$ value should be the maximum possible over all ways to transition to it.

From here, our answer is $$$dp[T-1][N-1][1].$$$

Runtime: $$$O(N^2)$$$, as we have $$$O(N^2)$$$ states and $$$O(1)$$$ transitions in our DP table. Click here for my submission. Note that I used a 2D DP table storing rows corresponding to $$$i$$$ and $$$k$$$. My loop iterating over $$$x$$$ corresponds to $$$j$$$ in this table.


F — Laminate

Again, we use dynamic programming. Let $$$dp[i][j]$$$ be the minimum cost of painting the first $$$i$$$ columns given that we've changed $$$H_i$$$ for $$$j$$$ of them, given that column $$$i$$$ has not had its $$$H_i$$$ changed.

Let's figure out the transitions. Suppose we want to reach $$$dp[i][j]$$$, and the last $$$k$$$ columns before column $$$i$$$ will have their heights changed. In this case, our last painted column is $$$i-k-1$$$, so our previous state was $$$dp[i-k-1][j-k]$$$. Now, if the height of column $$$i$$$ is less than or equal to the height of $$$i-k-1$$$, we can set the height of all adjusted columns in the middle to the height of column $$$i$$$ and then paint all of these columns using some of the same strokes we used for column $$$i-k-1$$$, so the cost of this transition is zero. Otherwise, we can use $$$H_{i-k-1}$$$ strokes to start painting column $$$i$$$ but will need $$$H_i - H_{i-k-1}$$$ more to finish, so this is the cost of our transition.

There are several ways to compute the final answer from this DP table, though the constraint that column $$$i$$$ must not have had its height modified is bothersome since it could be that the best solution involves modifying the last column's height. Probably the easiest way to get around this is to add an extra column with $$$H_i = 0$$$ at the end--given our cost scheme, this will never increase the height, nor will it be advantageous to change the height of this column. Then, our answer is $$$dp[N][K].$$$

Runtime: $$$O(N^2K)$$$, since each of our states has $$$O(N)$$$ transitions. Click here for my submission.


Feel free to post below if you have any questions or comments.

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

»
3 weeks ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

Different explanation of the same $$$\mathcal{O}(N^2)$$$ solution to problem C:

The expected value of any given step is

$$$\displaystyle\frac{1}{\binom{n}{2}}\sum_{i < j} \mathrm{dist}(i,j)$$$

The expected value of $$$N-1$$$ steps is this multiplied by $$$N-1$$$, by linearity of expectation.

The algorithm/code is identical, just a different way of thinking about it in case it helps anyone.

Sample code
  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Can you clarify, how do you define 'step' in your explaination?
    Easiest way I can think of this solution in O(N^2) approach is say we have (d1,d2,d3) then any pair (di, dj) will occur in total of (N-1)!. Since (dj, di) is same as (di, dj), we can club to get 2*(N-1)!. Hence total is 2*(N-1)! * (Sum of distance of any pair), which gets divided over N! to take average.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      By "step", I simply mean one edge within the final path. The expected value is uniform over all pairs of towns, and the same for each step (whether it's first or second or last), so we sum the distances of all pairs of towns and divide by the number of pairs ($$$n$$$ choose $$$2$$$).

      The final path has $$$n-1$$$ edges, so we multiply by $$$n-1$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me what is wrong in this logic for E problem. submission. Thanks in advance.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to implement the choose function in O(X+Y) in problem D ?

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

    To compute $$$\dbinom{A}{B}$$$, compute $$$A!$$$, $$$B!$$$, and $$$(A-B)!$$$. Then, using binary exponentiation, compute the modular inverses of $$$B!$$$ and $$$(A-B)!$$$, after which our choose function is $$$A! \cdot B!^{-1} \cdot (A-B)!^{-1}.$$$

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for problem C : Mycode

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

Here are some alternate ways of thinking / implementation tricks. These won't really change the solutions or runtimes.

Problem E: You can eliminate $$$k$$$ from the DP by first sorting the dishes in order of increasing time to eat. Then when you choose some subset of dishes to eat, the last dish is always the one that should go over.

Problem F: Another way to think about the process of changing a column's height is just removing it. This results in the same DP, but I found it easier to think about this way.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    In problem E I had thought about the sorting of dishes just like we do in exchange arguments dp. Then I apply standard knapsack type dp considering time as total weight and happiness as values but I'm going somewhere wrong. Can you plz help? Submission

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone tell me what's wrong with my code here? It gives me compilation error and I don't know why?

#include <bits/stdc++.h>
using namespace std;
 
struct point{
    double x, y;
};
 
double distance(double x1, double y1, double x2, double y2){
    double ans = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    return ans;
}
 
int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<point> p(n);
    for(int i = 0; i < n; ++i)
        cin >> p[i].x >> p[i].y;
    
    double long sum = 0;
    int counter = 0;
    do{
        for(int i = 0; i < n - 1; ++i)
            sum += distance(p[i].x, p[i].y, p[i + 1].x, p[i + 1].y);
        counter++;
    }while(next_permutation(p.begin(), p.end()));    
    cout << fixed << setprecision(9) << sum * 1.0 / counter << '\n';
    return 0;
}
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    next_permutation requires the < operator in order to work. (So you would have to implement it for the struct point.)

    note: that will still not give you AC (in order to go through all permutation, your vector needs to be sorted)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But shouldn't next_permutation give me all the possible permutations for the vector? What's the purpose of sorting it before that?

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

    Note that the nex_permutation gives next possible lexicographical combination,.... we need to count all N! cases which of courses your solution will not count(except one case ,when your array will already be sorted)...for example let P : 1 3 2 and now you apply while(next_permutation(p.begin(), p.end())); it will stop after 213,231,312,321which is "next" 4 possible combination but not all 3!=6 combination. Thus it is better to apply next_permutation thing on the index of array(already sorted) https://atcoder.jp/contests/abc145/submissions/8498789

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Task E can be solved using the idea of knapsack. But for each sweat you have to update dp state for time a[i] to T-1+a[i]. https://atcoder.jp/contests/abc145/submissions/8487772

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

    Yep, I solved it with a similar approach.

    Here's my easy to understand code for reference.

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

    Why do we need to sort vp? Edit: I understood now.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D during the contest I was able to figure out the simultaneous equation just wasn't sure how to count the number of ways,.....I am still not sure how kCn will give the number of ways..can someone can explain in detail

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain where my implementation of the tutorial goes wrong? Also I don't really get how does the reduction from 3d dp to 2d dp work. Any help would be really appreciated.

Code: https://ideone.com/kpY1HJ