3

I have read about Linear Diophantine equations such as ax+by=c are called diophantine equations and give an integer solution only if gcd(a,b) divides c.

These equations are of great importance in programming contests. I was just searching the Internet, when I came across this problem. I think its a variation of diophantine equations.

Problem :

I have two persons,Person X and Person Y both are standing in the middle of a rope. Person X can jump either A or B units to the left or right in one move. Person Y can jump either C or D units to the left or right in one move. Now, I'm given a number K and I have to find the no. of possible positions on the rope in the range [-K,K] such that both the persons can reach that position using their respective movies any number of times. (A,B,C,D and K are given in question).

My solution:

I think the problem can be solved mathematically using diophantine equations.

I can form an equation for Person X like A x_1 + B y_1 = C_1 where C_1 belongs to [-K,K] and similarly for Person Y like C x_2 + D y_2 = C_2 where C_2 belongs to [-K,K].

Now my search space reduces to just finding the number of possible values for which C_1 and C_2 are same. This will be my answer for this problem.

To find those values I'm just finding gcd(A,B) and gcd(C,D) and then taking the lcm of these two gcd's to get LCM(gcd(A,B),gcd(C,D)) and then simply calculating the number of points in the range [1,K] which are multiples of this lcm.

My final answer will be 2*no_of_multiples in [1,K] + 1.

I tried using the same technique in my C++ code, but it's not working(Wrong Answer).

This is my code : http://pastebin.com/XURQzymA

My question is: can anyone please tell me if I'm using diophantine equations correctly ?

If yes, can anyone tell me possible cases where my logic fails.

These are some of the test cases which were given on the site with problem statement.

A B C D K are given as input in same sequence and the corresponding output is given on next line :

2 4 3 6 7

3

1 2 4 5 1

3

10 12 3 9 16

5

This is the link to original problem. I have written the original question in simple language. You might find it difficult, but if you want you can check it:

http://www.codechef.com/APRIL12/problems/DUMPLING/

Please give me some test cases so that I can figure out where am I doing wrong ?

Thanks in advance.

10
  • 1
    Surely it is against the rules of the contest to ask for help? Can you wait for the contest to end first?
    – Nabb
    Apr 3, 2012 at 9:41
  • 1
    Can I expect some test case or at least some hint ? Apr 3, 2012 at 9:55
  • Dude, your code compiles and runs and gives the correct answers for the examples. What's the problem exactly? PS: your gcd algorithm doesn't need the arguments in order; you can elide 18 lines of code. Apr 3, 2012 at 10:20
  • @EddieEdwards: Yeah.I know my code works fine on examples but don't know why am I getting wrong answer on codechef.Any help will be appreciated. Apr 3, 2012 at 10:40
  • 1
    Yeah, well :) He's solved the problem on his own anyway. Just a small detail missed. And he seems to have disappeared without trace now he's got the fix so boy do I feel good for helping him :) Apr 3, 2012 at 13:00

2 Answers 2

14

Solving Linear Diophantine equations

ax + by = c and gcd(a, b) divides c.

  1. Divide a, b and c by gcd(a,b).
  2. Now gcd(a,b) == 1
  3. Find solution to aU + bV = 1 using Extended Euclidean algorithm
  4. Multiply equation by c. Now you have a(Uc) + b (Vc) = c
  5. You found solution x = U*c and y = V * c
0

The problem is that the input values are 64-bit (up to 10^18) so the LCM can be up to 128 bits large, therefore l can overflow. Since k is 64-bit, an overflowing l indicates k = 0 (so answer is 1). You need to check this case.

For instance:

unsigned long long l=g1/g; // cannot overflow
unsigned long long res;
if ((l * g2) / g2 != l)
{
    // overflow case - l*g2 is very large, so k/(l*g2) is 0
    res = 0;
}
else
{
    l *= g2;
    res = k / l;
}
2
  • Sorry for late reply but as told by you I was working on the problem.The thing pointed out by you seems to be correct,so I tried solving the problem in Java using BigInteger but got NZEC :( I'm still working on it and looking forward to solve it. Apr 3, 2012 at 15:07
  • The fix above does it with your original code in a few lines. You just need to check for overflow (multiply then divide, and if the result is correct you did not overflow) and set res = 0 if it happens. Apr 4, 2012 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.