Tävlingsprogrammering/Uppgifter/Friendbook

Friendbook

FriendBook är en internetsite där man kan chatta och skriva till sina vänner. Under en lång tid har de använt sig av ett simpelt “vänsystem”, varje användare har en lista över sina “vänner” bland de övriga användarna. På sistone har däremot en mycket kontroversiell feature dökt upp, nämligen att man även har en lista över sina “fiender”. Medan vänrelationen alltid är ömsesidig (man bekräftar att man känner varandra) så behöver fienderelationen inte vara det: person A kan ha en fiende B som av ren fiendskap vägrar acceptera A som fiende.

Du är poet och funderar ofta över visdomsord och citat! Nyligen har du fått upp ögonen för följande citat:

Med en vän menar man en som tycker illa om samma människor som man själv.

Du vill veta i hur stor utsträckning citatet stämmer på ett givet Friendbook-nätverk. Mer formellt, för hur många par av användare gäller att de antingen är vänner och har identiska fiende-listor eller att de inte är vänner och inte har identiska fiende-listor?

Indata

På första raden i filen friendbook.dat står ett heltal N, antalet användare (2 ≤ N ≤ 5000). Sedan följer N rader, där varje rad består av N tecken. Beteckna tecknet på rad y och kolumn x för S_yx. S_ij anger vilket förhållande person i har till person j. De möjliga tecknen är ’V’, ’F’ och ’.’, de står för vän, fiende samt neutralt förhållande. Om exempelvis S_ij =’F’ innebär det att person j finns på person i:s fiendelista. S_ii är alltid ’.’ och om S_ij =’V’ så är även S_ji =’V’ (men detta gäller inte alltid för de övriga tecknen).

Utdata

Programmet ska skriva ut ett heltal: antalet par av användare (utav de totalt ${\frac {N(N-1)}{2}}$ paren) för vilka citatet stämmer.

Exempel 1

3
.VV
V.V
VV.

Svar

Förklaring: Här är alla vänner med alla, så de har alltså alla samma fiender (trots att de inte har några fiender).

Exempel 2

3
.FF
F.F
FF.

Svar

Förklaring: Denna gång är alla fiender och då allas fiendelistor är olika stämmer citatet återigen för alla tre paren.

Exempel 3

5
.VFFF
V.FFF
FF.VF
FFV.F
FFFF.

Svar

Förklaring: De två paren som är vänner har identiska fiendelistor, övriga 8 par har olika fiendelistor.

Exempel 4

6
.VV.F.
V.V...
VV..FF
....VV
...V.F
FF.VF.

Svar

Förklaring: Här har de 5 vänparen olika fiendelistor. Men av de 10 övriga paren så har bara ett identiska fiendelistor, så 9 par uppfyller citatet.

Exempel 5

20
.VVVFVVVVV.VVVVVVVVV
V.VVVVVV.VVVVVVVVVVV
VV.VVVFV.VVVVFVVVVV.
VVV.VVVV.VVFVFVVV.VV
FVVV..VVVVVVVVVVVVVV
VVVVF.VVVV.VVVVVVVFV
VV.VVV.VVV.VVV.VVVV.
VVVVVVV.VF.VVV.V..FV
VF.FVVVV.VVVVF.VV.VV
VVVVVVVFV.VVFVVFVVVV
FVVVV.FFVV.VFV.VVVVV
VVVFVVVVVVV.FFVVV.VV
VVVVVVVVVF.F.VVV.VVV
VV.FVVVV.VVFV.VVVVF.
VVVVVVFF.V.VVV.V.VVV
VVVVVVVVVFVVVVV.VVVV
VVVVVVVFVVVVFV.V.VVV
VVVFVVVF.VVFVVVVV.VV
VVVVV.VFVVVVVFVVVV.V
VV.VVVFVVVVVVFVVVVV.

Svar

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^[1]).

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.

↑ Har java en gräns på 64 MB minne? Både ja och nej. Det som är begränsat är heapen. På ett 32-bit system är den 64 MB per default. Man kan dock begära mer minne med -Xmx flaggan när man kör programmet (java -Xmx512M ProgramNamn, kör programmet med 512 MB), men eftersom det inte är en själv som kör programmet, så blir ju storleken 64 MB (såvida inget annat har angetts i instruktionerna). Och det är just på heapen som matrisen (i allmänhet allting skapat med new hamnar på heapen) kommer att hamna, varför minnesgränsen blir 64 MB.

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);
}

[1] Har java en gräns på 64 MB minne? Både ja och nej. Det som är begränsat är heapen. På ett 32-bit system är den 64 MB per default. Man kan dock begära mer minne med -Xmx flaggan när man kör programmet (java -Xmx512M ProgramNamn, kör programmet med 512 MB), men eftersom det inte är en själv som kör programmet, så blir ju storleken 64 MB (såvida inget annat har angetts i instruktionerna). Och det är just på heapen som matrisen (i allmänhet allting skapat med new hamnar på heapen) kommer att hamna, varför minnesgränsen blir 64 MB.

[1]