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

×

CNTSOLS - Editorial

12
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Simple Math, Repeated Squaring

PROBLEM

You are given three integers d, m and N in the following relation

xd + yd + zd ≡ m, modulo N

Find the number of solutions of the above equation where

0 ≤ x, y, z ≤ U

EXPLANATION

The first observation to be made is that the value of N is very small. We already know that

ab = (a % N)b, modulo N

Despite the fact that U is a large number, it is only relevant for us to find the solutions (X, Y, Z) which satisfy

0 ≤ X, Y, Z < N

and for each solution (X, Y, Z), calculate the number of values in the range

0 ≤ x, y, z ≤ U

such that

  • x = X, modulo N
  • y = Y, modulo N
  • z = Z, modulo N

Let us say that

  • A[t] = td % N
  • 0 ≤ t < N

Now, we can iterate through the list of unique solutions (X, Y, Z)

for X = 0 to N-1
    for Y = 0 to N-1
        for Z = 0 to N-1
            if (A[X] + A[Y] + A[Z]) % N = m
                process(X, Y, Z)

The complexity of calculating A[] is O(N log d) if we use repeated squaring.

In the worst case, the number of times process() is called is O(N3).

For each solution (X, Y, Z) we wish add the solutions (x, y, z) from the complete range. The number of values of x, satisfying

  • x = X, modulo N
  • 0 ≤ x ≤ U

is

number-of-sols(X) =

floor(U / N) + {
    1, if (U % N > 0 AND X ≤ U % N),
    0, otherwise
}

Now, the number of solutions (x, y, z) for (X, Y, Z) is simply

answer = 0

process(X, Y, Z) =
    answer = answer +
        number-of-sols(X) *
        number-of-sols(Y) *
        number-of-sols(Z)

Thus, the answer can be found in O(N3) time.

CODING COMMENTARY

The answer has to be found modulo 109</sup+7. This leaves a lot of scope for integer overflow. Make sure that your implementation uses 64-bit integers for all intermediate results, at the least.

64-bit integers can handle the overflow of multiplying two 32-bit integers, but not three. You must find the modular result after each product.

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

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 14 Aug '13, 12:21

Ah! My solution, just like the editorial!

(12 Aug '13, 16:02) tijoforyou2★

Why not X will always be less then U%N in number-of-sols?

(20 Aug '13, 07:46) imdeepakg3★

I also used the nested loop procedure. But instead on looping on x,y and z, I looped on i,j,k such that
xd ≡ i(mod n),
yd ≡ j (mod n),
zd ≡ k(mod n).
I pre-computed number of solutions of x for xd ≡ i(mod n) for each 0<= i< n.

for i = 0 to N-1  
    for j = 0 to N-1  
        for k = 0 to N-1  
            if (i+j+k) % N == m  
                count+= solution[i]*solutions[j]*solutions[k];

I was getting wrong answer while submitting but I tested many large cases as well as border cases. All were matching with output of an accepted solution.

Is above procedure wrong, or there is any particular test case which fails in this algorithm?

link

answered 13 Aug '13, 18:04

shashwat001's gravatar image

4★shashwat001
5241610
accept rate: 17%

How does the condition (i+j+k) % N == m mean that xd ≡ i(mod n), and so on?

(13 Aug '13, 18:22) tijoforyou2★

I also did like you. See this solution as reference http://www.codechef.com/viewsolution/2464513

(14 Aug '13, 00:19) karan1735★

maybe your pow function has a bug when modulo = 1 . it was my bug , hope this helps.

(14 Aug '13, 01:52) contesant5★

What part of this solution is DP ?

link

answered 14 Aug '13, 02:47

a2n3k7it's gravatar image

3★a2n3k7it
16
accept rate: 0%

I had not tagged the problem as Dynamic Programming. Have removed it from the PREREQUISITES as well.

(14 Aug '13, 12:21) gamabunta1★

what is wrong with my solution I am using the same concept as given http://www.codechef.com/viewsolution/2504889 please find the bug in my code. Thanks!

link

answered 12 Aug '13, 17:48

vivekjnv93's gravatar image

3★vivekjnv93
1513512
accept rate: 0%

Well I was using a similar concept for my first solution but i got WA. Please tell me what is wrong with this approach. code: http://www.codechef.com/viewsolution/2510118

link

answered 12 Aug '13, 19:52

a_g2009's gravatar image

5★a_g2009
85237
accept rate: 0%

This problem can be done using DP in O(n^2) time.

link

answered 16 Aug '13, 10:29

gargdhruv36's gravatar image

0★gargdhruv36
1
accept rate: 0%

the trick behind upperlimit of N is really good and was not easy to find out......

link

answered 20 Aug '13, 10:39

pandeyarvind70's gravatar image

4★pandeyarvind70
1611
accept rate: 0%

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,026
×3,458
×1,897
×281
×150
×27

question asked: 12 Aug '13, 15:21

question was seen: 5,180 times

last updated: 20 Aug '13, 10:39