Google's Kick Start 2020 Round B

5 лет назад, # |

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)

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

+13

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

→ Ответить

5 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

toxic_hack

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

+19

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

→ Ответить

5 лет назад, # ^ |

i guess for nCr you typed rCn

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

code

double find_ways(int n,int m){
   num.clear();den.clear();
   double ret = 1;
   int manhattan = n-1 + m-1;
   int limit = 1e5 + 10;
   rep(i,1,m+n-2) num.emplace_back(i);
   rep(i,1,m-1) den.emplace_back(i);
   rep(i,1,n-1) den.emplace_back(i);
   rep(i,1,manhattan) den.emplace_back(2);
   int num_ptr =  0, den_ptr = 0;
   while(num_ptr < num.size() and den_ptr < den.size()){
      if(ret < limit) ret *= num[num_ptr++];
      else ret/= den[den_ptr++];
   }
   while(num_ptr <  num.size()) ret *= num[num_ptr++];
   while(den_ptr < den.size()) ret/= den[den_ptr++];
   return ret;
}

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.

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

shenqi16

5 лет назад, # ^ |

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);
};

→ Ответить

aryanc403

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

ninetyone

5 лет назад, # ^ |

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

→ Ответить

bansals888

5 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

aryanc403

5 лет назад, # ^ |

+12

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

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

sanjeethboddi

5 лет назад, # ^ |

What is FFT?

→ Ответить

5 лет назад, # ^ |

Fast Fourier Transform

→ Ответить

mdallrosa

5 лет назад, # |

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?

→ Ответить

Bl0ck_M0mb0

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

mdallrosa

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

5 лет назад, # |

How to Solve D.

→ Ответить

rahulpkvij

5 лет назад, # |

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

→ Ответить

PRESS_F_2_PAY_RESPECT

5 лет назад, # |

How to solve C without recursion using stack ?

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

my code i solved using stack.

→ Ответить

PRESS_F_2_PAY_RESPECT

5 лет назад, # ^ |

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

→ Ответить