0
$\begingroup$

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.They will be my answer for this problem.

I tried using the same technique in my C++ code but it's not working.

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/

Thanks in advance.

$\endgroup$
1
$\begingroup$

Hint $\rm\ A\:\mathbb Z + B\:\mathbb Z = \gcd(A,B)\:\mathbb Z,\ \ C\:\mathbb Z + D\: \mathbb Z = \gcd(C,D)\:\mathbb Z.\:$ An integer is in both of these sets iff it is divisible by both $\rm\:\gcd(A,B)\:$ and $\rm\:\gcd(C,D)\:$ iff it is divisible by their LCM.

For example, consider the third test case: $\rm\:A,B,C,D,K = 10,12,3,9,16.\:$ We have $\rm\:gcd(10,12) = 2,\:$ and $\rm\:\gcd(3,9)=3,\:$ and $\rm\:lcm(2,3) = 6,\:$ so their are $\rm\:\lfloor 16/6\rfloor = 2\:$ positive integers $\le 16$ divisible by both $2,3,\:$ and $2$ negative integers $\ge -16,\:$ so, with $0$, there are $5$ total in the interval $[-16,16].$

$\endgroup$
8
  • $\begingroup$ Yeah In fact that's what I'm thinking but don't know where I'm lagging.You can take a look at my code.I have done the same thing.But still keep getting wrong answer. $\endgroup$ – code_hacker Apr 2 '12 at 16:10
  • $\begingroup$ If you're simply trying to debug your code then trace it in on test example to determine the precise spot where it goes wrong. But that's not really a mathematical question. $\endgroup$ – Bill Dubuque Apr 2 '12 at 16:24
  • $\begingroup$ I have already done testing part,not only on the given input but also my own input as far as I can test it manually But not abled to find a test case that gives me wrong answer.So,I thought the concept that I'm using (diophantine-equations) might be wrong.I posted this question so that someone with a better knowledge can cross-check it which is a mathematical question. $\endgroup$ – code_hacker Apr 2 '12 at 16:32
  • $\begingroup$ It took me a while to decipher the question. (+1) for that, at least :-) $\endgroup$ – robjohn♦ Apr 2 '12 at 16:34
  • $\begingroup$ @code_hacker I explained the underlying mathematics, and you confirmed that is what your code employs. Further, you say your code gives the correct answer on the test cases. So why do you think there is any problem with your implementation? Are you trying to mathematically prove that the implementation is correct? $\endgroup$ – Bill Dubuque Apr 2 '12 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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