darkshadows's blog

Google's Kick Start 2020 Round B
By darkshadows, history, 4 years ago, In English

Hello again,

Google's Kick Start 2020 season is here! Kick Start hosts online rounds throughout the year, giving participants the opportunity to test and grow their coding abilities while getting a sample of the programming skills needed for a technical career at Google. Top candidates might be invited for interviews.

We have some exciting updates for 2020:

  • We’re removing Hidden Verdict Test Sets. All submissions will receive instant feedback.
  • You'll see an easiest fourth problem added to each round.
  • We have a new scoreboard feature of filtering by location and people you choose to follow!

I invite you to solve some fun and interesting problems on Apr 18 2020, 23:00 UTC (i.e. within next hour or so).

Dashboard can be accessed here during the contest. Problem analyses will be published after the contest.

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

Comments Comments (47)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Good luck to all :))) Wish y'all good scores!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +60 Vote: I do not like it

Giving a well-known problem as C!? Kickstarts used to be much much better than this.

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

    Can you elaborate how that problem was well known?

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

      It was directly this problem. With 180k accepted submissions I'd say it's pretty well known.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, can someone please explain, why my last submission receives WA on TC #2 for Prob 3?

I have attached it below.

EDIT: Figured out the solution, mod when multiplying.

Thanks to all that helped.

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

How to solve D(last problem) without overflow??

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

Did anyone else solved D using FFT ?? I want to know their implementation of FFT. (Yes it was an overkill and took me upto last 2 minutes to optimize)

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

    The probability to reach $$$(x,y)$$$ is $$$\dfrac{C^{x-1}_{x+y-2}}{2^{x+y-2}}(x < w, y < h)$$$

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

      Yes, it was simpler to use combinatorics. But I had no experience of computing large N choose R in doubles so I didnt think that way.

      and even if I find that formula, I wont be sure of precision errors.

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

      How to calculate this probability for the cells that are in the last column or the last row?

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

        If it's in the last column, the probability is $$$p(x, y) = p(x, y - 1) + p(x - 1, y) / 2$$$

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

      i guess for nCr you typed rCn

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

        Sorry, in Vietnam, $$$C^r_n = C(n, r) = (^n_r) = nCr$$$

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it
          code

          i pushed all the required factors to numerator and denomiator array.according to your experience is it ok to use such method for maintaining precision in this type of question, i am taking care of overflow.

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

            I just use logarithms to avoid overflow. I'm not really sure about precision error but i used this technique to AC a problem before. I don't think your method is ok with large m, n.

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

              I used the log transformation just the same as the official analysis. But still troubled with the float number issue. Could you correct my implementation?

              // tb[i]: log2(i!)
vector<double> tb(maxn); 
for (int i = 2; i < maxn; i++) {
    tb[i] = tb[i - 1] + log2(i);
}
// calc C(n,k)/2^n
auto calc = [&tb](int n, int k) {
    return exp2(tb[n] - tb[k] - tb[n - k] - n);
};
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                What is the value of maxn?
                I tried exp2/log2 with double instead of exp and long double in my AC soln. I still got an AC.

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

              Rather than using the logarithms I tried another approach where when computing the probability in linear time I would make sure that it was always less than 1 so that there was never any overflow. But I keep getting wrong answer with this approach. I think this might be due to precision issues but can't understand why

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

      I have a doubt regarding the above formula. Why does a path have a probability equal to 1/(2^(x+y-2)) because when (x+y-2) > min(m,n) then there can be the case that we can go out of the grid by going all Right or all Down. In this case, probability of going in either direction is not 1/2. Am I doing something wrong here? EDIT: I got my mistake. Sorry to bother.

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

    Can you elaborate how did you used fft?
    Btw Neal's fft is fastest I'm aware of .

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

      1) I can compute nth row of probabilities (no restrictions) using FFT. First row is simple.Now polynomial (1+x/2+(x/2)²+...+)/2 computes next row.

      I compute (r+1)th row. Then I sum over 1 to u-1 and each time remove previous term/2 to not overcount. Similarly for (d+1) row.

      2) It seems that implementation above is for Modular field only. I was seeking for doubles.

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

    What is FFT?

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

In the problem Robot Path Decoding we have the following restrictions for each test case set:

Test set 1 The total number of moves the robot will make in a single test case is at most 104.

Test set 2 No additional constraints.

But in the analyses it is written:

Test Set 2 Now it is possible that the number of moves is exponential in the length of the original program. Thus it would be impossible to execute the moves one by one in the given time.

Am i the only one who didn't understand this? Can anyone explain it to me?

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

    Think of WorstCase: 2(2(......(2(E))))...) with length 2000 no of 2's b4 E is (2000-1)/3 since multiplication with power(2,(2000-1)/3) is not possible therefore using modulo property.

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

      I know what he mean by exponential in the length of the original program. I interpreted the text in the wrong way. Because it is written:

      Test set 2 No additional constraints.

      I understood that the test set 2 would have the same contraints as test set 1, because it was not changing them. Thank you.

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

How to Solve D.

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

Can anyone please tell why my code gives WA for test 2 of 3rd problem : https://pastebin.com/3wdiELqp https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83dc

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

How to solve C without recursion using stack ?

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

    my code i solved using stack.

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

      The link doesn't show your code:(. Can you provide ideone link please? Sorry for my bad English :(

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        take a look
        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah great!! I also did it in a similar way but was surprised to see almost everybody use recursion on the 1st and 2nd page.

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

darkshadows it is better if you post a day before. I mean every one is not expected to be on codeforces for 24*7.

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

I was getting WA with this code https://pastebin.com/06caGcn4 for 1st problem of kickstart round A. After changing the if condition from 

if (checkpts[k] > checkpts[k - 1] && checkpts[k] > checkpts[k + 1] && checkpts[k] > checkpts[0] && checkpts[k] > checkpts[n])

to

if (checkpts[k] > checkpts[k - 1] && checkpts[k] > checkpts[k + 1])

answer came right. I am confused about this. Can anyone provide some edge case that will fail in initial if condition?

@darkshadows

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

    Why were you checking if the current value is greater than the first and the last value?

    I don't think you read the problem statement correctly.

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

In the last test case of sample test cases in problem D, how come the answer is 0.3125 I'm getting 0.375

I'm calculating the probability of falling into the hole and subtracting it from 1 to get the probability of success.

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

    You are missing the dependency between the cells in which you are calculating the answer most likely (Both cells are adjacent, so the values of reaching there are inter-dependent).

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

    Hey, I was looking for exactly this approach! Do you mind sharing your solution? I've tried a lot to think but I haven't been able to solve it using this method. The analysis provides the combinations method which is different. It would be of great help!

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can Someone explain me 5 3 1 2 4 2 test case of Last problem of kickstart when i calculate there is only 1 ways to reach from (1,1) to (5,3).right? so answer should be 1

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

    You assume that the robot will always walk along this single available path, but it is not the case since the robot walks randomly.

    The robot starts at cell (1,1). With 50% chance it will either move down and fall into the hole, or move right to cell (1,2). So the probability of reaching (1,2) is 0.5.

    From cell (1,2), again with 50% chance it will either move down and fall into the hole, or move right to cell (1,3). Since the probability of reaching cell (1,2) is 0.5, the probability of reaching (1,3) will be 0.5*0.5=0.25.

    Similarly, the probability of reaching (1,4) is 0.25*0.5=0.125 and the probability of reaching (1,5) is 0.125*0.5=0.0625.

    After reaching cell (1,5) the robot will always move down with 100% probability, so the probability of reaching cell (2,5) is 0.0625*1=0.0625 and the probability of reaching (3,5) is also 0.0625*1=0.0625.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

D was really nice

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

Here a stack approach of C with explanation if anyone is interested Here

→ Reply