SPOTWO - Editorial

easy
editorial
nov13
spotwo

#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


#2

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.


#3

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

",(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


#4

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


#5

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


#6

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


#7

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


#8

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


#9

solution links not live…


#10

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


#11

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


#12

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


#13

this is only possible when MOD is prime.


#14

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


#15

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


#16

Solution links updated


#17

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


#18

Why no correct submission in python ?


#19

@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


#20

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