### nerd's blog

By nerd, 8 years ago, ,

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

Is there any problems(not theoretical)?

 8 years ago, # |   0 Some geometry, I guess.
•  8 years ago, # ^ |   0 could you be more specfic?i mean can u give examples or something like this. or links
•  8 years ago, # ^ |   0 Intersection of k n-dimensional spheres =)
•  8 years ago, # ^ | ← Rev. 5 →   0
•  8 years ago, # ^ |   0 About this problem:  sgu : 275You can also solve it by Gauss when minimum value is required (assuming that you must take at least one A, otherwise the answer is always 0).
•  8 years ago, # ^ |   0 Can you explain how to solve sgu : 275 using Gaussian elimination or give some hints ?
 8 years ago, # |   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".
•  8 years ago, # ^ |   0 I saw problem "solve the system of linear equations" and only.May be some more advanced and red users can give other examples.
•  8 years ago, # ^ |   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.
•  8 years ago, # ^ | ← 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=2742P.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
 8 years ago, # |   0 I think Omar was refering to this problemSimliar one: SquareBesides, LIM of SPOJ is a cyclic probability problem. NWERC04H, which should be solved using gaussian elimination modulo P.
 8 years ago, # |   0 East Central Regional 2010 for North America ACM ICPC problem H
 8 years ago, # |   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.
 8 years ago, # | ← Rev. 2 →   0 One from Spoj : problem
 8 years ago, # |   0 @Verdona0   the problem http://www.spoj.pl/problems/XMAX/  is it a simple Xor??? or how dou you use System of Algebraic Linear Equations ???
 8 years ago, # |   0