SLAE Problems for Competitive Programming [Tutorial]

Revision en6, by MazzForces, 2018-06-13 22:40:02

Hello Codeforces.

SLAE stands for system of linear equations. Basically, consider we have a set of equations of the form :

a0·x0 + a1·x1 + a2·x2 + ... + an - 1·xn = m

b0·x0 + b1·x1 + b2·x2 + .... + bn - 1·xn - 1 = n

c0·x0 + c1·x1 + c2·x2 + .... + cn - 1·xn - 1 = o

.....

Note that all a, b, c... are real-valued arrays and all m, n, o are arbitrary reals. Realize how x0, x1, ...xn - 1 appear in each of the equations.

Now, we want to find values of [x0, x1...xn - 1] that satisfy each of the given equations listed. The simplest method to find such solutions is to use Gaussian Elimination, that solves the problem in O(N3), where N = number of equations = number of variables .

To Learn about Gaussian Elimination, click here. Today, we shall learn about 2 special class of problems that can be solved using Gaussian Elimination for SLAE.

Problem 1 : Markov Chains and Cyclic Expected Values :

Many a times as a part of expected value problems, you are expected to sum up infinite series that hold as limits, as probabilities lie in the closed interval [0, 1]. For example,

, as

However, not always can we expect to reach such simple sums. Consider the following example :

Tags gauss elimination, #math, xor

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en66 English MazzForces 2018-07-12 14:00:20 4
en65 English MazzForces 2018-06-29 19:00:27 23
en64 English MazzForces 2018-06-29 17:43:14 8
en63 English MazzForces 2018-06-29 16:20:35 30
en62 English MazzForces 2018-06-29 16:18:29 19
en61 English MazzForces 2018-06-29 04:16:09 24
en60 English MazzForces 2018-06-28 19:10:43 0 (published)
en59 English MazzForces 2018-06-26 13:36:11 174
en58 English MazzForces 2018-06-23 15:26:12 20
en57 English MazzForces 2018-06-23 14:43:15 145
en56 English MazzForces 2018-06-23 14:41:38 305
en55 English MazzForces 2018-06-21 14:36:53 25
en54 English MazzForces 2018-06-21 14:35:52 10
en53 English MazzForces 2018-06-19 16:10:21 10
en52 English MazzForces 2018-06-19 16:01:40 57
en51 English MazzForces 2018-06-19 14:48:09 35
en50 English MazzForces 2018-06-19 14:44:05 10
en49 English MazzForces 2018-06-19 14:42:50 1147
en48 English MazzForces 2018-06-19 14:20:26 300
en47 English MazzForces 2018-06-19 02:52:44 46
en46 English MazzForces 2018-06-19 02:51:31 311
en45 English MazzForces 2018-06-19 02:39:49 397
en44 English MazzForces 2018-06-18 18:38:16 95
en43 English MazzForces 2018-06-18 18:35:15 449
en42 English MazzForces 2018-06-18 18:25:37 1
en41 English MazzForces 2018-06-18 18:22:47 419
en40 English MazzForces 2018-06-18 15:30:43 1
en39 English MazzForces 2018-06-18 15:28:38 25
en38 English MazzForces 2018-06-18 15:26:54 28
en37 English MazzForces 2018-06-18 15:24:44 2
en36 English MazzForces 2018-06-18 15:23:06 77
en35 English MazzForces 2018-06-18 15:18:55 192
en34 English MazzForces 2018-06-18 13:28:47 11
en33 English MazzForces 2018-06-18 13:27:50 183
en32 English MazzForces 2018-06-18 13:25:45 10
en31 English MazzForces 2018-06-18 13:24:22 258
en30 English MazzForces 2018-06-18 13:21:38 46
en29 English MazzForces 2018-06-14 01:37:31 49
en28 English MazzForces 2018-06-14 01:36:14 23
en27 English MazzForces 2018-06-14 01:34:56 351
en26 English MazzForces 2018-06-14 01:29:07 122
en25 English MazzForces 2018-06-14 01:26:02 3
en24 English MazzForces 2018-06-14 01:25:29 10
en23 English MazzForces 2018-06-14 01:23:41 10
en22 English MazzForces 2018-06-14 01:22:47 2
en21 English MazzForces 2018-06-14 01:21:08 616
en20 English MazzForces 2018-06-14 01:12:44 8
en19 English MazzForces 2018-06-14 01:12:20 30
en18 English MazzForces 2018-06-14 01:10:35 26
en17 English MazzForces 2018-06-14 01:09:47 296
en16 English MazzForces 2018-06-14 01:05:44 435
en15 English MazzForces 2018-06-14 00:49:59 33
en14 English MazzForces 2018-06-14 00:46:47 561
en13 English MazzForces 2018-06-14 00:39:17 725
en12 English MazzForces 2018-06-13 23:57:55 3
en11 English MazzForces 2018-06-13 23:57:32 4
en10 English MazzForces 2018-06-13 23:57:00 48
en9 English MazzForces 2018-06-13 23:44:26 6
en8 English MazzForces 2018-06-13 23:43:54 916
en7 English MazzForces 2018-06-13 23:18:06 1008
en6 English MazzForces 2018-06-13 22:40:02 42 Tiny change: ' as $ \lim{ x \to \inft} i^x =0 $' -> ' as $ \lim_{ x \to \infty} i^x =0 $'
en5 English MazzForces 2018-06-13 16:14:26 8 Tiny change: 'n-1} \cdot3000000 x_{n-1} =' -> 'n-1} \cdot x_{n-1} ='
en4 English MazzForces 2018-06-13 16:13:54 385 Tiny change: 'expect to calculate such sums. Con' -> 'expect to reach such simple sums. Con'
en3 English MazzForces 2018-06-13 12:57:35 532
en2 English MazzForces 2018-06-13 12:49:16 239 Tiny change: 'Codeforces,\n\nSLAE s' -> 'Codeforces.\n\nSLAE s'
en1 English MazzForces 2018-06-13 12:43:24 594 Initial revision (saved to drafts)