CHMOD - Editorial

editorial
, , , ,
41

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

42

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

43

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

44

ā€œPage Not Foundā€ when tying to access Setterā€™ Solution

45

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

46

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

47

@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ā€¦!!!

48

@kunal361 thanks for pointing it outā€¦i donā€™t know what i was thinkingā€¦

49

the 25 prime logic was very good trick in this problemā€¦otherwise TLe

50

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.

51

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

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

1 Like
53

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ā€¦

54

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

55

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

56

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.

57

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
58

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
59

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
60

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