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.
Good luck to all :))) Wish y'all good scores!
Giving a well-known problem as C!? Kickstarts used to be much much better than this.
Can you elaborate how that problem was well known?
It was directly this problem. With 180k accepted submissions I'd say it's pretty well known.
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.
Overflow inside the loop. Take mod after every step instead of taking mod in the end.
hey can you tell me what's wrong in my solution. my code
10e9 is 10^10
Thank's dush1729.
How to solve D(last problem) without overflow??
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)
The probability to reach $$$(x,y)$$$ is $$$\dfrac{C^{x-1}_{x+y-2}}{2^{x+y-2}}(x < w, y < h)$$$
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.
How to calculate this probability for the cells that are in the last column or the last row?
If it's in the last column, the probability is $$$p(x, y) = p(x, y - 1) + p(x - 1, y) / 2$$$
i guess for nCr you typed rCn
Sorry, in Vietnam, $$$C^r_n = C(n, r) = (^n_r) = nCr$$$
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.
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.
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?
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.
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
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.
Can you elaborate how did you used fft?
Btw Neal's fft is fastest I'm aware of .
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.
What is FFT?
Fast Fourier Transform
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?
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.
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.
How to Solve D.
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
How to solve C without recursion using stack ?
my code i solved using stack.
The link doesn't show your code:(. Can you provide ideone link please? Sorry for my bad English :(
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.
darkshadows it is better if you post a day before. I mean every one is not expected to be on codeforces for 24*7.
I was getting WA with this code https://pastebin.com/06caGcn4 for 1st problem of kickstart round A. After changing the if condition from
to
answer came right. I am confused about this. Can anyone provide some edge case that will fail in initial if condition?
@darkshadows
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.
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.
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).
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!
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
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.
D was really nice
Here a stack approach of C with explanation if anyone is interested Here