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 it 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.
A solution to the first problem requires a conditional statement such as an ifstatement. When the condition \(N \leq C \times P\) is true, yes should be printed, and otherwise no should be printed.
The second problem asks you to determine the number of donuts remaining when the donut shop closes. This requires you to store the initial number of donuts \(D\) and then update the total number of donuts remaining after each event. Since we are given the number of events, \(E\), we can use a for loop to do this. For each iteration of the loop, we can read two lines of input and use a conditional statement to determine whether to add or subtract from the current donut total. Note that the symbol + or - must be represented
by a character or string type, and the quantity of donuts associated with the event should be represented by an integer type.
Most correct solutions to the third problem will use an outer loop that iterates \(N\) times. Each iteration will process an original product code and output the corresponding new product code.
To process an original product code, you need to consider each character individually. You can choose to do this as you read in a line of input or you can read the full line at once as a string and then walk through the string from left to right. Either way, an inner loop is needed.
No matter how you handle the characters, you effectively have to break the input into tokens. There are four types of tokens: lowercase letters, uppercase letters, positive integers and negative integers. The marks were distributed across four subtasks to recognize the fact that the difficulty increases as the number of token types increases and more significantly, when the tokens vary in length.
There are many decisions to make when implementing and structuring the processing.
You can first split the entire input into tokens, store them in a sequence of some type, and then handle each token, or you can recognize and handle tokens as you read the input.
You can choose to handle each type of token separately. For example, you could first concatenate all the uppercase letters. Alternatively, as you recognize each token, you can use its type to determine what action is required.
Once you reach the start of an integer, you can use another (more deeply nested) inner loop to find where it ends. Alternatively, you can record your current "state" (e.g. represent that you are in the middle of building an integer and whether it is positive or negative) and use the previous and current states to act accordingly.
The output can be printed as it is determined, or the complete line of output can be built as one string and printed all at once.
The key to helping Jeremy determine the maximum possible number of consecutive days with sunshine is to develop an algorithm. Of course, you then need to implement the algorithm, but to maintain focus, it can be very helpful to separate these two tasks.
To solve the first subtask, it is useful to count the number of S characters. It is then tempting to say that the correct answer is one more than this total. This is correct except for one special case. If there are no P characters, then the answer is \(N-1\) corresponding to when the data is incorrect for the first day or last
day.
The simplest algorithm to solve the general problem is probably to read and store the entire input, and consider the \(N\) possible cases for the one day that the data is incorrect. For each of these cases, you can first "flip" the corresponding S to P or vice versa and then scan the result for the longest sequence of S characters. This approach can earn full marks for the first two subtasks but will be too slow for the last subtask when \(N\) can be as large as \(500\,000\). In general, if an outer loop iterates this many times and for each iteration an inner loop also processes this much data, the algorithm will probably be too slow. Sometimes the inner loop can be hidden inside a built-in function. For example, search functions and string concatenation are notorious for slowing code down in this way.
We can avoid this slowdown and solve the last subtask by processing the data only once. Ignoring the special case of only S characters, the maximum possible number of consecutive days with sunshine will be the length of the longest string that consists of either (i) only S characters preceded or followed by exactly one P character, or (ii) only S characters followed by exactly one P character followed by another string of only S characters. To find the longest such string, there are parallels to J3 in that you more or less need to tokenize the input into blocks of S characters and blocks of P characters. If you wish, you can store the lengths of these blocks instead of the blocks themselves. Regardless, since we only need to consider up to three blocks in a row, all this can be done in one loop without too many steps per iteration.
For this question, we will talk about finding an optimal path for Ava that starts at the upper territory and ends at the lower territory but it doesn't really matter which direction you consider.
The first subtask gives us a clue on how to proceed. There are only two ways to reach the first or last tile in the second row, while there are three ways to reach each tile in between. Therefore we can quickly calculate the minimum cost to get to each of the tiles in the second row. Our final answer will be the minimum of these \(C\) minimum costs.
That is where the clue lies, because once we determine the minimum cost to get to each tile in the second row, we can ignore the first row, and consider the second and third rows as a repeat of the first subtask.
The general idea here is that we are solving the problem of determining the minimum cost to get to each tile in a row by first solving the "subproblem" of determining the minimum cost to get to each tile in the previous row. These subproblems can be solved by using recursion. That is, most of the work can be done by a function called solve that calls itself containing a line similar to:
return G[r][c] + min(solve(G,r-1,c-1),solve(G,r-1,c),solve(G,r-1,c+1))G[r][c] is the minimum cost to get to the tile in row \(r\) and column \(c\). This approach will earn \(11\) marks by solving the second subtask. It will be too slow to tackle grids with \(100\) rows and \(100\) columns because it will often solve the same subproblem many times. (Can you see why?) One way to overcome this hurdle is to use a technique called memoization which involves storing solutions to subproblems so they don’t
need to be be recalculated. Alternatively, you can use nested loops instead of recursion to walk through the grid from the upper row to the lower row storing the "answer" at each tile you encounter. This works because you will always know the answer to each subproblem you need, when you need it.
These approaches are examples of what is called dynamic programming. They were described in a way that suggests the full grid be stored in memory and be used to solve solutions to subproblems. That will work for the third subtask but will use up too much memory when the grid grows to \(20\,000\) rows and \(20\,000\) columns. This can be avoided, and full marks earned, by realizing you only need to store "answers" for the previous and current rows.