NeverSayNever's blog

HACK 101 Problem
By NeverSayNever, 10 years ago, In English

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 ..

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

»
10 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    As you can see,ans[i]=a^(2^i)

    Actually, it was said in the statement :D The answer to the question seems to be in your lines above, which show that ans[i] = ans[i - 1]2

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    @LeBron Thanx

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    @LeBron

    Can you also tell me how does that python code works because 2^a really a big number and handling such big number should lead to TLE although i know that time limit for python is relaxed ...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      As python doc says pow(x, y[, z]) is computed more efficiently than pow(x, y) % z #pow

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In python, using the pow(a,b) is equivalent to a ** b then mod c which will easily get TL due to involvement of large numbers but pow(a,b,c) do it in with some constant overhead.

      → Reply