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

×

Help in SEGPROD

I was trying to solve the first two subtasks of SEGPROD but it was giving me NZEC everytime. I don't know what made the program crash. Please help me debug it.

I am using the following logic to answer all the queries:

Let N = Product of all elements (from 1 to N ) (modulo P)
Let L = prefix product upto L-1 (modulo P)
Let R = suffix product from R+1 (modulo P)

Answer = (N * modularInverse(Q) * modularInverse(R)) (modulo P);

I tested this logic for sample inputs and some other Test Cases and it was giving correct output.

For first subtask P was prime and all the numbers were between 1 & P-1. So using MMI I could have got atleast 20 points. I am using Fermats’s little theorem to find MMI.

Here is the link to my solution using recursive version of it.

And here is the link to my solution with iterative version of it.

But they both are giving NZEC for reasons unknown to me.

I also used another method to find MMI mentioned here by Anveshi Shukla. But still the same results. Here is the link to that code.

Now for Subtask 2: P = x^k where x is prime and all the numbers are in range 1 to P-1. So I tried using Extended Euclidean algorithm to find MMI of numbers as it works when number and P are co-prime. This holds for both the subtasks and should atleast pass them. Here is the link to it.

The normal version of the code by by doing multiplication everytime for all the queries giving TLE is here. The code works fine. I just replaced running the loop everytime by the method mentioned above which gives result in constant time for each query. I can't understand what is wrong with my MMI codes. Please help.

asked 14 Nov, 01:01

vatsalsura's gravatar image

3★vatsalsura
1407
accept rate: 12%


In almost every version of your answer there is Integer Overflow resulting in a wrong track for the answer. For some cases it caused RE.

 x = (sum * pre * suf) % P;

This line in your code (present twice) is causing the overflow. Replace it by -

 x = (((sum * pre)%P) * suf) % P;

Do that and you will get AC for subtask #1. :) (And remember to take mod in each step)

For subtask #2 this logic won't work as A[i] and P might not be co-prime and hence don't have a modular multiplicative inverse.

link

answered 14 Nov, 04:13

trijeet's gravatar image

5★trijeet
1855
accept rate: 33%

1

Nicely explained, bro ! :) @trijeet

(14 Nov, 06:29) jaideeppyne4★

Thank you. I can't believe I did such a silly mistake. I was very careful for overflow's and checked for each and every calculation except for this one. I am so angry with myself. I was changing MMI finding techniques while the error was in calculating x.

(14 Nov, 17:12) vatsalsura3★

And for subtask 2 will the chinese remainder theorem solve the subtask or anything else?

(14 Nov, 17:20) vatsalsura3★

Read @taran_1407's appraoch from his psot. Nothing like CRT needed.

(14 Nov, 18:27) vijju123 ♦5★

I too tried messing with CRT first. :)

PS:Thanks for referral @vijju123. And Nicely answered @trijeet

(14 Nov, 19:04) taran_14076★
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:

×1,929
×335
×247
×13

question asked: 14 Nov, 01:01

question was seen: 153 times

last updated: 14 Nov, 19:04