Editorial for Danger at the Marks

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

The input provides a matrix $A$ . We can see that $A^k_{i,j}$ gives us the probability of ending at position $j$ after $k$ steps, when starting from position $i$ .

For a given start $s$ :

$E[\text{Collisions}] = \sum_t \Pr[\text{Collision at time } t]$

(by linearity of expectation)

$= \sum_t \sum_{i=1}^{n} A^t_{s,i} A^t_{1,i}$ .

A collision at time $t$ occurs precisely when Eric and Lucas occupy the same mark. They move independently, so the probability they both land at mark $i$ is $A^t_{s,i} A^t_{1,i}$ , and summing over $i$ gives the probability of a collision. The same sum is the $(s, 1)$ entry of $A^t (A^t)^\top$ , since

$(A^t (A^t)^\top)_{s,1} = \sum_{i=1}^{n} A^t_{s,i} ((A^t)^\top)_{i,1} = \sum_{i=1}^{n} A^t_{s,i} A^t_{1,i}$ .

The expectation is then $\sum_t (A^t (A^t)^\top)_{s,1}$ . Matrix addition is entrywise, so this is the $(s, 1)$ entry of $\sum_t A^t (A^t)^\top$ . (It turns out, entry $(x, y)$ gives us the EV for Lucas starting at $x$ , and Eric starting at $y$ .)

Naively calculating this takes $O(n^3 k)$ , which is not fast enough. We can find a recurrence to speed this up.

Define $f(k)$ to equal the sum from $1$ to $k$ :

$f(k) = \sum_{t=1}^{k} A^t (A^t)^\top$ .

$f(0)$ is the zero matrix.

$f(k) = A f(k - 1) A^\top + A A^\top$ when $k$ is odd.

$f(k) = A^{k/2} f(k/2) (A^\top)^{k/2} + f(k/2)$ when $k$ is even.

Using this recurrence, and being careful to calculate all required powers of $A$ with $\log k$ matrix multiplications, we can evaluate $f$ in $O(n^3 \log k)$ .

Solution (C++)

Code 1

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define nl '\n'
#define fr first
#define sc second
typedef long long ll;
typedef pair<int, int> pii; typedef vector<int> vi;

const ll mod = 1e9 + 7;

ll modpow(ll a, ll p) {
	ll res = 1;
	while(p) {
		if (p&1)res=res*a%mod;
		a=a*a%mod;
		p/=2;
	}
	return res;
}

const ll inv100 = modpow(100, mod-2);
typedef vector<array<ll,100>> mat;
int n;

mat matmul(const mat &a, const mat &b) {
	mat res(n);
	rep(i,0,n) rep(j,0,n) rep(k,0,n) {
		(res[i][j] += a[i][k] * b[k][j]) %= mod;
	}
	return res;
}

mat matadd(const mat &a, const mat &b) {
	mat res(n);
	rep(i,0,n) rep(j,0,n) res[i][j] = (a[i][j] + b[i][j])%mod;
	return res;
}

// :3
mat trans(const mat &a) {
	mat res(n);
	rep(i,0,n) rep(j,0,n) {
		res[i][j] = a[j][i];
	}
	return res;
}

mat id;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	ll k;
	cin >> n >> k;

	id = mat(n);
	rep(i,0,n) id[i][i] = 1;

	mat graph(n);

	rep(i,0,n) rep(j,0,n) {
		cin >> graph[i][j];
		(graph[i][j] *= inv100) %= mod;
	}


	mat grapht = trans(graph);

	// graph^k, sum
	auto recurse = [&](auto && self, ll k) -> array<mat,2> {
		if (k == 0) return {id, mat(n)};
		if (k % 2 == 0) {
			auto [ha,sum] = self(self, k/2);
			auto a = matmul(ha,ha);
			auto nw = matmul(matmul(ha, sum), trans(ha));
			nw = matadd(nw, sum);

			return {a,nw};
		} else {
			auto [ha,sum] = self(self,k-1);
			auto a = matmul(ha,graph);
			auto nw = matmul(matmul(graph,sum),grapht);
			nw = matadd(nw, matmul(graph,grapht));
			return {a,nw};
		}
	};

	auto [a,res] = recurse(recurse,k);
	rep(i,1,n) cout << res[i][0] << " \n"[i == n - 1];
}

Comments0

No comments yet

Be the first to comment.

Editorial for Danger at the Marks

Approach

Solution (C++)

Comments0

New comment