Waterloo CCC 2014 Junior Problem Solution

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 2014. 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!

For 2014 Waterloo Canadian Computing Competition, more information can be checked here.

‍

2014 CCC Junior Problem J1: Triangle Times

This is a pretty straightforward problem. We know, based on sides, triangles can be classified into three types. These are: Scalene Isosceles and Equilateral. We will be given 3 angles of a triangle as input. We have to determine what type of triangle it is.

The sum of all angles in a triangle is 180 degrees. If the sum of our given angles is not 180 degrees then we can not make a triangle from these angles. So, we will print Error.

Now, if the sum is 180 degrees, then it has to be one of the types of a triangle based on angles. We will use conditions to find out if all three angles are 60 or not. If it is, then we will output Equilateral. If not, then we will check if any two angles are equal. If it is then it is an Isosceles and if not then it is a Scalene. Look at the flowchart if you need further clarification.

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:

angle1 = int(input()) angle2 = int(input()) angle3 = int(input())
if angle1+angle2+angle3 != 180: print("Error")
elif angle1 == 60 and angle2 == 60 and angle3 == 60: print("Equilateral")
elif angle1 == angle2 or angle2 == angle3 or angle3 == angle1: print("Isosceles")
else:
print("Scalene")

‍

‍

2014 CCC Junior Problem J2: Vote Count

In this problem, we have to count votes for a singing competition and determine the result. This is an easy problem.

At first, we will be given the number of votes. Then we will be given a string where each character contains either A or B representing the singer A and Singer B. We have to count the number of A and B in that string. Based on the given conditions, we will print the name of the winner. We will print Tie if A and B got an equal amount of votes.

Look at the flowchart if you find trouble while coding.

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:

no_of_voters = int(input()) votelist = input()
voteA = 0
voteB = 0
for vote in votelist: if vote == 'A':
voteA += 1 else:
voteB += 1 if voteA > voteB:
print("A")
elif voteA == voteB: print("Tie")
else:
print("B")

‍

‍

Problem J3: Double Dice

In this problem, two players will play a game. In this game, both players will start with 100 points. Now, we will be given n which denotes the number of rounds that will be played. Then, in each round, both players will roll their die. Now, if both players roll the same number, then nothing will change in their points. It’s a tie. Now, if a player rolls the lower number than the other player, then he/she will lose x points. Here, x is the number of higher rolls. Finally, we have to print the score of both players.

Here, for each round, we will be given a line that contains the number of two dice rolls. Between two numbers, there will be a space. We can use the python split function for differentiating that.

Look at the flowchart if you find trouble while coding.

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()) Antonia = 100
David = 100
for i in range(n):
dices = input().split() AntoniaDice = int(dices[0]) DavidDice = int(dices[1]) if AntoniaDice > DavidDice:
David -= AntoniaDice
elif AntoniaDice < DavidDice:
Antonia -= DavidDice print(Antonia)
print(David)

‍

2014 CCC Junior Problem J4: Party Invitation

This problem can be solved in many ways. Here, we will be given a number of friends as input. Then we have to number our friends like 1,2,3……. After having our friend list, we will be given how many rounds we will do the removing process.

In each round, a number r will be given, where we have to remove those friends who are in those positions where the index number is divisible by r. For example, if we have 5 friends, and we would like to do 2 rounds of the removing process, then the removing process will be like the following diagram. Let, r = 3 for first round and r = 2 in second round.

So, for this example, we have to print 1 and 4. The trick is we are removing those friends who have the position that is divisible by r. Each round, their position will be updated. We can solve this by this kind of removal process.

But removing a value from an array in a loop can cause issues. So, we will think of another way for this solution. Instead of finding those positions which are divisible by r, we will find out those positions which are not divisible by r. Then we will append the value of that position to a temporary selected_friends array. After the removing process, we have to update our friendList to selected_friends. In this way, we don’t have to face any issues regarding deleting the values of an array.

Time Complexity: If there are n friends and we do r removing process. Then the time complexity of this code will be 𝑂(𝑛𝑟)

Python Code:

no_of_friend = int(input()) friendList = []
for i in range(no_of_friend): friendList.append(i+1)

rounds = int(input()) for i in range(rounds):
r = int(input()) selected_friends = []
for j in range(len(friendList)): if (j+1)%r != 0:
selected_friends.append(friendList[j]) friendList = selected_friends

for i in friendList: print(i)

‍

2014 CCC Junior Problem J5:

This last problem can be solved using a dictionary or two lists. Here, we will be solving this using two lists.

At first, we will be given an integer n which refers to the number o students in the class. Then, we will be given two strings of names divided by a space. Now, we can use the pythons built-in split() function to convert these two strings into two lists. Now, if we think of these two lists vertically, we can see that their index is like a serial number for the students. For example, if we have 4 students A, B, C, D, then the vertical list should look like the following diagram.

So, we can see here A and D are a pair in both the 0th index and 3rd index. Also, B and D are also a pair in both the 1st and 2nd index. You can see the logic here for a consistent pairing. First of all, both lists have the same value in different indexes. So, if A is in the 0th index in pair1 and its pair D is in 0th in pair2 then D must be in the same index of pair1 in which A is in pair2 for a consistent pairing otherwise it is not a consistent pair. To understand this logic more clearly, look at the following coding snippet and diagram.

pair1[i] != pair2[pair1.index(pair2[i])]

‍

Another condition for a bad consistency is if anyone is a partner of himself. We can easily check that by pair1[i] == pair2[i]. Now, we have to check this for the entire list. If we find a bad pair, then we can conclude that it is a bad pair and print bad. If we don’t find any bad pairing then we will print good.

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())

pair1 =[i for i in input().split()] pair2 =[i for i in input().split()]

state = True
for i in range(n):
if pair1[i] != pair2[pair1.index(pair2[i])] or pair1[i] == pair2[i]: print("bad")
state = False break

if state:
print("good")

‍