Motivation:
In google code jam 2019, in the qualification round something interesting happens with me.
The first problem Foregone-Solution, simple problem: given number N and want you to print two numbers A and B such that A+B = N, and neither A nor B contains any digit that is a 4.
We have 3 test sets:
1 < N < $$$10^5$$$
1 < N < $$$10^9$$$
1 < N < $$$10^{100}$$$
Numerical implementation solution for the first 2 test sets: https://ideone.com/MZwocZ i got TLE on second test set N < $$$10^9$$$
When i try to generate A and B randomly: https://ideone.com/LUFyhI i got AC (can anyone explain why that happens)
yes i know it should be solved using string instead but i'm talking about this case ^
Topic:
That makes me wonder, we use algorithms to get better, faster and optimal solutions for example if we have N elements with for example binary search we can find any element in the best case in 1 step and in the worst case in ($$$lg N$$$) steps
Well but the question is, if we search for element randomly is not possible to get element in just 1 step also or less than ($$$lg N$$$) steps or maybe in N steps
why we do not use both randomization and binary search for example $$$\frac{(lg N)}{2}$$$ steps use randomization and $$$\frac{(lg N)}{2}$$$ steps use binary search Or why not use 1 step randomization, 1 step binary search, 1 step randomization, 1 step binary search and so on..
The answer is because we maybe can’t find the number in those ($$$lg N$$$) steps or we maybe need more than ($$$lg N$$$) steps to find the number.
Well but we can during randomization steps update interval for binary search and during binary search update interval for randomization. which will decrease searching space and increase the probability of finding our target fast.. example
The idea i want to discuss: is it better to use randomization before/during performing some algorithms or not?
Codeforces Green Dot
