Logic for RIDDLE99 LoC JUN17

help
, , , , ,
1

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

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

1 Like
3

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

4

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

5

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.

6

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

1

5 25 3

7

@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

2 Likes
8

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

1 Like
9

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