Gaussian Elimination lecture

Gaussian Elimination

pronounce with 's', not 'sh'
solve a system of two equations
solve a system of three equations
talk about matrix representation
show a general algorithm
simulate on the same system of three equations
precision issues, pivot
usually computed modulo P, same but with modular inverse
binary version
example explained here https://en.wikipedia.org/wiki/Gaussian_elimination
practical programming use https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
think: does the answer always exist modulo P?
- x * 1000000007 = 5 has a solution for real values, doesn't for P=1e9+7

Real values, N, a[i] <= 5, exactly one solution, error 1e-4, print the one solution
N <= 100 modulo P, say 0 or 1 or many solutions

number of XORS of subsets, N <= 5e5, a[i] <= 1e18
XOR maximization https://www.spoj.com/problems/XMAX/
Zero XOR Subset https://codeforces.com/contest/1101/problem/G
You are given a sequence of integers (N <= 10^5, a[i] <= 10^9) and there are two players. First Alice removes some numbers and then Bob removes some of the remaining numbers but can't remove everything. Then they play a NIM game, Alice starts. How many numbers at least should Alice remove in order to ensure the victory in NIM game later? This is a very simplified problem Magic Matches Game https://community.topcoder.com/stat?c=problem_statement&pm=11676 .
Same problem but every number has a price of removing b[i]. This time Alice pays for removing numbers and needs to minimize the total cost.

Ivan and Burgers https://codeforces.com/contest/1100/problem/F
SumOfXor (non-trivial!) https://community.topcoder.com/stat?c=problem_statement&pm=14348
Process Q <= 100,000 updates of two types: insert and remove element x (x <= 10^6). Print basis size after every update.

complexity

O(Q*log^3) with a segment tree

You are given a small directed graph (N, M <= 15). We start at vertex 1. In every move we use a random edge going out of the current vertex. Find the expected value of number of moves before we get to vertex N. You can get from 1 to all vertices and from all to vertex N.
- Consider switching to probability: some vertices kill you, compute probability of not-dying.
https://open.kattis.com/problems/lostinthewoods
Snakes and Ladders https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4775
probability, Frog in grid https://www.hackerrank.com/challenges/frog-in-maze/problem
https://csacademy.com/contest/round-52/task/an-unstable-graph/statement/ and this is another reason why organizers shouldn't require real values (modulo would prevent my stupid solution BUT maybe the answer wouldn't exist?)

ev[1] = x

ev[1] = ... * ev[2] + ... * ev[1] -> ev[2] = a * x + b

0.6 forward, else backward by 1

ev[1] = x ev[2] = 5 * x + 10 ...

ev[5] = p1 * ev[6] + p2 * ev[4] + p3 * ev[3] + const ev[6] = (p2 * ev[4] + p3 * ev[3] - ev[5]) / p1 + const why SUM can't be 0?

N levels in a video game, always probability 1/3 of moving forward by 1, backward by 1 or to level 1. Compute EV of finishing the last level.
KMP https://acm.timus.ru/problem.aspx?space=1&num=1677 (BUT THE MAIN DIFFICULTY IS HUGE ANSWER!)
https://codeforces.com/problemset/problem/1265/E & https://codeforces.com/contest/1264/problem/C