An Eyewitness account from the NCPC

An Eyewitness account from the NCPC – Part 3/3

Editors note: Yesterday we left Suprdewd and his teammates sweating over the remaining problems to solve, so lets pop our heads back in and lets see how this ends. Read part 1 and 2

Problem F

My teammates had trouble understanding the description at first, but figured it out after writing it out on a piece of paper (I recommend taking a pen and paper to a competition if you’re allowed to).

Read the whole problem description here.

We’re given a list of moose. We know their strength and the year they first competed. We also know that Karl is the first moose in the list. After reading in the data, we looped through all the years, starting at 2011 and going up. Inside the loop we found the strongest moose which started competing not later than the current year in the loop. Then we removed that moose from the list. If that moose was Karl, we would output the current year and exit. If we got through all the years without Karl ever winning, we output “unknown”.

The C# code for helping the moose need a struct which looks like

public struct Moose{
    public bool IsKarl;
    public int Year;
    public int Strength;
}

Assuming that we have handled the input to get an array of Moose. The main algorithm looks like

// Sort them by strength descending so we can find the strongest moose for each year faster
List<Moose> lms = ms.OrderByDescending(moose => moose.Strength).ToList();
			
// Loop through all the years
for (int year = 2011; year <= maxYear; year++){
    // Find the best moose
    for (int i = 0; i < lms.Count; i++){
        Moose currentMoose = lms[i];
	if (currentMoose.Year > year){
            // The current moose hasn't entered the competition yet
	    continue;
        }
					
	// We found our best moose
	// If the best moose this year is Karl
	if (currentMoose.IsKarl){
            // We output the current year and exit
	    Console.WriteLine(year);
            return;
        }
					
	// Remove the best moose from the tribe and go to next year
	lms.RemoveAt(i);
	break;
    }
}
			
// We don't have enough data to determine when Karl will win
Console.WriteLine("unknown");

I finished Problem F and thought I should return to Problem A, which I then did.

Problem A

Problem description can be found here.
This problem has two parts. The first part is to count the number of paths from the top left to the bottom right modulo 2^31 – 1, by only going down or right from each square. If you think about it, this is exactly like one Project Euler problem, namely Problem 15 which Kristian has covered here (we need to used the dynamic programming method), but remember that everything must be done modulo 2^31 – 1 here. The only difference between these problems are the obstacles in the path. We cannot walk through them, so we set the number of paths from them to 0, which keeps the logic working. For example, if we are standing above an obstacle and to the right of an obstacle, the number of paths to the current location is 0 + 0 = 0 which is exactly what we want. After counting the paths, we output the count if it’s greater than 0. However, if there are 0 paths, we have to continue to part 2, which checks if we can walk from the top left to the bottom right if we can also walk left and up. Now we can use some kind of Pathfinding algorithm, but since we don’t care about the path itself, we’ll use Flood Filling. We start flood filling at the top left square, and if we reach the bottom right square we output “THE GAME IS A LIE”, otherwise we output “INCONCEIVABLE”.

I had a lot of trouble with this problem. There was something wrong with my modulo logic. I still don’t know what was wrong, but I managed to fix it 15 minutes before the competition was over.

The full solution to problem A is

// Read the input
int mod = Int32.MaxValue,
size = Convert.ToInt32(Console.ReadLine());
			
// Read the map into a two-dimensional boolean
// True is walkable 
// False is an obstacle
bool[,] map = new bool[size, size];
			
for (int row = 0; row < size; row++){
    string line = Console.ReadLine();
				
    for (int col = 0; col < size; col++){
        map[row, col] = line[col] != '#';
    }
}
			
// The path counts
int[,] paths = new int[size, size];
			
// There is one path from the end to the end
paths[size - 1, size - 1] = 1;
			
// We walk through all the map, starting at the end
for (int row = size - 1; row >= 0; row--){
    for (int col = size - 1; col >= 0; col--){
        if (row == size - 1 && col == size - 1){
            // We've already manually set the end
	    continue;
	}
					
	if (map[row, col]){ // If the current square is walkable
            long count = 0;
	    if (row < size - 1) count += paths[row + 1, col];
	    if (col < size - 1) count += paths[row, col + 1];
						
	    // We set the path count to the path count below us + the path count to the right of us (mod 2^31 - 1)
	    paths[row, col] = (int)(count % mod);
        } else {
            // If there is an obstacle on the current square,
	    // we set it to 0
	    paths[row, col] = 0;
        }
    }
}
			
// The total path count is in the top left of the array
int totalPathCount = paths[0, 0];
			
// If the total path count is greater than 0
if (totalPathCount > 0){
    // We output it, and exit
    Console.WriteLine(totalPathCount);
    return;
}
			
// The path count was 0, so we have to start flood filling
bool[,] flood = new bool[size, size];
flood[0, 0] = true;
			
Queue<Tuple<int, int>> visitQueue = new Queue<Tuple<int, int>>();
visitQueue.Enqueue(new Tuple<int, int>(0, 0));
			
while (visitQueue.Count > 0){
    // Dequeue the next square to visit
    Tuple<int, int> currentSquare = visitQueue.Dequeue();
				
    // Add all neighbours, which have not been visited, to the visit queue
    for (int xDelta = -1; xDelta <= 1; xDelta++){
        int curX = currentSquare.Item1 + xDelta;
	if (curX < 0 || curX >= size) continue;
					
	for (int yDelta = -1; yDelta <= 1; yDelta++){
            if (xDelta == 0 && yDelta == 0) continue;
	    if (xDelta != 0 && yDelta != 0) continue;
						
	    int curY = currentSquare.Item2 + yDelta;
	    if (curY < 0 || curY >= size) continue;
						
	    // We don't want to visit an already visited square or a square that is not walkable
	    if (flood[curX, curY] || !map[curX, curY]) continue;
						
	    if (curX == size - 1 && curY == size - 1){
                // We can reach the end square
		Console.WriteLine("THE GAME IS A LIE");
		return;
            }
						
	    // We mark the current square as visited
	    flood[curX, curY] = true;
						
	    // And add it to the visit queue, so we can examine it's neighbours later
	    visitQueue.Enqueue(new Tuple<int, int>(curX, curY));
        }
    }
}
			
// We can't reach the end at any cost
Console.WriteLine("INCONCEIVABLE");

At this point we were pretty happy with ourselves and neither did we have time to start another problem nor did we think of a solution for any of the other problems. So we just relaxed and waited for the results to be announced.

Final Words

We solved 4 problems of 10 (A, C, D, F) which I’m pretty proud of, considering how hard these problems are and that this is our first time. We finished 2nd of 4 teams in Iceland and 71st of 250 teams overall. I’m very satisfied with our final standings.

The competition was very exciting and crazy fun and I can’t wait to participate again next year.

I encourage everybody out there to consider taking part in a competition like this, whatever skill level they’re at. It’s a great experience and you have nothing to lose.

You can download my solution to the problem here.

Posted by Kristian

Leave a Reply