SRM 653 DIV 1
CountryGroupHard http://community.topcoder.com/stat?c=problem_statement&pm=13688&rd=16317&rm=325529&cr=23296695 Solution Dynamic Programming Definitions A** group** is a list of people from the same country sitting together. The last person of a group is the one with largest index. Transition Function Let’s consider the number of valid arrangements of first person to the i-th person when i-th person is the last person of a group \(f(i) = \begin{cases} 0 & \text{the number of valid arrangements of 1...i is 0} \\ 1 & \text{the number of valid arrangements of 1...i is 1} \\ 2 & \text{the number of valid arrangements of 1...i is larger than 1} \end{cases}\) Let’s define \(g(i) = \begin{cases} \sum\limits_{k=1}^{100} valid(i,k), & \text{if } a[i]=0 \\ valid(i,a[i]), & \text{if } a[i]\neq 0 \\ \end{cases}\) g(i) sums up all possible arrangements of 1..i given i is the last person of a group. and \(valid(i,k)= \begin{cases} 1 & \text{if } i-k\geq 0 \land (\forall j \in [i-k+1,i] \: , \: a[j]=0 \lor a[j]=k)\\ 0 & \text{otherwise } \end{cases}\) valid(i,k) check if is possible to set a[i] to k. then the transitions will be \(f(i) = \begin{cases} 0 & \text{if } g(i)=0\\ 1 & \text{if } g(i)=1\\ 2 & \text{if } g(i) > 1 \end{cases}\) and the base case \(f(0)=1\) since there is only one way to arrange an empty list. Time complexity is \[O(N^3)\]. My solution https://github.com/hujiewang/Programming-Contests/blob/master/topcoder/SRM%20653%20DIV%201/CountryGroupHard.cpp
Singing http://community.topcoder.com/stat?c=problem_statement&pm=13680&rd=16317&rm=325529&cr=23296695 Solution Reducing to Min-Cut and solve it by calculating Max-Flow Observation Given an assignment, the number of switches is equal to \(\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{i-1} c[j][i] \: \text{if pitch i and j are assigned to different persons}\) where \[ c(i,j)=\] how many times that pitch i and pitch j are adjacent Therefore we can build a graph where the capacity of the edge between each pair of vertices i and j is c[i][j] (\[i\neq j\]). Note that those edges need to be bidirectional since we cannot determine the flow direction in advance. Let’s create a source for Alice and a sink for Bob, and connect source to all vertices with pitches that can only be sang by Alice. Similarly, connect all vertices with pitches that can only be sang by Bob to sink, set capacities of these edges to \[\infty\]. The reason behinds this is that we need to group all pitches that can only be sang by Alice or Bob together (Note that Connecting source or sink to a vertex with \[\infty\] capacity implies that that vertex and source/sink are in the same partition, thus these vertices are in the same partition) Then the Min-Cut is exactly what we need. Push-Relabel is fast enough to compute the Max-Flow and the time complexity is \[O(N^3)\]. My solution https://github.com/hujiewang/Programming-Contests/blob/master/topcoder/SRM%20653%20DIV%201/Singing.cpp