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

×

Logic for RIDDLE99 LoC JUN17

I could get the first 2 test cases correctly but got WA (not TLE) for 3 and 4. Tried to think a lot but couldn't understand what is wrong here. Any help is appreciated. Thanks! Here is the logic I used for this question:

 import java.util.*;
class c
{
public static void main(String []args)
{
long t,a,b,m;
Scanner sc = new Scanner(System.in);
t=sc.nextLong();
for(long i=1;i<=t;i++)
{
a=sc.nextLong();
b=sc.nextLong();
m=sc.nextLong();
long c=0;
if(m>b)System.out.println("0");
else if(m<a)
    {
        c=(long)((b-a)/m);
        if(a%m==0||b%m==0)
        c++;
    System.out.println(c);
}
else 
    {
        c=(long)((b/m));
        System.out.println(c);
}
}
}
}

asked 04 Jul '17, 00:34

lord_aj's gravatar image

1★lord_aj
11
accept rate: 0%


You have to tell him the count of numbers between A and B (A<=B)which are divisible by M. A number is divisible by m,it means that number is a multiple of m.Now you need to find the number of multiples of m in between A and B(both inclusive).We can say that number of multiples of m in between 1 and N is N/m. so to find number of multiples in between A and B,find number of multiples up to B and subtract number of multiples up to A-1 and hence answer is B/m-(A-1)/m;

here is my accepted solution https://www.codechef.com/viewsolution/14370596

link

answered 04 Jul '17, 00:47

hruday968's gravatar image

2★hruday968
1.7k210
accept rate: 14%

Thanks.. I saw the logic you (and many other people) used and it is perfectly understandable. What I tried to do was - If M lies b/w A and B, then no. of multiples will be B/M and if it lies before A, then no. of muktiples will be (B-A)/M (+1 if either A or B is also a multiple). Could you take the time to tell what error did I make thinking this way? PS: I can't upvote your answer, but it was helpful (obviously) :)

(04 Jul '17, 01:14) lord_aj1★

Your logic seems fine to me. I have been curious about your WA and had been debugging your code tbh. :p

(04 Jul '17, 01:17) vijju123 ♦5★

hey your code fails when (b-a)/m!=b/m-a/m and here is the test case

1

5 25 3

(04 Jul '17, 01:39) hruday9682★

Oh.. Yes! Missed this. Thanks for the help! @hruday968 @vijju123

(05 Jul '17, 00:56) lord_aj1★

Your code gives wrong output for such type of test cases, which is common on larger numbers-

Input
1
1007 2009767 55
Your Output
36522
Correct Output
36523

On changing 1007 to 1045 (which is the 19th multiple of 55) your code prints correct output since you made sure to include those type of cases.

The difference between your logics is that in computer, you cannot claim that b/m -a/m = (b-a)/m always.

Take example of- b=10, a=8,m=9

10/9-8/9=1 
(10-8)/9=0

Check this test case also-

Input
1
11 100 9
Your Output
9
Correct Output
10

What you are doing is, (100-11)/9=89/9=9 Neither 100 nor 11 are multiple of 9.
What he did is, 100/9 - (11-1)/9=11-1=10.

To correct it, you should adjust a and b to nearest allowed multiple of the number. Like, a should be raised to nearest multiple of m, and b should be lowered to nearest multiple of n. Then your code prints correct answer.

In the end, by (b-a)/m we are seeing how many multiples of m we can fit inside the range STARTING from a.

If you start from 11, you can fit multiples in range of 11 to (11+81) = [11,92]. The multiples in this range is 9.

But we can prove by contradiction, that if you start from 18, multiples will be more. [11+7,92+7]=[18,99]. There is 1 more multiple here. This is the edge case to your logic.

link

answered 04 Jul '17, 01:35

vijju123's gravatar image

5★vijju123 ♦
13.1k1730
accept rate: 19%

edited 04 Jul '17, 01:51

2

@vijju123

his code fails when (b-a)/m!=b/m-a/m and here is the test case with small numbers

1

5 25 3

(04 Jul '17, 01:42) hruday9682★
1

Yes, i figured it out dear. Was editing the answer whole time XD. Did a proper research on this behavior today, you can say :p

(04 Jul '17, 01:45) vijju123 ♦5★
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:

×2,279
×185
×179
×136
×1
×1

question asked: 04 Jul '17, 00:34

question was seen: 433 times

last updated: 05 Jul '17, 00:56