10109  Solving Systems of Linear Equations
Moderator: Board moderators

 New poster
 Posts: 44
 Joined: Tue Apr 15, 2003 4:31 pm
 Location: Chittagong,Bangladesh
 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..?
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..?
10109
You can use Gauss Elimination Method for this problem.
So now you can solve this problem.

Life is nothing but sun is hot
So now you can solve this problem.

Life is nothing but sun is hot
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:
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!
My method: Gauss elimination.
After reading the problem again, I've noticed that:
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)You may assume each of the numerator and denominator part will not exceed the limit of data type long long (64 bit)
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
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

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am
for this my program outputs: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
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!

 New poster
 Posts: 20
 Joined: Tue Sep 20, 2005 9:20 am
 Location: Daejeon, Korea
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
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

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am
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.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.
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.
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.
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 selfmade fraction class.
2. int64 for all calculations.
3. Always saving the fractions such that the numerator and denominator are relatively prime.
Hope these help.
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
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.
1. I used a selfmade 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
HomePage

 New poster
 Posts: 9
 Joined: Mon Aug 13, 2007 7:45 am
why WA?
PS. Finally I got AC, and remove my code, I think WA due to wrong blank line during outputmy WA code is here, why got WA???
could someone give me more test case and correct solution?
really need help..
and my AC code got "No Solution." for Solution for Matrix System # 3 in above case.Jan wrote:Try the cases.
Input:following is my program response: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
Is it correct?Code: Select all
Solution for Matrix System # 3 No Solution.
Last edited by pfiesteria on Mon Oct 12, 2009 4:10 pm, edited 1 time in total.