10109 - Solving Systems of Linear Equations

[erfan]

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..?

[zing]

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

[zumur]

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


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

[txandi]

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!

[Jalal]

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

[howardcheng]

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?

[howardcheng]

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?

[howardcheng]

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).

[Margarita]

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!

[david]

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.

[DongJoo Kim]

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

[howardcheng]

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.

[baodog]

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.

[Jan]

Try the cases.

Input:

Code: Select all

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

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

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

4
4 4
1/-2 -2/-3 1/-2 6/9 8/12
67/-5 -5/9 0 0 1
0 0 0 1 1
1 0 1 1 7

5
4 8
1/-2 -2/-3 1/-2 6/9 8/12
1/-2 -2/-3 1/-2 6/9 8/12
67/-5 -5/9 0 0 1
67/-5 -5/9 0 0 1
0 0 0 1 1
0 0 0 1 1
1 0 1 1 7
1 0 1 1 7

6
4 5
1/-2 -2/-3 1/-2 6/9 8/12
67/-5 -5/9 0 0 1
0 0 0 1 1
1 0 1 1 7
1 0 1 1 8

0

Output:

Code: Select all

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

Solution for Matrix System # 2
No Solution.

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

Solution for Matrix System # 4
x[1] = -35/134
x[2] = 9/2
x[3] = 839/134
x[4] = 1

Solution for Matrix System # 5
x[1] = -35/134
x[2] = 9/2
x[3] = 839/134
x[4] = 1

Solution for Matrix System # 6
No Solution.

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.

[pfiesteria]

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

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.