Beaver10001000

Skyline

Story

A skyline consists of 14 towers as shown. The height of a tower is measured from the bottom of its base to its highest point, including any flagpoles or antennas.

Question

If the towers are listed from shortest to tallest, which tower would be 10th in the list?

• 
• 
• 
• 

Answer explanation

Explanation of Answer

Notice that the skyline consists of one sequence of towers that gets taller from left to right followed by a second sequence of towers that gets taller from left to right. Also notice that the last two towers in each of these sequences make up the four tallest towers overall. (This did not have to be true. It could have been the case, for example, that the four tallest towers were all at the end of one of the two sequences.)

Since there are 14 towers in total, if we ignore the four tallest towers, the tallest remaining tower will be 10th in the list. The tallest remaining tower is the one in Option A.

Connections to Computer Science

In this task, you are asked to determine which tower would be the 10th in a list of towers if all the towers were ordered by height. Arranging items in order is called sorting.

There are many well-known sorting algorithms and this task is related to the mergesort algorithm. The key idea behind this technique is to separately sort the two halves of the items. Then you must merge these two sorted lists to produce one completely sorted list. If you chose to solve this problem by sorting all 14 towers, then you could have been merging the sorted towers in the left half with the sorted towers in the right half.

Country of Original Author

Canada

Library Books

Story

Beavertown Library has only a small pile of books. When a beaver wishes to borrow a book, they take the book that is on the top of the pile and record their name. When a beaver returns a book, they place their book on the top of the pile and record their name again.

At the beginning of the week the pile of books was arranged as shown: pic 1

The library’s records at the end of the week show the following information: pic 2

Question

Which book did Cato borrow?

• 1. Charlotte’s Web

• 1. Curious George

• 1. Go, Dog, Go!

• 1. The Hobbit

Answer explanation

Explanation of Answer

At the beginning of the week, Alba borrowed a book and then Felix borrowed a book. Looking at how the books were arranged at the beginning, this tells us that Alba borrowed Charlotte’s Web and Felix borrowed Curious George.

At the end of the week, Cato borrowed a book immediately after Felix returned a book. Since books are taken from the top of the pile and returned to the top of the pile, this means Cato borrowed the same book that Felix returned. Since Felix borrowed only one book that week, we know that he must have returned Curious George. Thus, Cato borrowed Curious George.

It is interesting to notice that we do not need to consider all of the books that were borrowed and returned. For example, it does not matter which book Marta borrowed.

Connections to Computer Science

In this problem, you are asked to keep track of which books are available as they are borrowed and returned. The key property is that the last book returned is the first book that must be borrowed the next time someone borrows a book. We say that this follows the last-in first-out or LIFO principle.

In computer science, a collection of items that follows this principle is called a stack. It is one fundamental way that a collection can be stored. In particular, a computer program will often be broken into smaller pieces called subroutines. The order in which these subroutines are executed is often determined using a stack. Another example of a stack is a web browser’s back button: the last page visited is the first page revisited when the back button is pressed.

Country of Original Author

Canada

Locked Chests

Story

Five different chests are engraved with letters as shown: pic 1

Question

What is the lost label?

• 1. 496

• 1. 639

• 1. 436

• 1. 649

Answer explanation

Explanation of Answer

Chest BEB is the only one where the first and the third letter match. So, this chest matches key 636, which is the only key where the first and third digit match. So we know that the letter B corresponds to the digit 6 and the letter E to the digit 3.

LetterABERDigit 63 

Chest AER is the only one that ends with a letter other than B. So, this chest matches key 934, which is the only key that ends with a digit other than 6. Thus, the letter A corresponds to the digit 9 and the letter R to the digit 4.

LetterABERDigit9634

Now that we know all the letter-digit pairings, we can match the remaining chests to keys, and discover that chest RAB matches key 496, which is missing.

Connections to Computer Science

Cryptography is an area of study that lies at the intersection of computer science and mathematics. The mapping between digits and letters in this task is based on the monoalphabetic substitution cipher example called the Vatsyayana cipher. The idea came from an Indian text from the 4th century AD. The Vatsyayana cipher creates unique pairs for the alphabet letters – a letter always matches another letter and each letter can be used only in one pair. During encryption of an original message one letter is directly substituted by a paired letter. Interestingly, the exact same process is used to decrypt the message. By directly substituting a letter in the encrypted message with its paired letter, the original message can be retrieved. This encryption method is easy to crack as, once someone is sure about a letter pair(s), they can decrypt all other pairs.

Modern cryptographic techniques, such as those that are used for banking transactions through the internet, use much more advanced computational methods that rely on the difficulty of hard mathematical problems, such as factoring a number which has two very large prime factors.

Country of Original Author

Cyprus

Water Bottles

Story

Dani is required to entirely fill as many empty water bottles as possible using a 50 litre tank.

Suppose she is given the following 10 empty bottles where each bottle is labelled with the number of litres it can hold.

Question

What is the maximum number of bottles that Dani can fill entirely?

• 4

• 7

• 8

• 10

Answer explanation

Explanation of Answer

Dani can approach this task by first arranging the bottles from smallest to largest (in terms of how many litres they can hold).

At any point, if Dani has two empty bottles that can hold different amounts of water, there is no advantage to filling the larger bottle. So Dani can now fill the bottles one by one from smallest to largest. The smallest 7 bottles can be filled entirely using litres of water. The tank will have 8 litres left but all the remaining bottles can hold more than 8 litres, so no more bottles can be filled entirely.

Connections to Computer Science

This problem can be solved using a greedy strategy. For this problem, we can fill the bottles in sorted order according to the amount of water each bottle holds.

More generally, a greedy strategy involves making the best choice at each stage in the hopes of finding the best solution. In this way, it makes one greedy choice after another, reducing the given problem into a smaller one.

However, not every problem can be solved optimally using a greedy strategy. For example, knapsack problems usually do not have optimal solutions that can be found using a greedy strategy. Nevertheless, the greedy strategy is still useful because it is easy to describe and implement and often gives a good approximation to the optimal solution.

Country of Original Author

Thailand

Ancient Texts

Story

Symbols form the titles of ancient texts. Each type of symbol is associated with a digit as shown below. Some different symbols are associated with the same digit.

• 
• 
• 
• 

Answer explanation

Of the options, the only text that has the special number 6944 is the one in Option C.

Connections to Computer Science

When storing information, one important goal is to be able to quickly retrieve a particular piece of information. One method to accomplish this goal is to store information in a hash table.

A hash table consists of several locations where we can store information. The position of where to store a piece of information is determined by a hash function. For this task, the hash function for the symbols, which were the keys, was to assign them to one of the digits from 0 to 9, the values.

As was also realized in solving this task, sometimes there are collisions in the hash function, where two keys yield the same value. In order to deal with this, various collision resolution strategies have been developed to maintain efficiency. Hashing can provide extremely efficient lookup times even with a massively large amount of data.

Country of Original Author

Taiwan

Part B

Beaver Intelligence Agency

Story

For security reasons, a secret message was broken into four parts (1, 2, 3, and 4). Copies of these parts were then sent to the divisions and subgroups of the Beaver Intelligence Agency (BIA) as shown: pic 1

Labels on the copies of the message parts indicate who has access to it:

• “” means everyone in the BIA has access to this copy.

• “#” means the division that receives it and the division’s subgroups (indicated by arrows) have access.

• “=” means only the division or subgroup that receives it has access to this copy.

• Question

  Which one of the following has access to all four parts of the message?

• 1. Fox Subgroup

• 1. Wolf Division

• 1. Rabbit Division

• 1. Chipmunk Subgroup

Answer explanation

Explanation of Answer

Parts labelled with “” are accessible to everyone. We can visualize this by cloning each part labelled with “” and placing a clone within every division and subgroup. The Fox Subgroup holds part 4 labelled with “”. Here is what the BIA looks like after cloning this part: pic 1

Parts labelled with “=” are only accessible to the receiving division or subgroup so we don’t make clones of parts labelled with “=”. Looking at the BIA after all the clones have been made, we see that only the Chipmunk Subgroup has access to all four parts of the message.

Connections to Computer Science

There are various programming paradigms that different programming languages follow. For example, there are imperative programming languages (such as C++ or Python), functional programming languages (like Scheme), and object-oriented programming languages (like Java). In object-oriented programming (OOP), an object is a way of storing both data and particular operations to access or transform that data. Most object oriented programming languages are class-based, meaning that objects are instances of classes.

In this task, the divisions and subgroups represent classes. Every class has access to the relevant objects with the corresponding type of visibility. Public objects (those marked with a ) can be accessed from every class in the program. Private objects (those marked with a “=”) are only visible and changeable by the class itself. Protected objects (#) can be accessed by the class itself and by its subclasses. In this task, the subgroups can read “#" messages from their division leader.

Different types of visibility are very useful for organizing a program. A class does not have to deal with objects and properties from other classes, and access to information can be carefully controlled. In this way, some programming errors can be avoided.

Country of Original Author

Austria

Mountain Climber

Story

Binsa is climbing in the mountain range shown which has 11 peaks each of a different height.

Binsa climbs by starting at the top of a random peak, then looking left and right. If she sees a peak immediately beside her that is higher than the one she is currently on, she climbs to the top of this higher peak. If two neighbouring peaks are both higher, she climbs to the top of the higher one. She continues to do this until there is no higher peak immediately beside her.

Question

From how many of the peaks (including the highest peak) will Binsa reach the highest peak?

• 3

• 4

• 6

• 7

Answer explanation

Explanation of Answer

We label the peaks as shown.

Notice that the highest peak is .

If Binsa starts on she will not climb any further since the peak on her left and the peak on her right are both lower. She will not reach the highest peak from here. In addition, if she starts on any peak to the left of she will not reach the highest peak since she will not be able to climb past .

If Binsa starts on , both of the neighbouring peaks are higher so she will climb the higher one, , and reach the highest peak.

If Binsa starts on , she has reached the highest peak.

If Binsa starts on , she will climb to and reach the highest peak.

If Binsa starts on , both of the neighbouring peaks are higher so she will climb the higher one, .

From , Binsa will not climb any further since the peak on her left and the peak on her right are both lower. She will not reach the highest peak from here. In addition, if she starts on any peak to the right of she will not reach the highest peak since she will not be able to climb past .

Thus, there are exactly 3 peaks from which Binsa will reach the highest peak. They are , , and .

Connections to Computer Science

The process that Binsa follows is called a greedy algorithm. The key idea in a greedy algorithm is to make a choice at each step based on “local information", regardless of whether there is a better option that might yield a better solution. In this task, even though Binsa is trying to reach the highest peak overall, she decides what to do next only by looking at the two mountains right beside her. That is, instead of trying to look for the global maximum, instead she looks for a local maximum.

Greedy algorithms do not always correctly solve problems, but when they do, they usually do so very efficiently. For example, the change making problem yields a fast greedy solution: in most currency systems, making a certain amount of change can be done by repeatedly using a coin of as large a value as possible. Stopping this process when the desired total is reached, will always minimize the number of coins used.

Unfortunately, not every greedy algorithm gives the best answer. However, even if a greedy algorithm is incorrect, sometimes they can be used to find a solution that is “good enough". This is called an approximation algorithm.

A specific type of greedy algorithm used in artificial intelligence is called the hill-climbing algorithm. The name of this technique comes from the idea behind this task. Additionally, the story behind this task is related to an idea from geography called topographic isolation. One of the great things about studying computer science is how it can be applied to almost any other subject area.

Country of Original Author

Canada

Image Scanner

Story

The following five images represent the letters I, T, O, C and L, respectively. Each image is a 3-by-3 grid made up of nine pixels that are each black or white.

• 
• 
• 
• 

Answer explanation

Explanation of Answer

In the given image recording, the number 0 in the rightmost pixel in the middle row indicates that no other images have this shade at this pixel.

We can see that the images of the letters I, T, C, and L all have a white pixel in this location, but the image of the letter O has a black pixel. Since the image of the letter O has a unique shade at this pixel, it follows that the image scanned by the machine must be the image of the letter O.

Here are all images with their machine recording. pic1

Connections to Computer Science

A heat map is a graphical representation of data where the individual values contained in a two-dimensional grid are represented as colours. One common use of maps is in weather reports, indicating temperatures in different regions: the hotter the temperature, the more intense or redder the colour is.

In computer science, heat maps are used in image recognition or other machine learning algorithms, to highlight important areas of the data.

Country of Original Author

Germany

Household Appliances

Story

As a practical joke, someone has connected appliances to buttons P ,Q ,R ,S , and T in a very strange way.

Pressing a button toggles the on/off state of each appliance it is connected to. For example, pressing button T will turn the vacuum cleaner on if it is off and off if it is on. Pressing button T will also turn the television on if it is off and off if it is on.

All of the appliances are off.

You want only the television and coffee machine on (the third and fourth appliances from the left in the picture).

Question

Which of the following sequences of buttons should you press?

• T, R, Q, P

• R, Q, P, S

• S, P, T, R

• Q, S, R, T

Answer explanation

Explanation of Answer

For the sequence in Option D, the buttons Q, S, R, and T are pushed. When Q is pushed, the laptop, washing machine, and coffee machine are turned on.

At this point, the television and coffee machine are on, whereas all other appliances are off.

Another way to see that this is the correct answer while the others are not correct is to examine each button and appliance independently. Notice that if a button is pressed an odd number of times, the connected appliances are left in the “on" state, while an even number of presses leaves the appliances in the “off" state. The same holds for a single appliance: if the number of buttons pressed and connected to it is even, then the appliance will be turned off, and if it is odd, the appliance will be turned on.

• For the Option A , the vacuum cleaner is connected to three of the pressed buttons:. Hence, it will be “on" after all these buttons are pressed, which is not correct.

• For Option B , the coffee machine is only connected to two of the pressed buttons, which means that it will remain “off", which is not correct.

• For Option C , the washing machine is connected to only one of the pressed buttons, ,which means that it will be “on" after all these buttons are pressed, which is not correct.

• For Option D , we have the following number of button presses for the appliances:

  • laptop: two button presses, , which means it will be off at the end.

  • washing machine: two button presses, which means it will be off at the end.

  • television: three button presses, ,which means it will be on at the end.

  • coffee machine: one button press, which means it will be on at the end.

  • vacuum cleaner: two button presses, which means it will be off at the end.

  • Connections to Computer Science

    We can think of the appliances in this task in terms of individual binary digits, also called bits (from BInary digiTS). Each time a button is pressed that affects an appliance, it switches between off and on, which computer scientists usually write as 0 and 1, respectively.

    The binary system is used by computers, where all information is stored and manipulated as binary information. In particular, the computer hardware, such as the central processing unit (or CPU) operates with information as electrical signals, which are either “off” or “on”. These electrical signals are processed through logic gates, such as AND, OR, and NOT gates. One other logic gate is the XOR, or exclusive-OR gate, usually written as .

  • 0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0

  • For this task, we can think of the applicances as five bits, and keep track of their state and how each of the buttons change the state. That is, initially , we can think of the applicances, as read from left to right, as the sequence 00000 . After button Q is pressed, we know that the sequence would change to 11010 . Pressing just button R would change the sequence to 10101 . If we pressed both Q and R from the initial state, we would have

  • 00000 XOR 110101 XOR 10101 = 01111

  • Using this technique, we can determine the bit pattern for each button, XOR them, and determine which bits end up as 1 or 0, which indicates whether the appliance is on or off. Interestingly, the order in which we apply the XOR operations (button presses) does not matter.

    Country of Original Author

    Japan

Puzzle Pieces

Story

A beaver has a puzzle with 12 different types of pieces, 4 of which are red, 4 of which are yellow, and 4 of which are blue, as shown below. There is an unlimited number of each type of piece.

Question

Which of the following colour sequences cannot be constructed?

1. YELLOW BLUE BLUE RED BLUE

2. BLUE YELLOW RED YELLOW RED

3. RED RED YELLOW BLUE BLUE

4. BLUE RED YELLOW BLUE RED

• 
• 
• 
• 

Answer explanation

Explanation of Answer

For Option C, notice that the last puzzle piece must have a flat right side and be blue. Thus, this piece must be: pic 1.

Connections to Computer Science

Computer scientists call valid expressions well-formed. Expressions containing errors are called malformed. In this task, you were asked to find the malformed expression.

As another example, consider mathematical expressions that involve arithmetic. There are rules about where operators and operands must be placed. The expressions 2+3, 4 x 2, and (2+4) / 3 are well-formed but 2 + x 5 and 4x are malformed.

An expression that is well-formed can also be called syntactically correct. The syntax of a statement is the correct form or structure: for example, the sentence “My dog likes walks” is syntactically correct, but the sentence “Likes walks dog my” is not syntactically correct, since the form or order of the words is not correct. Most programming languages in computer science require that programs are syntactically correct.

In fact, computers are much more strict about syntax since computers do not have the same ability as humans to infer meaning from malformed sentences. For example, most English speakers could understand the meaning of “The stairs up I walked”, but an equivalently scrambled statement in a computer programming language would be rejected by the computer as a syntax error.

Country of Original Author

Macedonia