You are not logged in. Please login at www.codechef.com to post your questions!

×

SPOTWO - Editorial

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

This question is marked "community wiki".

asked 11 Nov '13, 15:04

shaleen's gravatar image

4★shaleen ♦♦
616913
accept rate: 0%

edited 11 Nov '13, 22:20

solution links not live..

(11 Nov '13, 15:52) bournecoder3★

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

(11 Nov '13, 16:18) anil091★

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

(11 Nov '13, 16:32) mecodesta4★

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

(11 Nov '13, 16:42) anil091★

Solution links updated

(11 Nov '13, 22:21) shaleen ♦♦4★

Why no correct submission in python ?

(12 Nov '13, 12:03) sp1rs2★

@anil09

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

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

(12 Nov '13, 21:03) try_catch3★
showing 5 of 7 show all

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

link

answered 11 Nov '13, 16:54

deepai_dutta's gravatar image

2★deepai_dutta
180129
accept rate: 0%

edited 11 Nov '13, 16:56

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

(11 Nov '13, 17:19) defacto3★

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

(12 Nov '13, 01:07) chandan7212★

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.

link

answered 11 Nov '13, 16:09

mecodesta's gravatar image

4★mecodesta
364151827
accept rate: 0%

this is only possible when MOD is prime.

(11 Nov '13, 17:06) rahul_nexus2★

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

(11 Nov '13, 17:21) mecodesta4★

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:

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

Best,

Bruno

link

answered 11 Nov '13, 16:10

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

edited 11 Nov '13, 16:57

Yeah. . My solution exploited Fermat's little theorem too :)

link

answered 11 Nov '13, 17:07

bodmas's gravatar image

5★bodmas
16127
accept rate: 0%

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

link

answered 12 Nov '13, 10:13

abhinav1's gravatar image

4★abhinav1
313
accept rate: 0%

edited 12 Nov '13, 10:15

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

link

answered 12 Nov '13, 20:20

chaitan94's gravatar image

4★chaitan94
2526
accept rate: 0%

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

(12 Nov '13, 21:10) kuruma3★

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.

(13 Nov '13, 05:17) sikander_nsit5★

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

link

answered 04 Mar '15, 02:47

kunjesh2014's gravatar image

2★kunjesh2014
9
accept rate: 0%

It is showing time limit exceeded what should I do to optimize the program?

(04 Mar '15, 02:48) kunjesh20142★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×15
×1

question asked: 11 Nov '13, 15:04

question was seen: 5,904 times

last updated: 04 Mar '15, 02:48