This past Saturday, two friends and I took part in the German Collegiate Programming Contest. Since none of us actually trained much beforehand and it was the first ICPC-like programming contest for two thirds of the team (me included), we were not one of those teams that managed to solve almost all problems, but ended right in the middle of the ranking with a total of three solved problems (even though we were really, really close to solving four 😉 ).

Nevertheless, I’d like to share some insights into one of the problems the organizers of the GCPC came up with. I really like it because there is a beautiful algorithm that you can apply to it and (mostly because) it is somewhat StarTrek related 😉 . The problem I’m talking about is problem L of the GCPC 2016 which you can find in this PDF. The solution of course contains spoilers, so if the problem statement makes you curious I’d recommend giving it a try first and coming back later to see if you found a more elegant solution. If you are a TUM student, you can even run it against all the tests that were used in the contest on TUMJudge.

I’m gonna share just the general problem statement here, for the details (input and output format and test cases) please take a look at the PDF linked above:

Before going into our working solution, I’d like to share some of the mistakes we made along the way: First we tried a brute-force approach on the off-chance that the time limit is so high that this suffices. What we did was to branch at every possible choice that Bob has while looking for the room aboard the Spacey McSpaceface that contains the override switch and keep track of the probability of the path. Unsurprisingly, this turns out to lead to an explosion of possibilities, so this approach was off the table.
The insight that solves this problem is that we don’t care at all how Bob ended up in a specific room, so we don’t need to keep track of which route he took with which probability but just with what probability he is in which at the moment – in a way, the problem is quite similar to a Markov model with the difference that the possible transitions are different from step to step, since doors open and close. At the end we just need to output the probability that Bob is in the last room – and, boom, we’re done.

With this we came up with a solution, that promises a reasonable run time and works for all the test cases given in the problem statement. Unfortunately, only for those and not for all the hidden test cases. After reading the problem statement once more really carefully, we saw that “there may be several doors between one pair of rooms which may or may not have the same letter written on them”, which we of course did not think of. So after fixing this we submitted again, but nope, still didn’t work.
So, back to reading the problem one last time: “… door from room a to room b labeled with l (on both sides)”. Which means that you can walk through the door from both sides which is also something we didn’t take into account. So after fixing this we were certain that it was going to work, but still somehow did not.
We were almost ready to give up and try another problem when we found our last bug: Bob is of course smart and does not leave the room with the switch again once he is there. This needs to be taken into account when computing the probabilities. We did that in our first brute-force solution, but for some reason forgot to do just that in the final version.

Ok, enough on all the things that can go wrong, let’s take a look at the code. First is reading stuff from the input:

	static double[] rooms;
	static char[] doorSequence;
	static int roomCount;
	static HashMap<Character,HashSet<Door>> doorsFor = new HashMap<>();
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		roomCount = in.nextInt();
		int doorCount = in.nextInt();
		
		rooms = new double[roomCount];
		
		for(int i=0;i < doorCount;i++){
			int from = in.nextInt();
			int to = in.nextInt();
			char letter = in.nextLine().charAt(1);
			Door aToB = new Door(from-1,to-1,letter);
			
			if(doorsFor.containsKey(letter)){
				doorsFor.get(letter).add(aToB);
			} else {
				HashSet<Door> set = new HashSet<>();
				set.add(aToB);
				doorsFor.put(letter, set);
			}
		}
		
		doorSequence = in.nextLine().toCharArray();
		in.close();
		
		// We are on the bridge in the beginning
		rooms[0] = 1;
		
		for(char letter : doorSequence){
			step(letter);
		}
		
		System.out.println(rooms[roomCount-1]*100);
	}

The only thing that is interesting here is subtracting one from all the room numbers. This has to be done since the indexing is done one-based in the problem but we do it zero-based in our code. The other thing that might be a little surprising is the usage of objects and built-in structures like the HashTable and the HashSet. My guess would be that the overhead of creating those is probably greater than the costs we would have by iterating over all doors each time, but as the number of doors increases this solution would become better and better compared to iterating over all doors. However, since it is nowhere near the time limit, it does not really matter anyway…

For the sake of completeness, here is the door class:

	public static class Door{	
		public Door(int roomA,int roomB,char letter){
			this.letter = letter;
			this.roomA = roomA;
			this.roomB = roomB;
		}
		
		char letter;
		int roomA;
		int roomB;
	}

The part that is really interesting however is the step function:

	public static void step(char letter){
		double[] newProbs = new double[roomCount];
		
		HashSet<Door> openDoors = doorsFor.getOrDefault(letter,new HashSet<Door>());
		
		// If we are in the last room we do not leave it
		for(int i=0;i < roomCount-1;i++){
			int outgoing = 0;
			
			for(Door d : openDoors){
				if(d.roomA == i || d.roomB == i){
					outgoing++;
				}
			}
			
			if(outgoing == 0){
				newProbs[i] += rooms[i];
			} else {
				for(Door d : openDoors){
					if(d.roomA == i){
						newProbs[d.roomB] += rooms[i]/(outgoing*1.0); 
					} else if(d.roomB == i){
						newProbs[d.roomA] += rooms[i]/(outgoing*1.0);
					}
				}
			}
		}
		
		newProbs[roomCount-1] += rooms[roomCount-1];
		
		rooms = newProbs;
	}

Most of it is very straightforward, the only things that might seem a little surprising are in line 17 and line 30. In line 17, we handle the case of no open outgoing doors. In this case we stay in the same room for certain, so the probability to be in this room in the next step is the same as in the last step. The += here could also be an = since having no outgoing doors also means there can be no open incoming doors.
The loop over the rooms excludes the last room (the room with the override switch Bob wants to reach). The reason for this is that we don’t leave this room again once we are in it. We encode this in line 30. Here it really has to be += because there might be a open door into the last room from another room, so the probability to reach this room might increase.

All in all, the GCPC was an awesome experience and I’m really looking forward to doing something similar in the near future again. Also, since there is no photo in this entire post so far, here is a photo of our team: 😉