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

×

AMR14C -Editorial

4
2

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY.

PREREQUISITES:

Hashing

PROBLEM:

Given an array, find out pair of numbers such their sum modulo M is less than or equal to X.

QUICK EXPLANATION:

As the naive solution will have time complexity of O(n2) which will not pass, So we can make a count array A, where A[p] = count of numbers whose value modulo M is p and we can check if first number module M is p, then in how many ways we can select another number. The time complexity of above solution will be O(M+N).

EXPLANATION:

Array A contains economy rates of the bowlers.

The naive solution will look like:

    long long int answer = 0;  
    for(int i =0 ; i < N ; i++)
        for(int j = 0 ; i< N ; j++)
            if( (A[i] + A[j] <= x)
                answer++;
    cout<<answer<<endl;

But the given solution has time complexity O(n2) which will not pass in the given time limit.

As you can notice that, the value of M is not large and a solution having time complexity of O(M) will pass.

An O(M2) approach:

Make an array B. where

B[k] = count of numbers in array A which has value of k on taking modulo M.

Now another naive approach can be written in following manenr having time-complexity of O(M2).

    long long int answer = 0;
    for(int i = 0 ; i< M ; i++)
        for(int j = 0 ; j< M ; j++)
            if( (i+j)%M <= x)
                answer += B[i]*B[j];
    cout<<answer<<endl;

In this approach, we are taking all such number, whole modulo M value i or j and if their sum modulo M is less than or equal to x, then they will contribute to the answer.

The above solution will also not pass, as time complexity of given solution is O(M2).

Now we will try to optimize the solution to O(M).

as we can observe that if we want ((i+j)%M) <=x, and we have fix the value of i. then j can take only few contiguous values.

There will be two cases.

Image

So, for the case I where i<=x:

for(int i=0 ; i<= x; i++)
    answer += B[i]*(B[0] + B[1] + ....+ B[x-i])

As we can see that the values which we are multiplying will B[i], their indices are contiguous in nature, so we can use the idea of prefix sum to get the value of the range sum in O(1) time.

Define Pre[i] = B[0] + B[1] + ... + B[i] then B[i] + .... + B[x-i] = Pre[x-i] - Pre[i-1]

So modified code will look like :

  for(int i=0 ; i<= x; i++)
    answer += B[i]*(Pre[x-i] - Pre[i-1]);

Similarly we can handle the second case when i>=x . Time complexity of the above solution will be O(M+N), which will easily pass in given time limit.

Editorialist's Solution:

Editorialist's solution can be found here.

asked 14 Jan '15, 23:05

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 23 Jan '15, 22:11

admin's gravatar image

0★admin ♦♦
19.8k350498541

@amitpandeykgp Please fix the solution link it's redirecting me to the same page.

Thanks :)

(15 Jan '15, 19:30) vs134★

Added, thanks.

(15 Jan '15, 21:37) amitpandeykgp4★

There's bugs in both the recurrences.

  1. For i<=x, You should also consider the window (M-i) <= j <= (M-1)
  2. For i>x, the j is given as going till M-1. This is wrong. For example if i=x+2, and j = M-1, then (i+j)%M = (x+M+1)%M = (x+1) which is greater than x.
link

answered 07 Oct '15, 02:37

s1d_3's gravatar image

5★s1d_3
165413
accept rate: 20%

Having understood the first and the second approach, I am confused and unable to understand the O(M) approach fully.

for (int i = 1; i<= M + X; i++)
           T[i] = T[i-1] + T[i];
       long long ans = 0;
       for (int i = 1; i<=n; i++)
       {
           if (X >= a[i])
               ans = ans + T[X - a[i]];
           ans = ans + (T[M+X-a[i]] - T[M-1-a[i]]);
       }

Why is T being calculated up to M+X and when a[i]<=X why is T[M+X-a[i]] - T[M-1-a[i]] also being added to the ans? Could you kindly explain the approach/cases in a little more detail?

Thanks.

Regards, Ankit.

link

answered 16 Jan '15, 12:22

ankitdhall's gravatar image

2★ankitdhall
212
accept rate: 0%

I am not able to understand case 2 of I+j<=x. Please any illustration for that?

link

answered 15 Jan '15, 12:15

rudra_sarraf's gravatar image

3★rudra_sarraf
33621119
accept rate: 9%

1

In the second case, i>x, So i+j can not be lesser than x. But (i+j)%M <= x which means M<=(i+j) && (i+j)<=M+x
So M-i <=j && j <= M+x-i, as i>x So M-i <=j && j<= M-1 [M-1 is the maximum value of M+x-i (as i>x)], Sorry for typo in latex.

(15 Jan '15, 14:40) amitpandeykgp4★
1

Thanks partner. Gotcha :) :)

(15 Jan '15, 19:12) rudra_sarraf3★

This same code passes here but shows Wrong Answer at here. Can some help.

link

answered 28 Sep '15, 06:53

saurabhsuniljain's gravatar image

2★saurabhsuniljain
8115
accept rate: 0%

Theres typo in editorial In case 1: it shud be 0<=j<=x-i

link

answered 03 Dec '15, 17:52

sanket407's gravatar image

4★sanket407
4849
accept rate: 10%

Bad Explanation Ever !!

link

answered 07 Jul '18, 15:41

shahriar599's gravatar image

0★shahriar599
1
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:

×3,746
×342
×37

question asked: 14 Jan '15, 23:05

question was seen: 4,408 times

last updated: 07 Jul '18, 15:41