Блог пользователя NeverSayNever

HACK 101 Problem
Автор NeverSayNever, 12 лет назад, По-английски

Hello all,

I am trying to solve this problem from Hack 101 Hackerrank .

https://www.hackerrank.com/contests/101hack20/challenges/superpowers

I was not able to click any other solution so i applied brute force and got TLE for some file then i decided to open some accepted solution and find a number of interesting code.

Here are the link to those solution.

Roman Rubanenko submission's : extremely small code (may be idea is very big) c++ code http://ideone.com/MI4uUA

python code link http://ideone.com/RhYWli

Surprise to see such codes..

Can anybody of you elaborate the idea behind these submission.. This will make me learn a lot..

Thanx in advance ..

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +10 Проголосовать: не нравится

In order to understand idea of Rubanenko — take a look at values of ans at first few iterations. 

ans[0]=A=A^1;
ans[1]=ans[0]*ans[0]=A^1*A^1=A^2=A^(2^1);
ans[2]=ans[1]*ans[1]=A^2*A^2=A^4=A^(2^2);
ans[3]=ans[2]*ans[2]=A^4*A^4=A^8=A^(2^3);
ans[4]=ans[3]*ans[3]=A^8*A^8=A^16=A^(2^4);
...

As you can see,ans[i]=A^(2^i); and Rubanenko just set A=2.

→ Ответить