2021 Waterloo CCC Junior Problem Solutions

In this tutorial, we are going to look at an explained solution of the problems in the Programming contest (Junior Division) on Canadian Computing Competition 2021. 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!

CCC 2021 Problem J1: Boiling Water

This is a pretty straightforward problem. Let’s understand the problem first then we will move into the solution. We will be given the temperature of the water at which water begins to boil (Also known as a boiling point). By using the formula in the problem description, we need to find out atmospheric pressure in kPa. The formula is:

𝑃   =   5   ×   𝐵   − 400

Here,

P = atmospheric pressure

B = boiling point

After using the formula, we have to print the value of P.

Then, based on the following conditions, we have to determine if we are below sea level, at sea level, or above sea level.

Conditions:

If atmospheric pressure is smaller than 100 kPa, then we are above sea level. So we will print 1

If atmospheric pressure is 100 kPa, then we are at sea level. So we will print 0

If atmospheric pressure is greater than 100, then we are above sea level. So we will print -1

So, before going to code, we have to take a look at the input and output specifications. Remember, we need to write our code in such a way that we can enter our value of B exactly as given. No prompt message will be required. Similarly, the output of the code will also have to be exactly as told in the output specification. The sample output is case-sensitive so we need to be careful about that.

Time complexity:

Since we are not using any for loop here and for every case of input, we have to perform the similar task, we can say that the time complexity of this problem is constant or 𝑂(1).

Python Code:

B = int(input())
P = 5 * B - 400
print(P)
if P  < 100:
    print(1)
elif P == 100:
    print(0)
else:
    print(-1)

CCC 2021 Problem J2: Silent Auction

In our second problem, we will be given a positive integer N. This N is representing the number of bidders. Then, we will be given N pairs of input containing the name and his/her bid. Our job is to print the name of the highest bidder.

At first, we will take input of N. Then, we will initialize a variable named max_bid which will be set to -1. Next, we will take a for loop which will iterate N times. In the for loop, we will take input of our bidder name and his/her bid respectively. Now, we will compare the current_bid with our max_bid variable. If the current bidder has a higher bid than the previous max_bid then we will store his/her name in the winner variable and also set the max_bid to current_bid value.

Finally, the winner variable will contain the name of the highest bidder. So, we will print the value of the winner variable.

Time Complexity:

There is a for loop in this code. It will iterate N times. Other parts of the code will have a constant time complexity. So,

Time Complexity = 𝑂(𝑛)

Python Code:

N = int(input())
max_bid = -1

for i in range(N):
    name = input()
    current_bid = int(input())
    if max_bid < current_bid:
        winner = name
        max_bid = current_bid

print(winner)

‍

CCC 2021 Problem J3: Secret Instructions

In this problem, we are trying to decode a sequence of code given by Professor Santos. We will be given some input lines. Each input line will contain a string of 5 characters.

Now, we have to decode these 5 characters. Here, the first two characters represent the direction to run. So, we will convert these two characters to integers and find the sum of them. Then we will determine the direction by following conditions:

If the sum is odd then the direction to turn is left.

If their sum is zero, then the direction won’t be changed so we will pass and

If their sum is even and not zero, then the direction to turn is right.

We can find if a number is even or odd by dividing it by 2 and checking if the reminder is 0 or 1. We can use mod (%) for this. For instance, 3 is an odd number. So 3%2 = 1. Again, 6 is an even number. So 6%2 = 0.

Finally, the rest 3 characters of the input line determine the number of steps that need to be taken. We can use the python split

function for this. Code[2:] means, it will slice the string from index 2 to its end. See the diagram to understand the decoding process clearly.

‍

‍

Now, we will use while True: which is an infinite loop. The last line of our sequence will contain 99999 which is actually an indication that our sequence is finished. So, we can use an if condition to break get out from the infinite while loop.

Before seeing the code, I would like to encourage you to try it out yourself first. You can also use the following flowchart while coding.

Time Complexity: The while loop will break after the last input which is 99999. Assuming, there will be n instruction codes that we have to decode. Then the while loop will run n times.

Therefore,

Time Complexity = 𝑂(𝑛)

‍

‍

Python Code:

direction = ''
while True:
    code = input()

    if code == "99999":
        break

    sum_of_first_two_digit = int(code[0]) + int(code[1])
    if sum_of_first_two_digit %2 == 1:
        direction = "left"
    elif sum_of_first_two_digit == 0:
        pass
    else:
        direction = "right"

    step = code[2:]
    print(direction +" " + step)

‍

CCC 2021 Problem J4: Arranging Books

This problem is a little bit hard for a junior problem. In this problem, we have a bookshelf containing three types of books (Large-sized, Medium-sized, Small-sized) and they are randomly stored on the bookshelf. Valentina wants to rearrange the books so that all the large books appear on the left, followed by all the medium-sized books, and then all the small books on the right. She does this by repeatedly choosing any two books and exchanging their locations. A position exchange between 2 books is called a swap. So, we need to find out the minimum number of swaps needed to arrange the bookshelf so that all large books are on the left, medium books are in the middle and small books are on the right side of the shelf.

‍

To solve this, at first, we will divide the bookshelf into three sections (L, M, S). Length of L section will be the number of large books, Length of M section will be the number of medium-sized books and Length of the small section will be the number of small books. Now, you will see, each section has some books which are correctly placed and some books which are wrongly placed. Now, after sectioning, we will start swapping.

Before proceeding, we need to understand the swap. Please see the diagram here.

While we are dealing with 3 different-sized books, we need to deal with two cases. In case 1, a single swap can put two books in the right place. As you can see by swapping C and A, both C and A are in their right place. On the other hand, in case 2, swapping two books at once can put only 1 book in the right place. We need to swap again to put the second book in its correct place. In the picture, even though we swapped A and C at first, A got its correct position but C does not. So, C needs to swap again with its correct positioned wrongly placed books.

‍

‍

As you can see we need two kinds of swapping to put any two wrongly placed books in their correct place. So we need to keep track of wrongly placed books in each section. Now, we will find out how much single swap is needed in the entire self. To do that, we need an array for each section where the number of books based on type will be stored. Now, we will need min(section_L[1], section_M[0]) single swaps between Large and Medium books from the medium section and large section respectively. Similarly, we will need min(section_L[2],section_S[0]) single swaps between Large and Small books from the small section and large section respectively. Again, we will need min(section_M[2],section_S[1]) single swaps between Medium and Small books from the small section and medium section respectively. Thus, adding all these three values will give us the total number of single swaps (Swap Case 1).

After that, we have to update our Section_L, Section_M, and Section_S based on single swapping. Now, the trick of counting double swaps (Swap Case 2) is just adding the wrongly placed books in a single section as after single swapping, only those books are remaining which are needed double swapping. Remember to multiply 2 while calculating double swap because as the name suggested, we need to swap 2 times to put the books in the correct place. Finally, adding the number of single swaps and double swaps will give our desired output.

Time Complexity = 𝑂(2𝑛), where n is the number of books.

Python Code:‍

shelf = input()
# A function to count the number of books
def get_count(shelf : str) -> list:
    count = [0, 0, 0]
    for book in shelf:
        if book == 'L':
            count[0] += 1
        elif book == 'M':
            count[1] += 1
        else:
            count[2] += 1
    return count

# Counting the number of Large, Medium and Small books in the shelf
L_total_count, M_total_count, S_total_count= get_count(shelf)

# Counting the number of Large, Medium and Small books in each section
section_L = get_count(shelf[:L_total_count])
section_M = get_count(shelf[L_total_count:L_total_count+M_total_count])
section_S = get_count(shelf[L_total_count+M_total_count:])

# Counting the number of single swap needed
singleSwap = min(section_L[1], section_M[0]) + min(section_L[2],section_S[0]) +min(section_M[2],section_S[1])



# Updating the count of each section after all single swap
s = 0

if section_L[1] < section_M[0]:
    s = section_L[1]
else:
    s = section_M[0]
section_L[1] -= s
section_M[0] -= s
section_L[0] += s
section_M[1] += s

s = 0

if section_L[2] < section_S[0]:
    s = section_L[2]
else:
    s = section_S[0]
section_L[2] -= s
section_S[0] -= s
section_L[0] += s
section_S[2] += s

s = 0

if section_M[2] < section_S[1]:
    s = section_M[2]
else:
    s = section_S[1]
section_M[2] -= s
section_S[1] -= s
section_M[1] += s
section_S[2] += s

# Counting the number of double swap needed

doubleSwap = 2* (section_L[1] + section_L[2])

# Printing the output
print(singleSwap+doubleSwap)

CCC 2021 Problem J5/S2: Modern Art

This problem is a little bit tricky, but once you get the main idea you will be amazed to see how we can solve lengthy problems using simple mathematical and logical tricks. In this problem, we will be given an M by N grid type canvas where every cell will be black initially. Our artist will pick either a row or column, and run their magic brush which will change the color to black to gold or gold to black. After K times of stroking the canvas, we have to find out how much cell is colored in gold.

You can see how the painting works and why sample input 1 has 4 gold cells after painting row 1 and column 1.

Now, we can use the brute-force method by making an MxN grid and changing the value of the grid based on each stroke. But in order to get full marks in this problem, you have to consider out the last batch in input specification where the value of 𝑀𝑁 ≤ 5 000 000 and 𝐾 ≤ 1 000 000. Any brute force method will exceed the given time limit in the python programming language. So, we need to think carefully and find a shortcut way to determine if a cell is gold or black after all operations.

As you can see, if a cell gets 1 stroke, it changed to gold. If the cell gets 2 strokes, it will be black. If the cell gets 3 strokes then it will be gold again. You can see a pattern here. If a cell gets N strokes, then if N is odd then the cell will be gold otherwise it will be black. Now, a cell can be stroked by both a row stroke and a column stroke. So, for each cell, we have to check if the sum of the column stroke and row stroke is odd or not. If odd, then we will count them as gold cells. Look at the diagram for further clarification.

I hope you get the idea. Now let’s start coding. At first, we will take input of M, N, K. Now, initialize two array rows and cols. Then we will increment the value of rows and cols array based on row stroke and cols stroke and their index. After that, we will initialize count = 0 and will check for each cell if it’s gold or not by checking if it has been stroked odd times or even times respectively. If a cell is gold then we will add 1 in the count variable. Finally, we will print count.

Time Complexity:

There is one for loop which will run K times and one nested for loop which will run MxN times. So,

Time complexity = 𝑂(𝐾 + 𝑀𝑁)

Python Code:

M = int(input())
N = int(input())
K = int(input())
rows = [0]*M
cols = [0]*N

for i in range(K):
    stroke = input().split()
    direction = stroke[0]
    index = int(stroke[1])-1
   
    if direction == 'R':
        rows[index] += 1
    else:
        cols[index] += 1

count = 0
for i in range(M):
    for j in range(N):
        if (rows[i] + cols[j]) %2 == 1:
            count += 1

print(count)

‍

‍