2 Special cases of Gaussian [Tutorial]

Правка en40, от MazzForces, 2018-06-18 15:30:43

Hello Codeforces. Today I'm writing about a Math topic that is simple, but resources and problems are very limited on Programming Contest Websites.

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 the variables whose Expected value we need to calculate to be independent. Consider you have N random variables , where , there are cyclic dependencies among the variables for their expected values, i.e consider E(X1) depends on E(X2), E(X2) on E(X3) and E(X3) depends on E(X1). For example, consider the following problem :

You are given Tree T consisting of N nodes. Initially there is a player in node S. In a single move, he moves to one of the adjacent nodes of the node he is currently at, each with equal probability. What is the expected number of moves before he reaches node T ?.

Here, we need to understand that the probabilities are infinite as well as cyclic. Creating a simple formula for the answer is quite hard. The Expected value starting from node S depends on some neighbor of node S, however, the Expected value of some neighbor of node S depends on Expected value of node S. Notice that we can create a transition matrix, as the procedure conducted on the tree is a Markov chain.

Create a matrix P, where P[i][j]= probability of moving from node i to j in a single move. Now, Let E(i) denote the expected number of steps needed to reach node T from node i.

.

Try and take a moment and think about why this formula is correct.

Spoiler

Surprise Surprise, this can be modeled as SLAE. Rewrite equations as :

. So the system is :

\begin{equation} \begin{pmatrix} 1-P[0][0] & -P[0][1] & ... & -P[0][N-1] \newline -P[1][0] & 1-P[1][1] & ... & -P[1][N-1] \newline .... \newline -P[N-1][0] & -P[N-1][1] & ... & 1-P[N-1][N-1] \end{pmatrix} \cdot \begin{pmatrix} E(0) \newline E(1) \newline . \newline . \newline E(n-1) \end{pmatrix} = \begin{pmatrix} 1 \newline 1 \newline .. \newline 1 \end{pmatrix} \end{equation}

This is the equation (IN - PE = 1,We need to find E. Note that for node T, we need to have P[t][i] = 0, t ≠ i and P[t][t] = 1, as we won't move from node T, it is an absorbent state of the markov chain. So, the Tth row of matrix IN - P will be all zeros. Just remove it from both sides of the equation.

Now, we know that unique expected values exist. (Obviously, they exist, that is the problem given). So, just take the matrix to RREF, to get the expected values. We have obtained E(i) for all 0 ≤ i ≤ N - 1, i ≠ T

We can use this generic technique in all cases where the expected values are cyclic in nature , i.e expected value of state A depends on state B, and expected value of state B depends on state A. We can use any prime mod too, to obtain expected value in Modulo.

Practice Problems :

One (Same problem as above) My Code

Two

Problem 2 : Xor's using SLAE

Pr-requisite : Vector Space properties, Linear Algebra.

Without reading the link, proceed at your own risk.

mod 2

mod 2

mod 2

So, xor is just bit-wise addition mod 2. We can represent the xor of two integer's x, y as vector addition in . For example ,

i.e. ,

\begin{equation} \begin{pmatrix} 0 \newline 1 \newline 0 \end{pmatrix} + \begin{pmatrix} 1 \newline 1 \newline 1 \end{pmatrix} \equiv \begin{pmatrix} 1 \newline 0 \newline 1 \end{pmatrix}
Mod \space 2
\end{equation}

So, we can use this addition to replace xor. Now, imagine the following two class of problems :

1> Given a set S of size N, find the number of distinct integers that can be represented using xor over the set of the given elements.

Solution

2> How many subsequences of a given set S of size N have xor equal to X. (Do it yourself).

All of these problems can be modeled using SLAE in Mod 2. We can do operations faster in Mod 2 using bitset having complexity .

Problems :

One

Two

Теги 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)