Tävlingsprogrammering/Uppgifter/Orkesteroptimering

Uppgift

https://po.scrool.se/problems/orkester

Lösning

För att förstå lösningen på det här problemet är det rekommenderat att man förstår sig på matchningar i bipartita grafer, och hur man kan hitta maximala matchningar genom dfs-matchning. Man kan exempelvis läsa om det här: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

Det här problemet är lämpligt att representera med en graf, så vi ska skapa en på följande sätt:

1. Vi börjar med att skapa en nod för varje musiker och en för varje takt. För enkelhets skull kan musikerna ritas på vänster sida och takterna till höger (grafen kommer att vara bipartit så detta är ett bra sätt att representera den).
2. Från varje musiker så skapar vi en kant till varje takt som han/hon kan spela. Notera att inga kanter skapas mellan två musiker eller två takter, vilket garanterar att grafen blir bipartit.

Om varje musiker endast var tillåten att spela en enda takt så hade problemet varit ekvivalent med att hitta en maximal bipartit matchning i denna graf. Nu är så inte fallet men maximal bipartit matchning är ändå en stor del av lösningen.

Om vi börjar med att hitta en maximal bipartit matchning i grafen så har vi löst problemet där varje musiker endast får spela en enda takt. Vi vill nu utöka denna lösning till fallet där varje person kan spela upp till två takter (och sedan vidare tills dess att alla får spela så mycket de vill och vi har en lösning till ursprungsproblemet). Att varje musiker tillåts spela ytterligare en takt går att visualisera genom att lägga till en kopia av varje musiker i varje steg, så istället för att t.ex. ha en musiker som tillåts spela 3 takter så har vi 3 identiska musiker som alla får spela en takt var.

Vi kan direkt konstatera att en optimal lösning alltid kommer att innehålla T takter, där T är antalet takter som kan spelas av någon av musikerna. Har vi en lösning med mindre än T takter så kan vi alltid förbättra den genom att spela en takt till. Detta, tillsammans med faktumet att oväsendet V är strikt minskande för varje musiker då han/hon spelar fler takter, innebär att det alltid är optimalt att matcha så många takter som möjligt i varje steg. Säg att vi har två lösningar X och Y som båda har T matchade takter, och att de i steg t hade matchat x respektive y takter. Om y < x så måste Y matcha åtminstone 2 takter mer än X i de resterande stegen, vilket motsäger det faktum att båda matchar T takter i slutändan. Alltså får vi ett optimalt svar genom att i varje steg lägga till en kopia av varje musiker och göra en maximal matchning i den nya grafen (där varje ny matchad takt tillför 1/t till svaret om vi är i steg t). Notera att vi inte bokstavligen behöver lägga till nya kopior av musikerna men det lönar sig att se det på det sättet.

Vidare är det lätt att inse att om vi misslyckats med att matcha en musiker med någon takt i ett steg så kommer det misslyckas i alla efterföljande steg också. Vi behöver alltså genomföra högst N + M stycken matchningsförsök, ett lyckat för varje takt samt ett misslyckat för varje musiker. Detta ger en algoritm med körtid O((N+M)*K), där K är antal kanter i grafen.

Lösning i Java:

package orkester;
import java.util.*;
import java.io.*;

public class OrkesterOptimering {
	
	static int M, N;
	static int[] matchedBy;
	static boolean[] visited;
	static LinkedList<Integer>[] g;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		solve(in, out);
	}
	
	static void solve(BufferedReader in, PrintWriter out) throws IOException {
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		g = new LinkedList[M];
		for (int i = 0; i < M; i++) {
			g[i] = new LinkedList<Integer>();
			st = new StringTokenizer(in.readLine());
			int T = Integer.parseInt(st.nextToken());
			for (int j = 0; j < T; j++) {
				g[i].add(Integer.parseInt(st.nextToken()) - 1);
			}
		}
		
		matchedBy = new int[N];
		Arrays.fill(matchedBy, -1); // Inga takter är matchade i början
		
		double res = 0;
		LinkedList<Integer> q = new LinkedList<Integer>();
		for (int i = 0; i < M; i++) q.add(i);
		int[] timesPlayed = new int[M];
		visited = new boolean[M];
		while (!q.isEmpty()) {
			Arrays.fill(visited, false);
			int v = q.removeFirst();
			visited[v] = true;
			timesPlayed[v]++;
			for (int u : g[v]) {
				if (match(u)) { // Vi lyckades matcha musiker v med takt u
					res += 1d/timesPlayed[v];
					matchedBy[u] = v;
					q.add(v);
					break;
				}
			}
		}
		out.println(res);
		
		out.close();
		in.close();
	}
	
	static boolean match(int v) {
		if (matchedBy[v] == -1) return true;
		int m = matchedBy[v];
		if (visited[m]) return false;
		visited[m] = true;
		for (int u : g[m]) {
			if (match(u)) {
				matchedBy[u] = m;
				return true;
			}
		}
		return false;
	}
}