SPOTWO - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY

PREREQUISITES:

High school maths

PROBLEM:

Calculate (2N__bin)2 % 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 (2N_bin)2 % 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 2n 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

4 Likes
2

solution links not live…

3

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.

4 Likes
4

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 :slight_smile:

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:

2M-1 mod M = 1, where M = 109+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 {20 mod M, 22 mod M, 22 mod M,…, 2k 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 :slight_smile:

Best,

Bruno

2 Likes
5

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

6

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

7

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

8

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

3 Likes
9

this is only possible when MOD is prime.

10

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

11

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

12

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

13

Solution links updated

14

same here…http://www.codechef.com/viewsolution/2980062 simple and efficient

15

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

16

Why no correct submission in python ?

17

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

18

@anil09

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

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

19

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

20

Your solution is giving WA because you are passing 2nbin to your function. 600000 in binary is close to 1.1E19 and range of ULL is 1.8E19. So 2nbin will go out of range. What you can do is make two calls to the modular exponent function, first to calculate 2^nbin and then (result of first call)^2.