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.

dark_shadow
  • 3,503
  • 11
  • 56
  • 81
  • 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 03 '12 at 09:41
  • 1
    Can I expect some test case or at least some hint ? – dark_shadow Apr 03 '12 at 09: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. – Eddie Edwards Apr 03 '12 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. – dark_shadow Apr 03 '12 at 10:40
  • Can you give an example where it fails? – Eddie Edwards Apr 03 '12 at 10:47
  • Got it - see answer below - it's all in the precise wording of the question. – Eddie Edwards Apr 03 '12 at 10:51
  • You shouldn't misuse the community by asking problems which are from an ongoing contest(which is against the rules of that contest). – Priyank Bhatnagar Apr 03 '12 at 11:34
  • It is not against the rules of that contest. Check the rules page here http://www.codechef.com/APRIL12/. – Eddie Edwards Apr 03 '12 at 11:40
  • @EddieEdwards, _Please do not discuss strategy, suggestions or tips in the comments during a live contest. Posting questions clarifying the problem statement is ok._ Yeah, sure, asking for help on any other website seems ok :| – Priyank Bhatnagar Apr 03 '12 at 12:54
  • 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 :) – Eddie Edwards Apr 03 '12 at 13:00

2 Answers2

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
Jarosław Gomułka
  • 4,935
  • 18
  • 24
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;
}
Eddie Edwards
  • 428
  • 2
  • 5
  • 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. – dark_shadow Apr 03 '12 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. – Eddie Edwards Apr 04 '12 at 10:14