CHMOD - Editorial

editorial
, , , , ,
61

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

1 Like
62

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

1 Like
63

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

64

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

65

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.

66

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.

1 Like
67

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 :smiley: 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.
1 Like
68

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)
1 Like
69

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

70

@gamabunta Please look into this!

71 
#include <bits/stdc++.h>
#define ll long long
#define N 100009
#define M 1000000007
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define cot cout.tie(0)
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;ll n;cin>>n;int cf[25][n];
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i)
        cin>>v[i];
    for (int i = 0; i < 25; ++i)
        for (int j = 0; j < n; ++j)
            cf[i][j]=0;
     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} ;
     for (int i = 0; i < 25; ++i)
     {
         for (int j = 0; j < n; ++j)
         {
             if(j) cf[i][j]=cf[i][j-1];
             int num=v[j];
             while(num%p[i]==0){
                cf[i][j]++;
                num/=p[i];//to store cumulative frequency of p[i]
             }
         }
     }
    int t;cin>>t;int l,r;ll m;
    while(t--){
        cin>>l>>r>>m;l--;r--;
        ll ans=1;
        for (int i = 0; i < 25; ++i){
            if(l)
            ans*=pow(p[i],cf[i][r]-cf[i][l-1]);
            else ans*=pow(p[i],cf[i][r]);
            ans%=m;
        }
        cout<<ans%m<<"\n";
    }
    return 0;
}

what is wrong?

72

segment trees with mod can also be used. But it is showing wrong answer?

73

May be they have restricted the stack space usage

74

please can anyone tell me whatā€™s wrong in my code, i am getting runtime error
CodeChef: Practical coding for everyone

75

what is D&C??

76

Did you find the error in your code?

77

I have used a dp table to calculate the product till index ā€˜iā€™ and for finding a product in the range [l,r] i have divided the product till index r-1 by the product just before the l-1th index. Why i am getting a WA in this solution? Here mod=1e18

ll tt,i,j,n,x;
cin>>n;
ll ans,a[n],l,r,mo;
input(a,n);
lli dp[n];
dp[0]=a[0];
rep(i,1,n)
{
dp[i]=a[i]*dp[i-1];
dp[i]%=mod;
}

cin>>tt;
// tt=1;
while(ttā€“)
{
ans=1;
cin>>l>>r>>mo;
if(l==1)
ans=dp[r-1]%mo;
else
{
ans=dp[r-1]/dp[l-2];
ans%=mo;
}
cout<<ans<<"\n";
}

78

Can anybody point out mistake in my codeā€¦followed same approach as mentioned above but getting WA in some test cases
Here is my Code

79

please help me finding error in this code

thanks in advance

80

this was very helpful