SPOTWO - Editorial

shaleen · November 11, 2013, 3:04pm

PROBLEM LINK:

DIFFICULTY:

EASY

PREREQUISITES:

High school maths

PROBLEM:

Calculate (2^N__bin)² % 1000000007 for given N, where N__bin stands for the decimal number encoded by the representation in base 2 of the number N

QUICK EXPLANATION:

Store the binary representation of N as decimal number in appropriate data type(as per language). Use fast exponentiation technique to calculate the result within time limit.

EXPLANATION:

First task is to get binary representation of N as decimal number. The largest value of N is 600000 whose binary representation is 10010010011111000000 which is less than 2^64 but greater than 2^63. For C programmers, unsigned long long is suitable to store this value.

Next task is to calculate (2^N_bin)² % 1000000007 within time limit. This can be achieved using Right-to-left binary method for modular exponentiation.
See mugurelionut’s solution for simple implementation in C/C++

Another simple way of calculating 2ⁿ in log n time is by using exponentiation by squaring. See setter’s solution for a simple function using this technique.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found here and here

mecodesta · November 11, 2013, 4:09pm

if power is greater than MOD value… you could use this to simplify the result calculation,

(x^(N%(MOD-1)))%MOD,

Eg, Binary Representation of 600000 in decimal is 10010010011111000000,
now 10010010011111000000 % ((1e9+7)-1) = 50940294

You can now see that (2^50940294)%(1e9+7) = (2^10010010011111000000)%(1e9+7) = 140171955.
Simple DP should take care about the rest of the optimizations.

kuruma · November 11, 2013, 4:10pm

Hello @all,

Besides the presented solutions (the tester one and mine) there is a much more clever solution of which I was not aware of.

Sadly, my solution was too complicated, possibly because I wanted to make something look harder than what it actually was.

I thought that for a specific value of N (around 527.000) its binary representation would exceed the capacity of an unsigned long long and as such I used simple fast exponentiation below that “threshold” value and devised a simple grade-school arithmetic scheme to “get around” the “supposed” ULL overflow.

You can read it when the links are live

The testers’ solution uses @mugurelionut scheme where the fact of not occuring any overflow just makes the task trivial with simple fast exponentiation (I really must have overlooked this fact while searching for C++ type limits).

Finally, the more theoretical solution which possibly lots of contestants used is based on a variation of Fermat’s Little Theorem that exploits the fact that:

2^M-1 mod M = 1, where M = 10⁹+7.

Therefore, we just output 2^{(2*N_bin % (M-1))} mod M

and we have correct answer!! As you can see, this trick would allow for a much higher constraint on the value of N assuming you would process it properly. Sadly, when I was told about this trick, I didn’t fully understood it (it was few months ago) and I ended up writing the most naive solution possible.

Hiroto Sekkido told me that even if M is changed, the sequence {2⁰ mod M, 2² mod M, 2² mod M,…, 2^k mod M, …} must be periodic (ignoring the first a few
terms), so such kind of cheat could be applicable.

I can leave here his solution using this approach as reference:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}

int main(){
  int T, N;
  int B;
  ll p, add;

  scanf("%d",&T);
  while(T--){
    scanf("%d",&N);
    B = 0;
    p = 0; add = 1;
    while(N){
      if(N%2) p += add;
      add = (add*10) % (M-1);
      N /= 2;
    }
    p = (p*2)%(M-1);
    printf("%d\n",(int)pw(2,p,M));
  }

  return 0;
}

This was the reason why the problem was set as EASY instead of MEDIUM.

Nontheless, I hope you have enjoyed it

Best,

Bruno

deepai_dutta · November 11, 2013, 4:54pm

This is what I did
600000’s binary is 10010010011111000000. So I computed an array of following values offline using a C program of modular exponentiation.

(2^10)%M
(2^100)%M
(2^1000)%M
(2^10000)%M
.
.
.
(2^10000000000000000000)%M

Now,600000’s binary (2^10010010011111000000)%M
can be written as *((2^10000000000000000000)%M)*(2^(10000000000000000)%M)… (2^1000000)%M)%M

bodmas · November 11, 2013, 5:07pm

Yeah. . My solution exploited Fermat’s little theorem too

abhinav1 · November 12, 2013, 10:13am

I implemented a Dynamic Programming approach. Each problem can be divided into 2 sub-problems (except powers of 2 like 4, 8, 16, 32, … which can be trivially solved). See below:

Base cases:

2^1 = 2^1 = 2;
2^2 = 2^10 = 1024;

2^3 = 2^11 = 2^10 * 2^1;
2^4 = 2^100 = (2^10)^10;
2^5 = 2^101 = 2^100 * 2^1;
2^6 = 2^110 = 2^100 * 2^10;
…
…
2^168 = 2^10101000 = 2^10100000 * 2^1000
…
and so on

Execution time - 0.23 Seconds

http://www.codechef.com/viewsolution/2913164

chaitan94 · November 12, 2013, 8:20pm

Can anyone tell me why this gave me WA?
http://www.codechef.com/viewsolution/2968557

kunjesh2014 · March 4, 2015, 2:47am

class Codechef
{

public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);

int t=sc.nextInt();

while(t–>0)
{
int n=sc.nextInt();

String s=Integer.toString(n,2);

int val=Integer.parseInt(s);

  BigInteger bi=new BigInteger("2");
  
  BigInteger ans=bi.pow(val*2);

System.out.println(ans);}
// your code goes here
}
}

bournecoder · November 11, 2013, 3:52pm

solution links not live…

anil09 · November 11, 2013, 4:18pm

how can we solve the same problem if N > 600000 i.e, if binary representation has more than 64 bits?

mecodesta · November 11, 2013, 4:32pm

@anil09, use big integer in the case of java, or use strings to manipulate bigger digits…

anil09 · November 11, 2013, 4:42pm

@mecodesta: suppose i am using only C. and i have 100bit value stored in string.That 100bit value treated as integer(N_bin) according to problem. How can we do left/right shift operations on that string?

rahul_nexus · November 11, 2013, 5:06pm

this is only possible when MOD is prime.

defacto · November 11, 2013, 5:19pm

this is what i did…it is definitely the most simple and fast way.
http://www.codechef.com/viewsolution/2923042

mecodesta · November 11, 2013, 5:21pm

Yeah but then again, most likely the MOD is selected to be a prime number to get the most out of it !!

shaleen · November 11, 2013, 10:21pm

Solution links updated

chandan721 · November 12, 2013, 1:07am

same here…CodeChef: Practical coding for everyone simple and efficient

sp1rs · November 12, 2013, 12:03pm

Why no correct submission in python ?

try_catch · November 12, 2013, 9:03pm

@anil09

u can see my version of solution…
hope u get wat i mean in the code…

http://www.codechef.com/viewplaintext/2919571

kuruma · November 12, 2013, 9:10pm

I guess directly using ULL won´t work and you have to do it incremetally… Check @mugurelionut’s solution for further reference