Блог пользователя nerd

System of Algebraic Linear Equations
Автор nerd, 13 лет назад, перевод, По-русски

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

Is there any problems(not theoretical)?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Some geometry, I guess.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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".
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I saw problem "solve the system of linear equations" and only.
    May be some more advanced and red users can give other examples.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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
     
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

http://acm.timus.ru/problem.aspx?space=1&num=1766
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
East Central Regional 2010 for North America ACM ICPC problem H
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
One from Spoj : problem

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://acm.sgu.ru/problem.php?contest=0&problem=260

→ Ответить