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

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

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
  • Проголосовать: не нравится

»
10 лет назад, # |
← 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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

    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

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    @LeBron Thanx

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить