SLAE Problems for Competitive Programming [Tutorial]

Правка en6, от 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 :

Теги gauss elimination, #math, xor

История

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