10109 - Solving Systems of Linear Equations

Moderator: Board moderators

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:

10109 - Solving Systems of Linear Equations

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
New poster
Posts: 3
Joined: Wed Dec 10, 2003 8:44 am
Yah i also develop LUP-decomposition but cannot realize when Multiple solution or no solution
zingzung

zumur
New poster
Posts: 1
Joined: Mon Dec 15, 2003 7:48 am
Contact:

10109

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

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

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

10109

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
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
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
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:
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!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
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
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea

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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
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.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Can someone post some critical i/o??

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

pfiesteria
New poster
Posts: 9
Joined: Mon Aug 13, 2007 7:45 am

why WA?

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.
Last edited by pfiesteria on Mon Oct 12, 2009 4:10 pm, edited 1 time in total.