This commentary is meant to give a brief outline of what is required to solve each problem and what challenges may be involved. It can be used to guide anyone interested in trying to solve these problems, but is not intended to describe all the details of a correct solution. We encourage everyone to try and implement these details on their own using their programming language of choice.
Attempts to solve past problems can be submitted on the CCC Online Grader. Also, after a contest is complete, official test data is available by clicking the corresponding “Download” button on our Past Contests webpage.
The first problem on this year’s contest involves printing out the result of an arithmetic expression. The expression consists of three input values representing the number of plates of each colour, and constant values which are the cost of each colour of plate.
This year, a twist was introduced at this early point of the contest.
We are told Dusa’s starting size and the size of the Yobis, but we are
not told how many Yobis there are. This means that a while
loop, or the equivalent, is needed instead of a for loop
which might be more familiar. That is, we can continue reading input and
adding the size of the current Yobi to the size of the Dusa
while the size of the Dusa is less than the size of the current
Yobi. Put another way, the loop continues until a Yobi is
encountered that is the same size as the Dusa or larger.
There are several different ways of solving this problem.
One approach is to maintain six variables storing values for the gold, silver and bronze score as well as a count of the number of participants with each of these scores. Taking care to initialize these variables properly, they can then be updated as needed given each new score. This approach can be used to pass all three subtasks.
Another approach is to first store a collection of all the scores in
a data structure (e.g. in a list in Python or an ArrayList
in Java). Then the maximum score (gold score) can be calculated and all
occurrences of this score removed from this collection. Then the new
maximum score (silver score) can be calculated and all occurrences of
this score removed from the updated smaller collection. The maximum of
the scores remaining in this even smaller new collection is the bronze
score and the number of times it occurs can be computed and printed.
This approach will pass the first two subtasks. Whether or not this
approach passes the last subtask depends on how computing and removing
occurrences of the maximum score is implemented. As long as this is done
by passing over the collection a fixed/constant number of times (i.e.
increasing the size of the collection does not affect how often a pass
is made over the collection), this approach should also pass the third
subtask.
Sorting can also be used here. After sorting the scores, the bronze score can be identified quickly for the first subtask where the scores are distinct. Otherwise, a loop is needed to scan from highest to lowest score effectively finding the "boundaries" between the gold and silver scores and between the silver and bronze scores. Any built-in sorting function/method should be fast enough to pass the last subtask. It is also possible but challenging to implement a sorting algorithm which will be fast enough to earn full marks with this strategy.
It can take some time to wrap your head around the behaviour of Alex’s strange keyboard. To help us discuss it here, we will refer to the following five values.
pressed – the first line of input representing the
keys pressed by Alex
displayed – the second line of input representing
the letters displayed on the screen
silly – the letter corresponding to the silly
key
wrong – the letter displayed when the silly key is
pressed
quiet – the letter corresponding to the quiet
key
For the first subtask, the quiet key is not pressed which means that
the letter in pressed that is not in displayed
must be silly. Also, wrong must be the letter
that is in displayed but not in pressed.
Finding a character that appears in one string but not the other can be
done with a loop and search. The search can be accomplished with a
built-in function or nested second loop. (In general, we can check
whether or not the quiet key is pressed by comparing the lengths of
pressed and displayed.)
For the other subtasks, we can still begin by determining
wrong as above. Similarly, we can determine a pair of
letters x and y that correspond to
silly and quiet, but we need to work a bit
harder to determine whether x corresponds to
silly and y corresponds to quiet,
or the other way around. For the second subtask, we can use the fact
that the first troublesome key pressed is the silly key. Otherwise, one
way to do this is to simulate Alex’s keyboard by replacing all
occurrences of x in pressed with
wrong and removing y from
pressed. It the result equals displayed then
we know that x corresponds to silly and
y corresponds to quiet. Otherwise, we know
that it is the other way around. To solve the final subtask where a
large number of keys are pressed, the number of times we pass over the
input strings cannot depend on N, the bound on their
lengths. This can be achieved by storing the letters in
pressed and displayed in a data structure that
allows for efficient searches (e.g. a dictionary in Python or
HashMap in Java.)
This problem can also be solved without predetermining
wrong and candidates for silly and
quiet. We can scan pressed and
displayed left to right looking for the first place where
they differ. For the second subtask, we then immediately know that
silly must be the mismatched character in
pressed and wrong must be the mismatched
character in displayed. To determine quiet (if it was
pressed), we can continue scanning until we find a mismatch that does
not involve silly. We omit the details here, but for the
third and fourth subtasks, we can extend this approach by considering
cases and simulating the behaviour of Alex’s keyboard once we determine
silly or quiet.
For the final problem in this year’s competition, the fundamental task is to determine all the locations that the farmer can reach. By "visiting" each of these locations and summing the values of the pumpkins at these locations, we can produce the total value harvested by the farmer. This requires us to store the pumpkin patch in memory which must ultimately be done with a two-dimensional structure (e.g. a list of strings or two-dimensional array).
For the first subtask, the farmer can reach every location. Visiting every location can be done with a nested loop.
For the second subtask, we can begin at the farmer’s starting location and move in one direction until blocked by hay or the edge of the patch. Since we know that the locations the farmer can reach form a rectangle, doing this up, down, left and right, allows us to determine the dimensions of the rectangle and the location of a corner of the rectangle. This allows us to use a nested loop as in the first subtask to visit all the locations that the farmer can reach.
A different strategy is required for the final two subtasks. We can
maintain a collection of locations to visit. Initially this collection
will consist only of the starting location of the farmer. Then we can
repeatedly remove a location from the collection and if it has not yet
been accounted for, add the value of the pumpkin at this location to a
running total. Also, since the farmer can only move in four possible
directions, every location we visit presents up to four potential new
locations to add to the collection. Locations should not be added if
they are not reachable (contain hay or do not exist because we are at
the edge of the patch) or if they have already been accounted for. One
clever way to record that a location has been accounted for is to change
the S, M or L at that location to
a *. This general technique is an example of what is called
a flood fill algorithm.
Notice that the collection of locations to visit can theoretically grow very large and contain many duplicates. This is because, for example, visiting the location at row 4 and column 7 could result in us adding the location at row 3 and column 7 to the collection, but this same location might be added when visiting row 3 and column 8 (or row 2 and column 7, or row 3 and column 6). Avoiding this is needed to earn 15 marks.
Depending on how the collection is implemented, the full solution
described here is called breadth-first search (BFS) or
depth-first search (DFS). DFS can also be implemented using a
recursive function or method which is a function or method that
calls itself. For recursive functions, the collection is implicit and
stored in a portion of memory usually referred to as the call
stack. Different languages and machines can put different limits on
how large the call stack can be. Python tends to be especially
restrictive and so using recursion and Python for this problem likely
requires you to instruct the system to make enough room by importing the
sys module and issuing a command such as
sys.setrecursionlimit(100000).