Google Kick Start 2021 — round E

3 years ago, # |

Solution for the problem D "Increasing Sequence Card Game" test set 3 (N > 10^6): https://www.quora.com/What-is-the-sum-of-the-series-1+-1-2-+-1-3-+-1-4-+-1-5-up-to-infinity-How-can-it-be-calculated

It was by far the easiest problem of them all. Which awarded the largest amount of points.

→ Reply

YPK

3 years ago, # ^ |

Can you explain how the answer is of that form?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Just implemented a simple straightforward bruteforce solution for N <= 10 and looked at the results:

Spoiler

Case #1: 1.0000000000
Case #2: 1.5000000000
Case #3: 1.8333333333
Case #4: 2.0833333333
Case #5: 2.2833333333
Case #6: 2.4500000000
Case #7: 2.5928571429
Case #8: 2.7178571429
Case #9: 2.8289682540
Case #10: 2.9289682540

Based on these results, it's obvious that the answer is 1 + 1/2 + 1/3 + ... + 1/N. And this makes it a pure math problem, which is generic enough to be searchable on the Internet.

→ Reply

darkcoder123

3 years ago, # ^ |

Wow, really need this kind of observation skills by looking at result. :))

→ Reply

3 years ago, # ^ |

It's not just looking at the result alone. For N=1, the answer is 1. Then if we add one more card, it can go either to one side of the deck or to the other side and thus adds 1/2 to the expected score, making the formula 1 + 1/2. Next looking at N=3, we can see that ~0.3333333333 gets added to the answer and makes it 1 + 1/2 + 1/3. Further checking cases N=4,5,6,... confirms that this pattern continues. The top rated answer from quora provided the $$$H_n=ln(n)+0.5772156649$$$ approximation for large $$$n$$$ and it does the job. Here's a link to my submissions for this contest.

Looking at the editorial, appears that the expected solution was supposed to be a bit more complicated.

→ Reply

LOVELY_BOY_

3 years ago, # ^ |

How to solve problem A ?

→ Reply

3 years ago, # ^ |

Just open one of the solution. You’ll learn more than from pure answer. If you’ve got WA its probably because for string like ‘abc’ you are doing ‘ba’ and can’t put ‘c’.

→ Reply

Resende

3 years ago, # ^ |

It's always dangerous to say that something is obvious. You should try to prove if you think you found a pattern. For this problem I think there may be a simple proof by induction. I demonstrated in other way by first solving test set2 with dp and then replacing the dp definition of the previous states.

As an example of how this kind of thinking may mislead you, I give you the following classical problem find the Maximal number of regions obtained by joining n points around a circle by straight lines. The sequence starts with 1, 2, 4, 8, 16, ... So it's obvious that the next number is 32? But it's actually 31 A000127.

Many times the attempt to prove that your assumption is true may lead you discover that you were wrong and save you time implementing the wrong solution.

→ Reply

Into_Your_Arms

3 years ago, # ^ |

← Rev. 2 →

+10

Using Errichto "contribution Technique" — The $$$i^{th}$$$ card from the top will have contribution in the final answer $$$<=>$$$ all previous card appeared are smaller than it. and probability of this is $$$1/(n-i+1)$$$. So you just need to do $$$\sum_{I=1}^{i=n}1/i$$$

Spoiler

→ Reply

b4nanacream

3 years ago, # ^ |

-11

TIME LIMIT EXCEDED

→ Reply

uux

3 years ago, # ^ |

That's why for bigger N, you do as explained in this comment.

→ Reply

darkcoder123

3 years ago, # ^ |

Is there a blog or video for that of errichto, if yes please share link.

→ Reply

3 years ago, # ^ |

https://mirror.codeforces.com/blog/entry/62690 I wish I had seen the complete video when I first saw the post :(

→ Reply

darshancool25

3 years ago, # ^ |

Easy for those who could find the appropriate link by googling...nightmare for others !!

→ Reply

3 years ago, # ^ |

Not really. You could code O(n^2) solution for test n = 10. And observe that dp[i] depends on sum of dp[1:n-1] and you could precalculate with accumulator. This would make your solution linear and n = 1e6 would pass.

→ Reply

darshancool25

3 years ago, # ^ |

ik...I was talking about Test set 3

→ Reply

aniket_lakhotia

3 years ago, # |

I tried doing problem C(Palindromic Crossword) using some dfs kind algorithm(I stored nearest blockages for each row and column) and kept getting runtime error, can someone point out the mistake in my logic? Thanks link: https://pastebin.com/Xx3KHbGU

→ Reply

3 years ago, # ^ |

Try to run it for a 1000x1000 grid filled with '.'

→ Reply

aniket_lakhotia

3 years ago, # ^ |

Thanks man, turns out I was not setting the columns in result grid and was trying to access columns without setting them, it was a stupid mistake :(

→ Reply

TimeTraveler

3 years ago, # ^ |

I did that too. I calculated horizontal and vertical palindrome equivalent positions of each non blocked cell.

Spoiler


#include <bits/stdc++.h>
#define int int64_t
using namespace std;

const int N = 1e3+7;
int H[N][N], V[N][N];
bool vis[N][N];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;	cin >> t;
    for(int _ = 1; _ <= t; _ ++) {
        cout << "Case #" << _ << ": ";
        int n, m;   cin >> n >> m;
        string s[n + 1];
        for(int i = 0; i < n; i++)
            cin >> s[i];
        for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            H[i][j] = V[i][j] = -1;
            vis[i][j] = false;
        }
        
        s[n] = string(m + 1, '#');
        for(int i = 0; i < n; i++)
        {
            s[i] += '#';
            int prev = 0;
            for(int j = 0; j <= m; j++) if(s[i][j] == '#')
            {
                for(int k = prev; k < j; k++)
                    H[i][k] = j - k + prev - 1;
                prev = j + 1;
            }
        }
        for(int j = 0; j < m; j++)
        {
            int prev = 0;
            for(int i = 0; i <= n; i++) if(s[i][j] == '#')
            {
                for(int k = prev; k < i; k++)
                    V[k][j] = i - k + prev - 1;
                prev = i + 1;
            }
        }

        int ans = 0;

        function<void(int, int)> dfs = [&](int i, int j)
        {
            vis[i][j] = true;
            if(H[i][j] != -1 and !vis[i][H[i][j]])
            {
                if(s[i][H[i][j]] == '.')
                {
                    ans++;
                    s[i][H[i][j]] = s[i][j];
                }
                dfs(i, H[i][j]);
            }
            if(V[i][j] != -1 and !vis[V[i][j]][j])
            {
                if(s[V[i][j]][j] == '.')
                {
                    ans++;
                    s[V[i][j]][j] = s[i][j];
                }
                dfs(V[i][j], j);
            }
        };
        for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        if(isalpha(s[i][j]) and !vis[i][j])
        {
            dfs(i, j);
        }

        cout << ans << '\n';
        for(int i = 0; i < n; i++) {
            s[i].pop_back();
            cout << s[i] << '\n';
        }
    }
}

→ Reply

ijxjdjd

3 years ago, # |

+30

I have a much different solution to $$$D$$$ that allows for a more general statement that makes the problem slightly more interesting (and definitely harder).

Using one-indexing, if we try to find the number of times card $$$i$$$ is at position $$$j$$$ and ends up in the final hand, we find that this number is $$${i-1 \choose j-1}(j-1)! (N-j)!$$$. In short, this is choosing $$$j$$$ cards lower than $$$i$$$ and placing them in front of position $$$j$$$, then permuting everything but card $$$i$$$ and position $$$j$$$. To find the total number of times a single card $$$i$$$ is in the final hand, sum over all positions $$$j$$$ and expand. This nets you $$$\sum_{j \le i} \frac{(i-1)!}{(i-j)!(j-1)!} (j-1)! (N-j)!$$$. Simplify to get $$$(i-1)!\sum_{j \le i} \frac{(N-j)!}{(i-j)!}$$$. Notice that the subtraction of numerator and denominator removes $$$j$$$ from the summation, so we can try turning the fraction into a binomial coefficient. $$$(i-1)! (N-i)! \sum_{j \le i} \frac{(N-j)!}{(i-j)! (N-i)!} \rightarrow (i-1)! (N-i)! \sum_{j \le i} {N-j \choose i-j} \rightarrow (i-1)! (N-i)! {N \choose i-1}$$$ where the last transformation is by a binomial identity. Simplifying this expression trivially we, we find that the contribution is exactly $$$\frac{N!}{N-i+1}$$$, but the entire expression will be divided by $$$N!$$$ so the contribution to the expected value of card $$$i$$$ is exactly $$$\frac{1}{N-i+1}$$$

The problem could have given a set $$$S$$$ and asked to find the expected value of the intersection between the final hand and $$$S$$$ or, if you want to keep the $$$H_n$$$ approximation, you can ask for the intersection between the final hand and all cards not in $$$S$$$. Even so, it's easily bruteforceable if one knows about the linearity of expectation, but the statement no longer screams to be brute forced.

→ Reply

Into_Your_Arms

3 years ago, # |

for last problem Why I was getting WA for 3rd test case when I was trying to solve this recurrence $$$f(n)=f(n-1)+1/n$$$ by matrix exponentiation.

→ Reply

Errichto

3 years ago, # ^ |

+18

Matrix expo allows for adding $$$constant \cdot n$$$, not $$$ constant / n$$$. Either you made a breakthrough or your matrix doesn't make sense :D

→ Reply

Into_Your_Arms

3 years ago, # ^ |

← Rev. 2 →

-7

Thanks! I was not aware of it and wasted hours. Can you please provide any reference or some reason for "why it doesn't work with double?"

→ Reply

Errichto

3 years ago, # ^ |

It works with doubles. You can add 0.3*n. It doesn't support division. Because how you would do that? You choose matrix coefficients and they get multiplied by something, not divided.

→ Reply

b4nanacream

3 years ago, # |

+15

for me A was harder than D.

→ Reply

mychecksdead

3 years ago, # |

← Rev. 2 →

+19

For D problem, I found a solution easier than analysis solution. Suppose that we found answer for n-1 (base case is n=1 which is 1). Think all of the permutations from n-1, increase every number with 1. Now, we should just insert 1 into somewhere into them, there are two cases: 1. Insert 1 at the beginning, it gives us (n-1)!, because there are (n-1)! permutations. 2. Insert 1 at anywhere expect the beginning, it won't be included in any increasing subsequence. So it gives us for every answer from n-1, (n-1) times of it + from the first case there is 1 more f(n-1) too. So f(n)/n! = (f(n-1) / (n-1)!) * n + (n-1)! / n! = f(n-1) + 1/n. Then for n <= 1e6, brute force, otherwise use formula for harmonic sums, which is f(n) = ln(n + 1) + (Euler–Mascheroni constant =~ 0.5772). (edit: fixed plagiarism)

→ Reply

codicon

3 years ago, # ^ |

This is genius. Thanks :)

→ Reply

parth_kabra

3 years ago, # |

It was a nice round! I secured rank 1085 in it

→ Reply

wowsuchempty

3 years ago, # |

Is C some form of a well-known problem ? I noticed a lot of people do C but fail at D.

→ Reply

3 years ago, # ^ |

C was just some recursion .

→ Reply

ankan2526

3 years ago, # ^ |

← Rev. 2 →

your rank is just +3 of mine :)

→ Reply

granth.dhir

3 years ago, # ^ |

Any tips for a beginner, it was my first time..

→ Reply

3 years ago, # ^ |

Try CSES problemset and Atcoder Beginner Contest , your skills will improve exponentially with time.

→ Reply

granth.dhir

3 years ago, # ^ |

What level of maths is needed to aid a solution?

→ Reply

3 years ago, # ^ |

Upto my level , Not much

→ Reply

3 years ago, # ^ |

Yeah , It wasn't a good Kickstart for me , :( , but still it's fine .

→ Reply

3 years ago, # ^ |

Just as the editorial explains in the "Test Set 2" part, it's a graph problem. I solved it by constructing an adjacency list and then doing DFS. Relatively few participants submitted a partial solution only for Test Set 1 and this makes sense, because it's actually easier to treat it as a graph rather than doing something ad-hoc.

I think that Codeforces offers awfully few graph problems among Div2A-Div2D, so I recommend participating in AtCoder beginner/regular contests to improve your skills at solving this stuff.

→ Reply

3 years ago, # ^ |

Why ad-hoc? I don't think a lot of people solved it as a graph problem. It's a usual board/matrix problem which is more common/simple. You can save all # indexes in a row/column and traverse them with your board and get next jump in constant time or make [up/down/left/right]-matrices, or [horizontal/vertical]-matrices and do the same. Bfs — or — dfs, doesn't really matter. This approaches seem more common and widely used to me then graphes, not something special or ad-hoc.

→ Reply

3 years ago, # ^ |

I checked your solution and it looks like you essentially used a fancy problem-specific data structure for storing and retrieving information about graph edges instead of something more conventional. I used a plain and boring adjacency list in my solution. The other differences are pretty much cosmetic/insignificant. As for which approach is more simple, I would say that mine probably better followed the teakettle principle and it was a more reliable way to get a guaranteed result (even at the cost of more lines of code).

In my opinion, we both solved it as a graph problem. You may disagree, but that's similar to saying "it's not a graph, it's Takahashi's kingdom with towns and roads". Graph is a useful abstraction with useful properties and useful algorithms. Sometimes graph edges are given to us directly as a part of input data. But in this particular problem C, it was a graph with a little bit of disguise.

→ Reply