Tävlingsprogrammering/Uppgifter/Friendbook

Mall:Proguppgift

Lösning

Den här uppgiften är ganska kul, eftersom den medför vissa begränsningar på flera plan. I värsta fall har vi 5000 användare, d.v.s. 25 miljoner chars att läsa in från en fil, vilket givetvis tar sin tid och för Java användaren värdefullt minne (en char är 2 byte i Java, så ca 50 av 64MB är redan upptagna).

Det man vill göra är att jämföra alla med alla, vilket för 5000 användare är ca 12,5 miljoner jämförelser. Helt möjligt att genomföra på 5 sek kanske någon tänker, men vänta nu, vad ska vi jämföra? Jo fiendelistor (vilka fiender användare har och om de är samma), och hur många jämförelser behöver man för att kolla om två fiendelistor är lika? Jo 5000, så våra 12,5 miljoner blir helt plötsligt 62,5 miljarder, vilket inte är så trevligt. Vad man dock kan göra är att ha en smartare respresentation för varje fiendelista, t.ex. ett BitSet och då blir det ca 5000/64 jämförelser för att kolla om två fiendelistor är lika. Dock hinner man inte under 5 sek med det tillvägagångssättet för de större testfallen (5000 användare).

Vad man vill göra är att bara behöva gå igenom varje användares lista över relationen till andra användare ca en gång. Vi vill helt enkelt ta en användare, kolla vilka fiender han har, göra en representation av vilka fiender han har, lägga till användaren till en grupp där alla har just den representationen av fiender. D.v.s. vi går igenom alla användare och stoppar dem i grupper utefter vilka fiender de har. Sedan går vi igenom alla grupper och för varje användare i gruppen kollar vi om deras vänner också finns i gruppen (och för fallet icke-vän att de inte finns där). Då blir helt plötsligt vårt 12,5 miljoners tillvägagångssätt högst möjligt.

I lösningen nedan används ett BitSet för att representera en användares fiender, eftersom det är relativt minnessnålt och enkelt att jobba med. Sedan använder vi BufferedReader istället för Scanner för att få lite snabbare inläsning.

import java.util.*;
import java.io.*;

public class Friendbook
{
	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws IOException
	{
		//long tid = System.currentTimeMillis();

		//Vi ska läsa av filen friendbook.dat.
		BufferedReader scan = new BufferedReader(new InputStreamReader(new FileInputStream("friendbook.dat")));

		//Antalet användare.
		final int N = Integer.parseInt(scan.readLine());

		//Läser in användarna.
		char [][] net = new char[N][N];
		for(int i = 0; i<N; i++)
		{
			scan.read(net[i],0,N);
			scan.skip(1); //Nyrad kan ibland vara två tecken, tänk på det.
		}

		scan.close();

		//Antalet par som uppfyller villkoret.
		int sum = 0;

		//Håller reda på alla grupper.
		Groups gs = new Groups();

		//Går igenom alla användare.
		for(int i = 0; i<N; i++)
		{
			//Fiendelista för användaren.
			BitSet b = new BitSet(N);

			//Går igenom relationerna för användaren.
			for(int j = 0; j<N; j++)
			{
				//Markerar användare som fiende.
				//Det går lite fortare att markera flera i ett svep.
				if(net[i][j]=='F')
				{
					int fr = j;
					while(++j<N && net[i][j]=='F');
					b.set(fr,j);
				}
			}

			//Lägger till denna användare i en grupp.
			gs.add(b,i);
		}

		//Går igenom alla grupper.
		for(List <Integer> same : gs)
		{
			//Markerar vilka användare som har just den fiendelista vi betraktar.
			boolean [] u = new boolean [N];
			for(int j : same) u[j] = true;

			//Går igenom användarna i gruppen.
			for(int j : same)
			{
				//Vi ska bara räkna antalet giltiga par från användaren själv
				// och framåt, så att vi inte räknar ett par två gånger.
				for(int k = j+1; k<N; k++)
				if(net[j][k]=='V'){ if(u[k]) sum++; }
				else if(!u[k]) sum++;
			}
		}

		//Skriver ut svaret.
		System.out.println("Svar: " + sum);
		//System.out.println("Tid: " + (System.currentTimeMillis()-tid));
	}

	private static class Groups implements Iterable <List<Integer>>
	{
		//BitSet:et representerar en fiendelista.
		//List<Integer> innehåller alla användare som har just den fiendelistan.
		HashMap <BitSet, List<Integer>> set;

		public Groups()
		{
			set = new HashMap <BitSet, List<Integer>> ();
		}

		//Lägger till användare "i" i gruppen "b".
		public void add(BitSet b, int i)
		{
			//Hämtar gruppen.
			List <Integer> s = set.get(b);

			//Om den inte fanns, så skapar vi den.
			if(s==null)
			{
				s = new LinkedList <Integer> ();
				set.put(b,s);
			}

			//Lägger till användaren i gruppen.
			s.add(i);
		}

		//Så att vi kan använda en for-each loop.
		public Iterator<List<Integer>> iterator()
		{
			return set.values().iterator();
		}
	}
}

Enkel lösning som går ut på att helt enkelt stoppa in alla fiendelistor i ett std::set. Eftersom ett std::set alltid kollar om det finns en dubblett när man försöker lägga till ett element (och i så fall returnerar en pekare till det som redan fanns), kan vi lagra vilken adress alla fiendelistor har. När vi sedan loopar över alla par ser vi helt enkelt om båda har samma fiendelista, dvs. samma adress till en sträng med den tillhörande fiendelistan. Man kan även lägga märke till att citatet stämmer på detta par om (är vänner == samma fiendelista) är sant.

#include <cstdio>
#include <set>
#include <string>

using namespace std;

int N;

set<string> fiendelistor;
set<string>::iterator fiendelist_id[5000];

bool are_friends[5000][5000];

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		string fiendelista;
		fiendelista.resize(N);
		
		char indata[N+1];
		scanf("%s", indata);
		
		for(int j=0; j<N; j++){
			are_friends[i][j] = (indata[j] == 'V');
			fiendelista[j] = (indata[j] == 'F');
		}
		set<string>::iterator id = fiendelistor.insert(fiendelista).first;
		fiendelist_id[i] = id;
	}
	int count = 0;
	for(int i=0; i<N-1; i++) for(int j=i+1; j<N; j++){
		count += (are_friends[i][j] == (fiendelist_id[i] == fiendelist_id[j]));
	}
	printf("%d\n", count);
}

Eftersom vi bara har 5000 olika fiendelistor kan det vara smart att försöka komma på att representera varje fiendelista med ett tal som beräknas fram utifrån fiendelistan. En sådan representation kallas hash. Om en hash representeras av ett 32 bitarstal, blir sannolikheten för 5000 element ca 0.3% att två olika element får samma hash, dvs. väldigt osannolikt. Vi kan använda oss utav stds nya hash-funktion som finns från gcc 4.5 (och kör man inte det är koden för den hashfunktionen väldigt simpel ändå, dvs. kan pasteas in direkt). En sådan lösning går mycket snabbare att köra:

//g++ friendbook.cpp -o friendbook -std=gnu++0x
#include <cstdio>
#include <string>

using namespace std;

int N;

bool friends[5000][5000];

size_t hashar[5000];

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		char buffer[5001];
		scanf("%s", buffer);
		string s;
		s.resize(N);
		for(int j=0; j<N; j++){
			s[j] = buffer[j] == 'F' ? 'F' : '.';
			friends[i][j] = buffer[j] == 'V';
		}
		hashar[i] = hash<string>()(s);
	}
	int antal = 0;
	for(int i=0; i<N-1; i++) for(int j=i+1; j<N; j++){
		bool samma = hashar[i] == hashar[j];
		bool is_friend = friends[i][j];
		antal += (samma == is_friend);
	}
	printf("%d\n", antal);
}