An Eyewitness account from the NCPC – Part 2/3

An Eyewitness account from the NCPC – Part 2/3

Written by on 17 October 2011

Topics: Other

Editor note: We are coming back from the short break with a lot of exciting students ready to throw them self at 10 exciting problems that needs to be solve in a very short time. So lets get right into it. Read part 1 here

There are 10 problems, uniquely identified with a character from A to J. They are not ordered by difficulty, but in a competition like this you want to finish the easiest problems first.

The problem set is located here, but since the problem descriptions are long, I won’t be posting them here. I recommend you read the problems and try them out for yourself before reading the rest of the story. You need to read the descriptions of problems A, C,  D and F at least, which are the problems I’ll be talking about.

Each team can have up to three members and is provided a single computer. I was chosen to program while my teammates would find and solve problems, although I would of course help with solving problems while I was not programming.

When the competition started, one of my teammates started reading problem A, the second started reading problem B and I started reading problem C. I saw that C was an easy problem and started to program.

We solved the problems using c++ during the competition, but I have chosen to rewrite the solution in C# for this account.

Problem C

This problem was, by far, the easiest problem. After reading the text you are given that a player in a game wins all his battles, except the battles where he does the “Chains of Ice” move immediately followed by the “Death Grip” move. The description says that “Chains of Ice” is represented by the character “C” and “Death Grip” is represented by “D”. This basically means that you need to count the lines which do not contain the substring “CD”.

int cnt = Convert.ToInt32(Console.ReadLine()),
wins = 0;

for (int i = 0; i < cnt; i++){
    // We won the battle if the line doesn't contain "CD"
    if (!Console.ReadLine().Contains("CD")){
        wins++;
    }
}
Console.WriteLine(wins);

I had trouble submitting my solution to this problem in the competition. I kept getting an error message “Invalid function”. This was caused by a function that I used when I was debugging the program locally, which made the C++ cin stream read from an input file. All I had to do was comment out that line and it worked perfectly.

The first thing you have to do when solving a problem, is to understand the description. Problem C is a good example of how the problem creators can make a very simple task harder just by coating it with unnecessary clutter.

At this point, my teammate had written what seemed like a reasonable solution for Problem D on a piece of paper.

Problem D

Problem description can be found here.

In the competition we solved this by simulation. If we were under the goal floor, and we could go up, we would go up. We did the same if we were over the goal floor. This was done in a loop, and we counted the button presses. Along with this we also had some conditions to break out of the loop if we saw that the goal could not be reached.

Our first attempt at a solution was flawed. It would get stuck in the loop on certain inputs. We quickly fixed that by monitoring the button push count and making sure it didn’t go higher than some maximum value that we figured out.

Our solution looks like

// Read the input
string[] input = Console.ReadLine().Split(' ');
int f = Convert.ToInt32(input[0]),
s = Convert.ToInt32(input[1]),
g = Convert.ToInt32(input[2]),
u = Convert.ToInt32(input[3]),
d = Convert.ToInt32(input[4]),
cnt = 0;

// The maximum number of button pushes we'll
// tolerate before we stop trying to get to the target floor
// (the button pushes will only reach this if the target floor is unreachable)
// This was a quick fix we did to get a correct answer in the competition
int max = 1000000 * 2;

// If the up count is equal to the down count, the length to the target floor
// must be divisable by that count
if (u == d && u != 0 && (Math.Abs(g - s) % u) != 0){
    Console.WriteLine("use the stairs");
} else {
    // The main loop
    while (true){
        // If we are under the target floor
	if (s < g){
            if (u == 0){
                // We are under the target floor and the elevator doesn't go up
		Console.WriteLine("use the stairs");
		break;
            }

	    if ((s + u) > f){
                // The elevator doesn't go that high
                if ((s - d) < 1){
                // The elevator can't go down either
                    Console.WriteLine("use the stairs");
                    break;
                }

                // We'll have to go down, we have no other choice
		s -= d;
		cnt++;
            } else {
                // We go up
                s += u;
		cnt++;
            }
        } else if (s > g) {
            // We're above the target floor
            if (d == 0) {
                // We can't go down
		Console.WriteLine("use the stairs");
                break;
            }

	    if ((s - d) < 1){
                // If we can't go down
                if ((s + u) > f) {
                    // And we can't go up either
                    Console.WriteLine("use the stairs");
		    break;
                }
                // We have no choice but to go up
                s += u;
                cnt++;
            } else {
                // We go down
                s -= d;
                cnt++;
            }
        } else {
            // We're at our destination
            // We output the number of button pushes so far
            Console.WriteLine(cnt);
            break;
        }
        if (cnt > max)  {
            // Quick and dirty fix (don't try at home)
            Console.WriteLine("use the stairs");
            break;
        }
    }
}

However, there is a much cooler way to solve this problem. We can visualize the problem as a binary tree, where the root node is the current floor.

Illustration of binary tree

The left child node is the floor we go to if we press the down button, and the right child node is the floor we go to if we press the up button. Then we build on the child nodes using the same logic. Note that we don’t add child nodes to the tree which represent floors that are out of range (are less than 1 or greater than the highest floor).

We can search this tree for the goal floor, and the depth of that node (in the tree) is how many button pushes we have to make. The search algorithm we want to use to search the tree is called Breadth-First Search or BFS. If you don’t know how BFS works, Wikipedia has a good description of it here (you should also take a look at it’s counterpart, Depth-First Search, and try to figure out why we can’t use it here).

Note that we need to remember which floors we’ve visited, so we can prevent searching from the same floor again, possibly resulting in an infinite loop.

I have programmed that solution as well. We need a small struct to hold some data which looks like

public struct Floor{
    public int FloorNumber;
    public int ButtonPushes;
}

The main algorithm is implemented as

// Read the input
string[] input = Console.ReadLine().Split(' ');
int f = Convert.ToInt32(input[0]),
s = Convert.ToInt32(input[1]),
g = Convert.ToInt32(input[2]),
u = Convert.ToInt32(input[3]),
d = Convert.ToInt32(input[4]);

if (s == g) {
    // We are already at the goal level,
    // so we don't have to press any buttons
    Console.WriteLine("0");
    return;
}

HashSet<int> visited = new HashSet<int>();
Queue<Floor> floors = new Queue<Floor>();

// We start by visiting the starting floor
floors.Enqueue(new Floor() { FloorNumber = s, ButtonPushes = 0 });
visited.Add(s);

while (floors.Count > 0){
    Floor currentFloor = floors.Dequeue();
    int up = currentFloor.FloorNumber + u,
    down = currentFloor.FloorNumber - d;

    // If the next floor is the goal floor
    if (up == g || down == g){
        // We output the number of button pushes
	Console.WriteLine(currentFloor.ButtonPushes + 1);
	return;
    }

    // If we can go up and haven't already visited that floor
    if (up <= f && !visited.Contains(up)) {
        // We add it to the visit queue and mark it as visited
        visited.Add(up);
        floors.Enqueue(new Floor() {
            FloorNumber = up,
            ButtonPushes = currentFloor.ButtonPushes + 1
        });
    }	

    // If we can go down and haven't already visited that floor
    if (down >= 1 && !visited.Contains(down)){
        // We add it to the visit queue and mark it as visited
        visited.Add(down);
        floors.Enqueue(new Floor() {
            FloorNumber = down,
            ButtonPushes = currentFloor.ButtonPushes + 1
        });
    }
}

// The tree doesn't contain the goal floor
// We're going to have to use the stairs
Console.WriteLine("use the stairs");

After finishing Problem D, a solution for Problem A popped into my mind. I programmed a solution, but I would always get a “Wrong Answer” when I submitted it. After a while, I gave up and we went on to solve Problem F.

Editors note: We will leave SuprDewd and his team mates for the day while they are sweating over the remaining problems and figuring out a solution. So come back tomorrow for the exciting end of the story. You can find all the source code here.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.