nerd's blog

System of Algebraic Linear Equations
By nerd, 13 years ago, In English

In which problems we can use solving System of algebraic linear equations, such as by Gauss' method?

Is there any problems(not theoretical)?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Some geometry, I guess.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Ok, let's change question:
"if gauss' method is used in normal contests, that is acm, ioi, codeforces, topcoder, ...?"
"if you have such problems, please give me link".
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I saw problem "solve the system of linear equations" and only.
    May be some more advanced and red users can give other examples.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I've seen many "Probability" and "Expected Value" related problems which can be solved using Gaussian method. 
    A simple example: Starting from (0, 0) in a MxN grid and walking randomly with given probabilities, what's expected number of steps to visit (0, 0) for the second time? If you write the relations, you'll see that they constitute a system of linear equations.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Problem 1: http://www.spoj.pl/problems/GS/

    Problem 2: There was also one on Topcoder but I can't remember which SRM it was so here is a brief description for the problem statement:
    You have N bulbs and N buttons. At the beginning all the bulbs are switched off. Each button can change the state of some of the bulbs. Given N and the bulbs each button affects, return the least number of buttons needed from these buttons such that you can reach all the possible configurations you can reach using any combination of the N buttons. (1 <= N <= 50).

    Problem 3: There is also the direct type:
    http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=2742

    P.S. In the last one the sample input is incorrect, here is the correct one:
    2 2 1 
1 1 
1 1 

3 3 1 
19 14 20 
12 15 18 
13 14 16 

4 4 2 
14 15 14 15 
14 15 14 15 
14 15 14 15
14 15 14 15
0 0 0
     
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think Omar was refering to this problem

Simliar one: Square

Besides, LIM of SPOJ is a cyclic probability problem. NWERC04H, which should be solved using gaussian elimination modulo P.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
East Central Regional 2010 for North America ACM ICPC problem H
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I know three more from spoj -> WIDGET, AE1B and CHARLIE.
They all use some sort of modulo field.
There's another Markov Chain kind of problem -> MARIOGAM, also on spoj.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
One from Spoj : problem

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
http://acm.sgu.ru/problem.php?contest=0&problem=260

→ Reply