Ninjo's blog

By Ninjo, 2 years ago, In English

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?

Read more »

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

By Ninjo, 4 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(codeforcesgreendot.com/dashboard) created!

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

poll: [let me know your opinion about creating new mobile app]

According to my poll ^ about creating codeforces green dot mobile app.
Result: (78% Yes | 22% No) total: 76 voters



[pending] App on Google play


[STATISTICS]
92 registered users
608 likes on Facebook
107 followers on Twitter

Join our NEW #telegram channel to get updates instantly!

telegram: https://t.me/CfGreenDot


[UPD]: >> web domain has changed ".com" instead of ".cf" http://codeforcesgreendot.com

Follow app on FacebookTwitter
contact developer khaledalam.net

With best regards, Khaled

Read more »

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