Problem Statement:
514E - Darth Vader and Tree
Solution:
Learnt something new! A very clever idea to use fast matrix exponentiation to solve for the DP states. Check the official editorial for a better understanding :) (Thank you for the enlightenment!)
Let V(m) be the number of vertices that are located exactly m unit distance away from root. Hence we can have the following relationship: \(V(m) = \sum_{i=0}^{100} c[i] V(m-i) \), where c[i] is the number of edges with length i amongst the n edges. What we want to find is \(S(x) = \sum_{i=0}^{x} V(x) \). The clever idea is to transform these equations into matrix multiplications!
Showing posts with label Fast Matrix Multiplication. Show all posts
Showing posts with label Fast Matrix Multiplication. Show all posts
Wednesday, February 18, 2015
Saturday, November 8, 2014
Codeforces #276 (Div. 1) Problem C: Strange Sorting
Problem Statement:
484C - Strange Sorting
Solution:
This is an awesome problem. Good stuff.
The first thing to notice is that that the length of string n and the number of queries is bounded by \(nm \leq 10^6\). What happens if \(n = 10^6\)? In this case for \(K\) large enough, the running time of pure simulation of the operations will take too much time.
The great idea that is suggested by the problem setter (Codeforces handle: Bugman. You are awesome) is to think of each sorting operations as permutations on the string, which it indeed is. The good thing about permutation is that we can represent it in an NxN elementary matrix (which only has one "1" in each rows and each columns, and "0" everywhere else). Let's call this permutation matrix as P. Then each shuffling operations can be seen as matrix multiplications of S and \(P^n\). So if we can find a matrix P to represent the d-sorting on S at different substring of S, we can proceed with doing a fast matrix multiplication of \(P^n\) which takes \(O(N\lg{n})\), which also marks the bound for the running time of each query (Btw, the matrix multiplication itself in general is \(O(N^3)\), but since the matrices multiplied are elementary, we only need \(O(N)\) time, and it is quite fun to figure out how to do it :D).
484C - Strange Sorting
Solution:
This is an awesome problem. Good stuff.
The first thing to notice is that that the length of string n and the number of queries is bounded by \(nm \leq 10^6\). What happens if \(n = 10^6\)? In this case for \(K\) large enough, the running time of pure simulation of the operations will take too much time.
The great idea that is suggested by the problem setter (Codeforces handle: Bugman. You are awesome) is to think of each sorting operations as permutations on the string, which it indeed is. The good thing about permutation is that we can represent it in an NxN elementary matrix (which only has one "1" in each rows and each columns, and "0" everywhere else). Let's call this permutation matrix as P. Then each shuffling operations can be seen as matrix multiplications of S and \(P^n\). So if we can find a matrix P to represent the d-sorting on S at different substring of S, we can proceed with doing a fast matrix multiplication of \(P^n\) which takes \(O(N\lg{n})\), which also marks the bound for the running time of each query (Btw, the matrix multiplication itself in general is \(O(N^3)\), but since the matrices multiplied are elementary, we only need \(O(N)\) time, and it is quite fun to figure out how to do it :D).
Subscribe to:
Posts (Atom)