In this tutorial, we are going to look at an explained solution of the problems in the Programming contest (Junior Category) on Canadian Computing Competition 2020. The solutions and explanations are made by keeping in mind that this is your first participation in a programming contest. I would suggest you try to code first after reading the explanation and before seeing the solution code. Keep practicing and solving the problems. Happy Coding!
Problem J1: The New CCC (Canadian Calorie Counting)
This is a pretty straightforward problem. We have a simple menu with burgers, drinks, side orders, and desserts, and every item has 3 variations. Each variation has its own amount of calories. Our user will choose 1 variation from each item. We have to find out the total calories of selected meals.
We will make 4 lists in python for each item. Their first index [0] will be set to 0 because indexing in the array starts with 0 and our choices start from 1. The last index [4] of each array will be set to 0 too because it means no order. Then, we will print our welcome text and start taking input of each food item. Finally, we will add all the calories and print the total calories.
Look at the flow diagram below while solving before seeing the code.
Time Complexity: Since we are not using any for loop here and for every case of input, we have to perform similar task, we can say that the time complexity of this problem is constant or O(1).
Python Code:
Problem J2: Roll the Dice
In this problem, we will have 2 dices. Each of them will have m and n sides which we have to take input from our user. Then we have to count in how many ways we can get a sum of 10 from this two m and n sided die.
The trick for this problem is, we have to subtract each side of the first die and check if it is less than or equal to the maximum value of the second die which is n. We also have to check if the result of subtraction is greater than 0 or not. In this way, we can find if that side of the first die can help to make the sum 10.
Also, we have to be careful about the printing statement. If our count is 1 then our printing statement should be “There is 1 way to get the sum 10.” Otherwise, “There are {count} ways to get the sum 10.”
Look at the flow diagram below while solving before seeing the code.
Time Complexity: The time complexity of this code will be O(N) where N is the number of sides in the first die.
Python Code:
Problem J3: Cell-Phone Messaging
Our third problem is about the old button phones where you had 10 keys for 10 numbers. For buttons 2 to 9, there were 26 letters assigned like the given picture.To get the desired letter, we have to press multiple times based on the position in that key. For example, to write “c” we press the key ‘2’ three times. To write “dada” we press 3232—four key presses. Now each keypress takes 1-second time. We have to pause for 1 second while writing two consecutive letters on the same key. In this problem, we will be given strings, and for each string, we need to calculate the time required to type in this button phone. We have to terminate the program if the given input is ‘halt’.
In order to solve this problem, we are going to use a python dictionary, where, each alphabet will be a key for the dictionary. Values of the dictionary will be the number of buttons we need to press. Now, after taking the input string, we will use a for loop to iterate through the string letter by letter. For each letter, we will find the number of seconds it requires to type and add that to a variable that keeps track of the time. Furthermore, for each letter, we will check if the corresponding key is same to its previous one. If it is, then we need a pause, which will add 2 more seconds in the time variable.
Finally, we need to print the time variable for each string.
Time complexity: The time complexity of this code will be O(N) where N is the number of strings that will be given.
‘
Python Code:
Problem J4: It’s tough being a teen!
This is a hard problem. In this problem, there are some tasks that are indexed from 1 to 7. Some of these tasks have some constraints. For example, in order to perform task 7 (Watch television), you must do task 1 (Do math homework). There are 5 constraints that are already given in the question which are (1,7),(1,4),(2,1),(3,4), and (3,5) where (x,y) indicates that the task is numbered x should be done before the task numbered y.
Now, there will be more constraints that will be given by the user in pairs of numbers. We will stop taking input if the pair of numbers is 0 and 0. We have to output the order of tasks that they should perform while abiding by all the constraints. If it is not possible, then we should print “Cannot complete these tasks. Going to bed.” Note that, it will not be possible to perform some tasks if they have formed a cycle of pre-requisite. For Sample Input 2, look at the following diagram for further clarification.
Here, task 1 needs to be done before task 7, task 7 needs to be done before task 2 and task 2 needs to be done before task 1. So, it is a cycle of pre-requisite.
We will solve this problem using vectors and binary heap data structure. To know more, visit Vector and Binary Heap. Using two vectors task and preRequisite, we will add the constraint first. Then we will take user input and add the additional constraint into those two vectors. Now, we will create a min-heap by initializing a priority_queue PQ and queue sequence. After that, we will push all those tasks which don’t have any pre-requisite.
Now we will use a while loop which will run until our priority queue PQ is not empty. Then, we will push the top value of PQ and pop the last value of PQ. Then a for loop will iterate preRequisite[key].size() times where the following coding snippet will run.
After PQ becomes empty, we will have the order of tasks saved in the sequence variable. Now, if this queue does not have 7 values then it means there is no way to perform the task with given constraints. Then it will print “Cannot complete these tasks. Going to bed.”. Else, we will print the sequence queue.
C++ Code:
Problem J5: CCC Othello
In this problem, we have to make a simulation of the Othello (Reversi) game. Othello is a strategy board game for two players, played on an 8×8 board. There are sixty-four identical game pieces called disks that are white on one side and black on the other. Players take turns placing disks on the board, face-up, with their respective color. During a play, Any disks of the opponent's color in a straight line (vertically, horizontally, and diagonally) bounded by the disk just placed, and another disk of the current player's color are turned over to the current player's color. Look at the following figure for further clarification.
Initially, there will be some disc already placed on the board. In this problem, the game will start with one of the three configurations which are given below.
In this problem, we will be given our configuration a, b or c, then followed by an integer N that represents the number of moves that will be made in this simulation. After that, there will be n pairs of integers which represent the row and column of each move. Our task is to print the number of black and white faced disks on the board after the simulation of given inputs.
To solve this problem, we will use three 2D List for the three configurations first where +1 means black disk and -1 means white disk. Then, based on the user input, we will choose the configuration to play with. The first move will always be black. So, we will use a counter to determine if it is a move of black disk or white disk. Now, for each move, we will put the disk into its cell and then do 8 searches on its 8 sides (up, down, left, right, up-left, up-right, down-left, and down-right). If we find a similar color of the disk in the searches, then we will stop the search and flip all the disks between them. This will be done on all 8 sides. If we don’t find the disk in the linear search, then nothing will happen. You can get a better idea of these searches by looking at the picture below.
Fig 8
We will do these 8 searches for all moves. Finally, we will do a linear search to count how many black and white disks are there on the board and print it as the output of this problem.
Time complexity: The time complexity of this code will be O(N) where N is the number of pairs that will be given.
Python Code:
<code>
a = [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, -1, 1, 0, 0, 0], [
0, 0, 0, 1, -1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
b = [[1, 0, 0, 0, 0, 0, 0, -1], [0, 1, 0, 0, 0, 0, -1, 0], [0, 0, 1, 0, 0, -1, 0, 0], [0, 0, 0, 1, -1, 0, 0, 0], [
0, 0, 0, -1, 1, 0, 0, 0], [0, 0, -1, 0, 0, 1, 0, 0], [0, -1, 0, 0, 0, 0, 1, 0], [-1, 0, 0, 0, 0, 0, 0, 1]]
c = [[0, 0, 1, 1, -1, -1, 0, 0], [0, 0, 1, 1, -1, -1, 0, 0], [0, 0, 1, 1, -1, -1, 0, 0], [0, 0, 1, 1, -1, -1, 0, 0], [
0, 0, 1, 1, -1, -1, 0, 0], [0, 0, 1, 1, -1, -1, 0, 0], [0, 0, 1, 1, -1, -1, 0, 0], [0, 0, 1, 1, -1, -1, 0, 0]]
def stLineLR(flag, initial_dise, x, y):
global z
if flag:
for _ in range(y-1, -1, -1):
if z[x][_] == 0:
return 0
elif z[x][_] == initial_dise:
return 1
else:
z[x][_] *= -1
return 1
else:
for _ in range(y+1, 8):
if z[x][_] == 0:
return 0
elif z[x][_] == initial_dise:
return 1
else:
z[x][_] *= -1
return 1
def stLineUD(flag, initial_dise, x, y):
global z
if flag:
for _ in range(x-1, -1, -1):
if z[_][y] == 0:
return 0
elif z[_][y] == initial_dise:
return 1
else:
z[_][y] *= -1
return 1
else:
for _ in range(x+1, 8):
if z[_][y] == 0:
return 0
elif z[_][y] == initial_dise:
return 1
else:
z[_][y] *= -1
return 1
def DLineRL(flag, initial_dise, x, y):
if flag:
i, j = x-1, y+1
while i >= 0 and j < 8:
if z[i][j] == 0:
return 0
elif z[i][j] == initial_dise:
return 1
else:
z[i][j] *= -1
i -= 1
j += 1
return 1
else:
i, j = x+1, y-1
while i < 8 and j >= 0:
if z[i][j] == 0:
return 0
elif z[i][j] == initial_dise:
return 1
else:
z[i][j] *= -1
i += 1
j -= 1
return 1
def DLineLR(flag, initial_dise, x, y):
if flag:
i, j = x+1, y+1
while i < 8 and j < 8:
if z[i][j] == 0:
return 0
elif z[i][j] == initial_dise:
return 1
else:
z[i][j] *= -1
i += 1
j += 1
return 1
else:
i, j = x-1, y-1
while i >= 0 and j >= 0:
if z[i][j] == 0:
return 0
elif z[i][j] == initial_dise:
return 1
else:
z[i][j] *= -1
i -= 1
j -= 1
return 1
dict_type = {'a': a, 'b': b, 'c': c}
inp_t = input().split()
z = list(dict_type[inp_t[0]])
cnt = 0
for i in range(2, len(inp_t), 2):
x, y = int(inp_t[i])-1, int(inp_t[i+1])-1
if cnt % 2 == 0:
z[x][y] = 1
else:
z[x][y] = -1
cnt += 1
f_1 = stLineLR(True, z[x][y], x, y)
if not f_1:
stLineLR(True, z[x][y]*-1, x, y)
f_1 = stLineLR(False, z[x][y], x, y)
if not f_1:
stLineLR(False, z[x][y]*-1, x, y)
f_2 = stLineUD(False, z[x][y], x, y)
if not f_2:
stLineUD(False, z[x][y]*-1, x, y)
f_2 = stLineUD(True, z[x][y], x, y)
if not f_2:
stLineUD(True, z[x][y]*-1, x, y)
f_3 = DLineLR(True, z[x][y], x, y)
if not f_3:
DLineLR(True, z[x][y]*-1, x, y)
f_3 = DLineLR(False, z[x][y], x, y)
if not f_3:
DLineLR(False, z[x][y]*-1, x, y)
f_4 = DLineRL(True, z[x][y], x, y)
if not f_4:
DLineRL(True, z[x][y]*-1, x, y)
f_4 = DLineRL(False, z[x][y], x, y)
if not f_4:
DLineRL(False, z[x][y]*-1, x, y)
b, w = 0, 0
for _ in range(8):
b += z[_].count(1)
w += z[_].count(-1)
print(b, w)
</code>
.png)
