OJ Board

Hello all helper,
I solved 10109 by LUP decomposition algorithm.But i cannot realize by this algorithm when it is no solution.
Am i correct to solve this problem by this algorithm?
Else can anyone suggest another correct algorithm please..?

Yah i also develop LUP-decomposition but cannot realize when Multiple solution or no solution

You can use Gauss Elimination Method for this problem.
So now you can solve this problem.


------------------------------------------------------------------------
Life is nothing but sun is hot

I can't find out what's wrong in my program... I've tried lots of different inputs and all the outputs where ok. But I'm getting WA

My method: Gauss elimination.

After reading the problem again, I've noticed that:

You may assume each of the numerator and denominator part will not exceed the limit of data type long long (64 bit)

Can I assume in all the process all of the numerator and denominator will fit in a long long?? (After modifying a fraction, my program simplifies it)

If it's not this... can someone give me a tricky input?? or can someone check my code?? (I'd send it by email, I don't want to post it here... only 35 people got accepted...)

Thanks for all!

I do feel trouble for such kind of input too.
In some cases u will find input in range of long long
and x[1], x[2], x[3].......x[n] in that range too.
But numerator and denomirator may exeed the range in the cases of
multipliction of guessian.
The best way i think each time devide the numbers which are
going to be multiply/added with the numerator or denomirator,
must be devide by each of those GCD. In that case u will find
small numera. and deno.
BUt in some input this technique fails too
try the following one:

3 3

353 45 29 79
45 29 3 5
29 3 4 8
353 45 29 79

I use Gaussian elimination with my own rational numbers, but I'm getting WA. I am guessing that I have overflow somewhere even with long long numerators and denominators. Can anyone who has solved this give some hints?

I wrote my big rational class (it is not very efficient), and if I have not made any mistake, the intermediate results blow up (I used a fixed size array, good for 160 decimal diigits) and failed with an assert...

Can anyone who got AC share a hint or two?

Finally got AC...I wonder if there was an easy solution. I used pretty complicated stuff to get it to run in time (Chinese remaindering with large primes).

Jalal wrote: BUt in some input this technique fails too
try the following one:

3 3

353 45 29 79
45 29 3 5
29 3 4 8
353 45 29 79

for this my program outputs:

Solution for Matrix System # 1
x[1] = 585/3278
x[2] = -631/3278
x[3] = 1394/1639

is it true?
i used Gauss method... but got TLE
can someone who got Accepted give me inputs for this problem?
thanks!

I used simple Gaussian elimination, representing rationals as a pair
of long long's, and got AC in about 1.5 seconds, so there's no need to do anything complicated here.

how about this I/O ?

input

5
5 3
1 3 3 2 1 5
0 0 3 1 2 1
0 0 0 0 0 0

10
2 4
0 0 0
0 0 0
1 2 1
2 2 2

11
3 3
2 1 1 5
4 -6 0 -2
-2 7 2 9

12
3 3
353 45 29 79
45 29 3 5
29 3 4 8

13
2 4
1 2 1
6/2 1 2
4 3 1
2 1 2

14
3 3
0 0 3 10
0 3 -3 3
2 -1 2 7

15
2 3
1 1 10
1 1 20
2 2 50

18
3 3
2 2 2 2
4 4 4 4
16 16 16 16

20
3 3
1 2 0 3
3 4 4 7
5 6 3 8

22
1 5
1 10
-1 -10
2 20
3 30
5 50

0



output

Solution for Matrix System # 5
Infinitely many solutions containing 3 arbitrary constants.

Solution for Matrix System # 10
x[1] = 1
x[2] = 0

Solution for Matrix System # 11
x[1] = 1
x[2] = 1
x[3] = 2

Solution for Matrix System # 12
x[1] = 585/3278
x[2] = -631/3278
x[3] = 1394/1639

Solution for Matrix System # 13
No solution.

Solution for Matrix System # 14
x[1] = 7/3
x[2] = 13/3
x[3] = 10/3

Solution for Matrix System # 15
No solution.

Solution for Matrix System # 18
Infinitely many solutions containing 2 arbitrary constants.

Solution for Matrix System # 20
x[1] = -7/5
x[2] = 11/5
x[3] = 3/5

Solution for Matrix System # 22
x[1] = 10

david wrote:I used simple Gaussian elimination, representing rationals as a pair
of long long's, and got AC in about 1.5 seconds, so there's no need to do anything complicated here.

I was quite sure that I tried this before and it still blew up for me (assertion failed due to overflow). Perhaps I had a bug in that code and gave up too quickly.

In any case, I computed the answer modulo a number of primes and use Chinese remaindering + rational number reconstruction to get the final results. Have to be careful if you get different ranks under different primes, though.

It would be really helpful is some critical i/o is posted.
I keep getting WA, even though I pass all the cases
on the board and ones I make up.
I use Gauss Jordan elmination.
Overflow is dealt with using BigInteger class with
fast division.

Thanks.

Try the cases.

Input: Output: Some Hint:

1. I used a self-made fraction class.
2. int64 for all calculations.
3. Always saving the fractions such that the numerator and denominator are relatively prime.

Hope these help.

my WA code is here, why got WA???
could someone give me more test case and correct solution?
really need help..

PS. Finally I got AC, and remove my code, I think WA due to wrong blank line during output

Jan wrote:Try the cases.

Input:

Code: Select all

3
4 4
0 1 1 1 3
0 0 0 0 0
0 0 0 1 1
0 1 1 2 9

0

following is my program response:

Code: Select all

Solution for Matrix System # 3
No Solution.

Is it correct?

and my AC code got "No Solution." for Solution for Matrix System # 3 in above case.