Discussion @ 1361. Spaceology vs. Chronistics @ Timus Online Judge

semiconductor Spaceology vs. Chronistics: I am stuck on test #55 [7] // Problem 1361. Spaceology vs. Chronistics 23 Apr 2005 22:02

My solution is like this:
We find the paths of A && B. Definitely A && B will enter some circular path eventually. We assign to every junction(for A && B separately):
1. "pos" if this junction is traversed only once(before A || B enters his circular path)
2. "(pos,period)" if it appears in the circular path, where pos is the first occurrence of the junction,and period is the length of the circular path
3. "-1" if it is never visited
Then for every junction we check whether its position(s) for A will meet B's. We may need to solve the equation:
pos_A + period_A * x == pos_B + period_B * y
where x,y >= 0 && the value on each side is minimum
This can be done with euclid's method.

However I am stuck on test#55. I have disposed all of my energy to find the tricky case but ended up with no result.
Please help!

Edited by author 23.04.2005 22:04

Vladimir Yakovlev (USU) Your algo is right [3] // Problem 1361. Spaceology vs. Chronistics 24 Apr 2005 14:02

I solved this problem in the same way and get AC
link: http://acm.timus.ru/status.aspx?space=1&pos=811782

semiconductor Re: Your algo is right [2] // Problem 1361. Spaceology vs. Chronistics 24 Apr 2005 19:08

Have you used int64 for the intermediate result?
I suspect I've got some kind of overflow
Thx

Kit Re: Your algo is right // Problem 1361. Spaceology vs. Chronistics 24 Apr 2005 19:55

Of course, there are may be very big numbers!
if period_A = 99999, period_B = 99998 and pos_B - pos_A = 99997, we have almost 100000^2.
Good luck!

Vladimir Yakovlev (USU) Yes, I made all calculations in int64 // Problem 1361. Spaceology vs. Chronistics 25 Apr 2005 13:12

semiconductor Re: Spaceology vs. Chronistics: I am stuck on test #55 [2] // Problem 1361. Spaceology vs. Chronistics 26 Apr 2005 19:24

I still can't pass #55
Now I suspect I made something wrong when solving
pos_A + period_A * x == pos_B + period_B * y using euclid's method
My method goes like this
(short hands: pos_A: n1, pos_B: n2, period_A: a, period_B: b)
So we want to solve n1 + ax == n2 + by, such that x, y >= 0 && n1 + ax is minimized
if n1 >= n2, we just solve
   by - ax == n1 - n2, such that x, y >= 0 && x is minimum
else
   ax - by == n2 - n1, such that x, y >= 0 && y is minimum
Here's my code for solving
ax - by == n, such that x, y >= 0 && y is minimum
( which equals to solve:
by == a - n mod a (mod a) )

!! I am sorry for the readablility of the code since I don't know how to make the code look like indented. You can use my account 36057RJ to edit this msg and get indented code
################################
typedef typedef __int64 LL;
LL
Gcd(LL a, LL b, LL *x, LL *y)
{
    if ( b == 0 ) {
        *x = 1;
        *y = 0;
        return a;
    } else {
        LL xx, yy;
        LL gcd = Gcd(b, a % b, &xx, &yy);
        *x = yy;
        *y = xx - (a / b) * yy;
        return gcd;
    }
}
LL
SolveLinear(LL a, LL b, LL n)
{
    LL result;
    LL x, y;
    LL q;
    LL d = Gcd(b, a, &x, &y);
    n = (a - n % a) % a;
    if ( n % d != 0 )
        return -1;
    x *= n / d;
    q = a / d;
    result = x % q;
    if ( result < 0 )
        result += q;
    return result;
}
####################################
Is this the right thing to do ?
Thanks in advance for taking your time to
check this

Edited by author 26.04.2005 19:31

Safe Bird Interestingly, I got WA on 55 too. I'm checking it over now. // Problem 1361. Spaceology vs. Chronistics 1 May 2005 09:22

Love_xx I still can't pass it. I'm sure that I solved such equation correctly.... // Problem 1361. Spaceology vs. Chronistics 1 May 2005 09:59

Discussion of Problem 1361. Spaceology vs. Chronistics