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

×

CHMOD - Editorial

24
6

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Simple Math, Repeated Squaring

PROBLEM

You are given a list of N integers.

Each value in the list is between 1 and 100.

You have to respond to T queries of the following type

  • Given L and R
  • Find the product of all integers in the given list between L and R, inclusive
  • Find the above product modulo some M, which is also given

EXPLANATION

For each query, iterating through the list between L and R to maintain the modular products is too slow.

Of course, we use the fact that each value is between 1 and 100 to our advantage.

  • There are 25 prime numbers between 1 and 100

Each number has a unique prime factorization. The product of a set of numbers can also be simulated by adding up the frequencies of each prime in all numbers in the set.

For example, suppose we have to multiply 36 and 45.

36 = 2232
45 = 325

36 * 45 = 22345

Thus, we can maintain a table of cumulative frequencies for each of the 25 primes between 1 to 100 for the given list of numbers.

When processing a query

  • consider each of the 25 primes
  • find the frquency of the prime between L and R. This can be done in O(1) using pre-calculation of cumulative frequencies
  • calculate primefrquency for each prime and multiply these values
  • maintain the result modulo M

These ideas are best presented in the pseudo code below.

PSEUDO CODE

Given:
    N, the number of numbers
    L[N], the list of numbers
    P[25], primes between [1, 100]
    CF[N,25], cumulative frquency for each prime

for each query Given Query: left, right, M answer = 1 for i = 1 to 25 r = CF[right,i] - CF[left-1,i] v = P[i]r % M, use repeated squaring answer = (answer * v) % M

The complexity of answering each query would be O(25 log N).

Cumulative Frequencies can be calculated in O(25 * N).

CODING COMMENTARY

You can either calculate the primes in thr porgram or hard code the array of primes by calculating it offline.

The repeated squaring should take care of the fact that the exponent can be 0. a0 should return 1 for any a.

Calculating the cumulative frequencies table should be done carefully. The frequencies of the primes for each number between 1 and 100 can be pre-calculated. Use these frequencies to build the cumulative frequencies table.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 12 Aug '13, 15:19

gamabunta's gravatar image

1★gamabunta
2.3k128183169
accept rate: 14%

edited 12 Aug '13, 15:20

this is giving TLE anyone plz help http://ideone.com/pawz5b

(13 Aug '13, 23:26) v2v43★

I hate the question where key lies in exploiting the limits.

(18 Aug '13, 09:52) imdeepakg3★

Is the setter's solution not up? I am getting a "Page Not Found".

link

answered 12 Aug '13, 16:47

tijoforyou's gravatar image

3★tijoforyou
4.2k52364
accept rate: 15%

"Page Not Found" when tying to access Setter' Solution

(17 Aug '13, 11:59) sap88coder2★

@gamabunta Please look into this!

(28 Aug '13, 16:19) tijoforyou3★

D&C solution gives TLE. Complexity should be O(lg n) per query. Does anyone know why it is? Maybe in this approach MOD (%) operator is called fewer times...

link

answered 12 Aug '13, 15:39

kingarthurie's gravatar image

4★kingarthurie
70347
accept rate: 16%

I don't see how D&C would apply to this problem, furthermore per query time complexity after all those pre-computation should be O(25) = O(1).

(12 Aug '13, 15:41) tyrant1★

solution(l, r) = solution(l, m) * solution(m,r), where m is (l+r)/2

something like that should be D&C, the simplest one.

and you are wrong about O(1), it is O(lg n), you have forgotten fast squaring ....

(12 Aug '13, 15:49) kingarthurie4★

@kingarthurie: My bad :(

(12 Aug '13, 16:00) tyrant1★

If you're doing a naive D&C, query complexity would be Omega(n).

Your recurrence would be T(n) = 2 * T(n / 2) + Omega(1).

T(n) = Omega(n)

(14 Aug '13, 06:21) michaelx4★

Took me ages to figure the idea! My solution: http://www.codechef.com/viewplaintext/2511516

First, I had a go at it using Python and Java, thanks to the support for big integers. But they gave me TLE.

Thinking "out of the box", I tried the naive method. Actually find all products (keeping the modulo) in the given ranges. That too, timed out obviously.

Then I figured out that N is only as large as 100. Instead of storing the primes' frequencies. I stored the numbers frequencies itself. A complexity of O(100 log N) per query and O(100 N) for pre-calculations. But this welcomed me with a shower of TLES.

Common, how else can I optimize? Multiplications... modulos... I thought of how to stop myself from looping, even the 100 times, just to avoid those computations. Couldn't find any better solution. I thought, I am having modular exponentiation. If somehow I could increase the exponents, by combining some numbers, then I could further optimize. But couldn't think of how to?

One day, thanks to the fundamental theorem of arithmetic, I remembered the prime numbers. Actually, I thought of storing the counts of powers of 2, as counts of powers of 2 itself. And just like that, the thought extended. I was not much thrilled, as the complexity now will be O(25 log N), but notation-wise, it is the same as O(100 log N), as both are O(log N). Still, I thought of 75% reduction in the running time.

Coded it up, but tests in my local machine could only bring down the running time (on average) from ~8.5 seconds to ~2 seconds per file. And we needed 1 second. But there is nothing bad as not trying. So, I tried, and voila! It was accepted.

That is my story of solving CHMOD.

What I wonder?
There are at least a few, who solved it at one go. I mean, how did they even think directly about the ideas of cumulative frequencies of prime numbers. Didn't the idea of storing cumulative frequencies of the given numbers cross their mind? Or is there another idea?

Would love to hear from people who cracked this at their first attempt itself.

link

answered 12 Aug '13, 16:23

tijoforyou's gravatar image

3★tijoforyou
4.2k52364
accept rate: 15%

edited 13 Aug '13, 18:14

2

I crack this problem in my first attempt :)

(12 Aug '13, 16:51) sandeepandey2★

@sandeepandey What was your approach? Is it the same as the one discussed in the editorial?

(12 Aug '13, 16:55) tijoforyou3★
1

Yeah same approach. A(i) < =100 was big hint for me :)

(12 Aug '13, 17:06) sandeepandey2★

:D Right! Right!

A(i) ≤ 100 was a hint for many (including me). But for me, the idea of prime numbers didn't click before there were a few TLEs.

@sandeepandey Thank you for sharing!

(12 Aug '13, 17:12) tijoforyou3★
1

@tijoforyou same story here. Apart from the fact that A(i) ≤ 100 was a hint i figured out at starting :)

(12 Aug '13, 17:36) sobhagya3★
1

Interesting. I used prime numbers in the first go and didn't even notice that storing freqs of 1-100 could have been an alternative approach. To answer your question, I started solving the problem by looking at the segment products. I noticed that they'll consists of only primes from 1 to 100 and that's how I came up with the idea of storing prime frequencies. Thanks for this alternative view!

(13 Aug '13, 15:45) shantanuag2★

@shantanuag Thank you for your inputs on this. :)

(13 Aug '13, 19:17) tijoforyou3★
showing 5 of 7 show all

The idea of my solution is to use segment tree to calculate sums in [L, R] interval for log10 values and later convert this to integer applying modulo operation.

When I had such sum, first I found how many billions are in result (log10 / 9.0) exponentially multiplied this value and result multiplied with 10^dif where dif is something like real mod after dividing by 9.0 (hope it's clear).

link

answered 12 Aug '13, 15:42

betlista's gravatar image

3★betlista ♦♦
16.8k49115225
accept rate: 11%

I can up to that idea 2, but this idea give me WA if I'm correct, most probably duo floating point precision problems.

(12 Aug '13, 15:51) kingarthurie4★
1

Truth is, that I didn't get accepted yet, but I don't think that there is precision problem. I'll let you know, when (if) I'll get AC ;-)

(12 Aug '13, 16:10) betlista ♦♦3★

Even I thought of segment trees. But then, for each modulo, creating a separate segment tree is wasteful. Having a segment tree with big integers is also wasteful (and probably give memory error).

But I noticed that there are no changes in the array to be made. So, if i have an array prod of bigints, so that prod[i] = product of all number from a[1] to a[i], then product from a[l] to a[r] could be found in O(1) as prod[r]/prod[l - 1]. But the time required to do the math with bigints was too costly, and i got a lot of TLEs.

I, however, managed to find the idea of primes and got an AC.

(12 Aug '13, 16:29) tijoforyou3★

Using Segment tree was my second approach as storing product of numbers in a product array table was my first approach but I was getting SIGFPE and then latter on WA on both the approaches.

What I was thinking is the highest value of mod is 10^9 and during calculation of product or formation of segment tree, i was taking mod of 10^9 + 7 in order to maintain in the size in int.

(13 Aug '13, 08:56) hrculiz1★

After then I thought perhaps this is not good idea so I implemented big integers in c++, this was my first handshake with big integers in c++, thanks to the problem I learned how to use big integers but still problems was not solved and got TLE's.

(13 Aug '13, 08:56) hrculiz1★

there so much bilions in result such that owerflow in even long double : result = k * 1e9 + x ; result <= 1e200,000 so , k <= ~1e20000

(13 Aug '13, 20:37) contesant5★

But when using log10, the max sum is 10.000 * 2 ;-)

(13 Aug '13, 20:40) betlista ♦♦3★
showing 5 of 7 show all

I use the same Algorithm as you do..but i got TLE ...

link

answered 12 Aug '13, 15:59

jtjl's gravatar image

6★jtjl
1
accept rate: 0%

It's probably because your power function is recursive...make it iterative and submit it again....Happened same to me... Very tight Time Limit Constraint...

(12 Aug '13, 16:19) xpertcoder4★

i'd got AC and my power function was recursive too :D

(12 Aug '13, 20:58) akrai482★

so was mine !

(13 Aug '13, 19:14) mecodesta4★

I used the same algo but instead of 25 i used all the 100 numbers that is O(100log(n)) solution , but it got TLE , can anyone explain why it is so , as time is independent of constants so O(100log(n)) should be same as O(25*log(n)) .

link

answered 12 Aug '13, 16:04

m_garg's gravatar image

3★m_garg
31125
accept rate: 0%

Time is not independent to constants. This was time tight solution, and you must use prime decomposition in order to get AC. You did 4 time more job, and your solution was 4 time slower. Usually it is not the problem, but in this problem, 4 times slower running time is a lot.

(12 Aug '13, 16:09) kingarthurie4★
1

The O(25 log N) solution takes only 1/4-th of the time that O(100 log N) solution takes. So, that is obviously way faster. Many, I think, failed to figure that out! :(

(12 Aug '13, 16:36) tijoforyou3★

this is what i did...the similar approach..can be applid to solve.this problem wcount

link

answered 12 Aug '13, 16:06

princerk's gravatar image

3★princerk
72871123
accept rate: 5%

I dont think this question qualifies as an easy one. It requires segment trees and modular exponentiation. Please consider moving it to medium. It took me 3 hours to get to the Algorithm. And only around 900 could solve it over the ten days.

link

answered 12 Aug '13, 20:09

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156281
accept rate: 4%

Segmented Trees ? Why do you need that in this ?

(12 Aug '13, 21:55) malaykeshav4★

@pushkarmishra : hi,could you please elaborate your idea of solving this problem using Segment Tree ?

(14 Aug '13, 09:37) sandeepandey2★

this is giving TLE anyone plz help http://ideone.com/pawz5b

link

answered 13 Aug '13, 23:25

v2v4's gravatar image

3★v2v4
1
accept rate: 0%

@v2v4 I just changed the power function (exp in your code) and it is now AC. Here is the link http://www.codechef.com/viewplaintext/2582486

Your code is absolutely correct, it's just that your exponential function performs too much modulus operations. And modulus operations are computationally expensive.

Happy Coding.

(26 Aug '13, 21:26) viaan2★

can sm1 plss check why m i getting WA for my code.....

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

i m getting all right answers for as many test cases as i could think of....am i missing sm exceptional case??

link

answered 14 Aug '13, 02:22

phantom002's gravatar image

5★phantom002
62114
accept rate: 20%

Can anybody tell what's wrong with the code?
http://www.codechef.com/viewsolution/2517179

link

answered 14 Aug '13, 07:48

abhinav1592's gravatar image

2★abhinav1592
4572713
accept rate: 0%

In your program, the line res=(res*power(i,tmp[i],m)); can give an overflow. It should have been res=(res*power(i,tmp[i],m))%m; to avoid overflows.

(14 Aug '13, 09:16) tijoforyou3★

What's wrong with the following DP algo? (Not totally correct just the idea)

long long inputArray[n]; long long dp[n];

dp[0]=inputArray[0]; for(int i=1;i<n;i++)dp[i]=dp[i-1]*inputArray[i];

for(int i=0;i<queries;i++) { if(l==0)cout<<dp[r]<<endl; else cout<<dp[r]/dp[l-1]<<endl; }

link

answered 16 Aug '13, 11:39

charlotte's gravatar image

4★charlotte
1
accept rate: 0%

Why is comlplexity of prime factorizing each number not considered ? In the worst case, we'll have atleast floor(25/2)=12 division tests for each number. I think the expression of complexity is of the sort: O( N * CostFactorization + T * NumUpdates * ExponentiationTime) so it will be O( N + T * lg(MAX))

link

answered 16 Aug '13, 15:47

dtb_'s gravatar image

3★dtb_
75123
accept rate: 0%

edited 16 Aug '13, 15:50

can somebody give me the testcase for which i am getting sigfpe my solution is:http://www.codechef.com/viewsolution/2481713

link

answered 18 Aug '13, 10:54

khitish's gravatar image

3★khitish
45151824
accept rate: 0%

@khitish..int can not store such huge values(multiplication of all nos may reach upto 100 ^ 100000..some combination of nos may lead to ur b array storing a "0"..please go through the editorial to get an idea of what u have to do to solve this sum...!!!!

link

answered 18 Aug '13, 11:13

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

edited 18 Aug '13, 11:14

@kunal361 thanks for pointing it out...i don't know what i was thinking...

(18 Aug '13, 16:18) khitish3★

the 25 prime logic was very good trick in this problem........otherwise TLe

link

answered 20 Aug '13, 00:16

akashverma_123's gravatar image

3★akashverma_123
1197
accept rate: 3%

can there be overflow in the cumulative frequency if each of it's elements is int? Also when I logically declared my data-types i got WA solution1and when I changed everything to long long it got accepted solution2. Can any one please tell the reason or point out where is the overflow in the first program? Thanks in advance.

link

answered 24 Aug '13, 22:19

sudharkj's gravatar image

3★sudharkj
5137
accept rate: 0%

1

@sudharkj The overflow is in your rsq function. There, the type of a is int, and the statement a=(a*a)%m; will overflow.

Eventhough the initial argument passed to rsq can only be as large as 97, we are calculating its powers (can be upto 100 !!).

Imagine calculating 9750 modulo 109. Surely, there can be overflows here.

(24 Aug '13, 22:38) tijoforyou3★
1

thanks! a friend of mine replied the same thing and it got accepted.

(24 Aug '13, 23:45) sudharkj3★

Again, posting here for help.. I'm stuck with this problem. For some test case no. > 100, it's giving me SIGSEV runtime error..I've tried every corner case I can think of..still not getting any leads..

link

answered 26 Aug '13, 10:58

samkit's gravatar image

2★samkit
1612510
accept rate: 0%

Oh, it is not. Because, there are so many AC solutions, which won't work, when it a number is greater than 100.

(26 Aug '13, 12:43) tijoforyou3★

You are getting SIGSEGV because, your arrays a and cf aren't large enough. Check carefully with the constraints!!

(26 Aug '13, 12:47) tijoforyou3★

That's obvious that there is some bug in my solution, but i'm not able to figure it out. Tried arrays with large size, but no wonder.

(26 Aug '13, 13:36) samkit2★
1

I only looked at your last submitted code (at the time, the above comment was made), and the array size was small.

I looked into your newer codes.

I took your code and made a small change - made the arrays global. (Declaring large arrays locally will also give stack memory limit error.)

Here is the changed code. It has escaped from Runtime Error, but you have a new problem to cope with now - TLE.

(26 Aug '13, 16:25) tijoforyou3★
1

Just got AC..I was amazed when I noticed that unnecessary use of mod operator in power function as well as final result's computation was causing time limit..#urgh In the morning, declaration of large dynamic array in main function was causing sigsev..Thanks for pointing out that..

Today,I've submitted more than 40 solutions each with minor change :-D It took me hell lot of time to figure out these loopholes..after suffering this, learnt two things:-P 1. mod function is computationally too expensive, dont use without need. 2. Declaring large array locally can cause stack memory limit error.

(26 Aug '13, 17:52) samkit2★
1

Yes! Whenever there is a SIGSEGV in a code that involves only arrays (barring the normal variables), then

  1. Either it is because we have violated the array bounds (either because the array size is too small, or because of some negative indices)
  2. Or because we have large local arrays (which can be moved outside the block into the "global" visibility to remove SIGSEGV)
  3. Or because our array size is very large, that there is not enough memory at all (which cannot be avoided and we will need other better algorithms)
(26 Aug '13, 18:00) tijoforyou3★
showing 5 of 6 show all

my logic is same as the editorial,but it gives TLE. http://www.codechef.com/viewsolution/3914314 please can someone guide me where i might be wrong

link

answered 17 May '14, 22:18

shubham12's gravatar image

3★shubham12
4421610
accept rate: 13%

please check submision id 4099624,it's giving wrong answer.. http://www.codechef.com/viewsolution/4099624 please say why it's wrong? On which test case it's wrong ?????

link

answered 16 Jun '14, 00:31

deepansh90's gravatar image

2★deepansh90
313
accept rate: 0%

I have used precalculation technique . For ex. let 1 2 3 4 5 be array . Then through precomputation i have made another array . 1 2 6 24 120 . After that in order to cal any query it is :- arra[m]/arr[l-1] where l is lower rage and m is upper .. Is my approach wrong.. getting WA many times Could someone help me out. Solution is :- http://www.codechef.com/viewsolution/6845308

link

answered 08 May '15, 01:29

ritwikenator's gravatar image

2★ritwikenator
4614
accept rate: 16%

Please help me out. Tried every optimization I could think of!

https://www.codechef.com/viewsolution/10665307

link

answered 02 Jul '16, 00:58

utkarshgupta's gravatar image

2★utkarshgupta
1
accept rate: 0%

What is wrong with this code? I am getting WA. http://ideone.com/NnOcyz

link

answered 21 Jul, 23:45

aditya24041997's gravatar image

2★aditya24041997
0
accept rate: 0%

Will the segment tree approach work? I tried but its giving WA.

link

answered 12 Oct, 17:54

saurabh__'s gravatar image

3★saurabh__
1
accept rate: 0%

can anyone help me with the following code. why is it not working i can't see...please. https://www.codechef.com/viewsolution/15878086

link

answered 16 Oct, 20:22

pri_1234's gravatar image

3★pri_1234
111
accept rate: 0%

-1

include <iostream>

include <cstdio>

using namespace std;

unsigned long long int pr(int a,int b,unsigned long long int m){

if(b == 0)return 1;
unsigned long long int ans = pr(a,b/2,m)%m;
if(b%2){
    return (((a*ans)%m)*ans)%m;
}else{
    return (ans*ans)%m;
}

}

int ans[100001][26];

int main() {

int p[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

unsigned long long mod,aa;
int l = 25;
int arr[101][25] = {{0}};
for(int m = 2;m < 101;m++){
    int awe = m;
    for(int j = 0; j < l && awe > 1; j++) {
        if(awe%p[j] == 0) {
            while(awe%p[j] == 0) {
                arr[m][j]++;
                awe /= p[j];
            }
        }
    }
}
int n;
cin >> n;
int in[n];
for(int i = 0;i < n;i++) {
    scanf("%d",&in[i]);
}
for (int i = 0; i < 25; i++ ) {
    ans[0][i] = arr[in[0]][i];
}
for(int i = 1;i < n;i++){
    for(int j = 0;j < 25;j++){
        ans[i][j] = ans[i-1][j] + arr[in[i]][j];
    }
}
int final[26];
int k;
cin >> k;
while(k--){
    int l,r;
    scanf("%d%d%llu",&l,&r,&mod);
    aa = 1%mod;
    for(int i = 0;i < 25;i++){
        if (l > 1)final[i] = ans[r-1][i] - ans[l-1][i] + arr[in[l-1]][i];
        else final[i] = ans[r-1][i];
    }

    for(int i = 0;i < 25;i++){
        if(final[i]){
            aa = (aa*pr(p[i],final[i],mod));
            if(aa >= mod)aa = aa%mod;
        }
    }
    cout<< aa<<endl;
}

return 0;

}'

why i got TLE..can any one help me please...

link

answered 13 Aug '13, 08:06

sudit11's gravatar image

3★sudit11
0
accept rate: 0%

I changed your recursive pr function to iterative one and viola!!! It worked...

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

I had this same prob. and I don't know why recursive is failing in our case...as akrai48 has implemented it recursive...I think we have been doing things that aren't optimized...Would be grateful if someone throw a light on it... :-)

(13 Aug '13, 15:59) xpertcoder4★
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:

×12,344
×2,686
×270
×103
×25

question asked: 12 Aug '13, 15:19

question was seen: 9,909 times

last updated: 16 Oct, 20:23