Ninjo's blog

By Ninjo, 4 years ago, In English

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: i got TLE on second test set N < $$$10^9$$$

When i try to generate A and B randomly: 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 ^

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?

Full text and comments »

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

By Ninjo, 6 years ago, In English

Hello, Codeforces!
Today i want to introduce Codeforces Green Dot google chrome extension. Check your friends list status and submissions fast and easily and be up to date with platform blog actions.

New web app( created!

you must register here to use app. to get your API keys from here

[UPD]: Create "Recent Actions Twitter Bot" @CfGreenDot

Follow app on FacebookTwitter

Full text and comments »

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