Waterloo CCC 2019 Junior Problem Solution

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

ProblemJ1: Winning Score

‍

This is a very easy problem. At first, let’s dive into the problem and understand what the problem is referring to, then we will see the solution.

In this problem description, our job is to determine which team will win, (Team Apple or Team Banana) or if the game ended in a tie.

Input description:

A1=First score of the team Apple

A2=Second score of the team Apple

A3=Third score of the team Apple

B1=First score of the team Banana

B2=Second score of the team Banana

B3=Third score of the team Banana

This is how we will take the input.

We see the scoring system at a basketball game as a 3-point shot, a 2-point field goal, or a 1-point free throw. For each team, the first score is the 3-pointshots, the second score is the 2-point field goals, and the third score is 1-pointfree throws. So the formula stands-

A1 × 3 + A2 × 2 + A3 × 1 = total score (in case of team Apple)

B1 × 3 + B2 × 2 + B3 × 1 = total score (in case of team Banana)

Flow-chart:

‍

CCC 2019Junior Problem

‍

Now, using the formula we will get the team’s score. We have to print “A” if team Apples scored more points than the team Bananas or “B”  If the team Bananas scored more points than the team Apples, otherwise “T” which indicates a tie.

Before looking at the solution to the problem, we have to make sure our code takes the input exactly as the sample input is given in the problem. Also, we have to make sure to give the desired output in the exact format it was wanted in the question.

Python Code:

A1 = int(input())
A2 = int(input())
A3 = int(input())

B1 = int(input())
B2 = int(input())
B3 = int(input())


appleTotalscore = A1*3 + A2*2 + A3*1
bananaTotalscore = B1*3 + B2*2 + B3*1

if appleTotalscore > bananaTotalscore:
    print("A")

elif bananaTotalscore > appleTotalscore:
    print("B")

else:
    print("T")

Time complexity:

As 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. The complexity of this problem is constant or 𝑂(1).

‍

CCC 2019 Junior Problem J2: Time to Decompress

In our second problem, you and your friend find a way to send messages back and forth. Your friend can encode a message which is written with a positive integer N and a symbol. For example , N = 4 (here 4 is a positive integer ) and symbol = “+” (a plus symbol). And you will be able to decode the message from your friend by writing down out that symbol N times in a row on one line.

Input description:

n =int(input())

Here the first line implies a number of lines in the message

lines= input().split(“ ”)

The second line implies that each line will contain a positive integer(N) followed by one space, followed by a (non-space) character.

This is how input will be taken.

#Split function

Let me give a short idea of how the split method is working here.

The split() method in python divides a string into a list. For example-

string = "welcome to programming"

s = string.split()

print(s)

output-> ['welcome', 'to', 'programming']

If I elaborate the problem a little bit more, your friend gives a positive integer(N) = 4 with a symbol “+” then you will decode that message by writing “++++”four plus symbol, because here the positive integer (N) = 4 with the “+” symbol means you will write four times of the plus symbol. This is the main part of understanding the problem. If we state a formula it will be, N × symbol

Flowchart:

Python Code:

n = int(input())

decodedMessage = []

for i in range(n):
    lines = input().split(" ")
    N = int(lines[0])
    symbol = lines[1]
    decodedMessage.append(symbol * N)
   
print(*decodedMessage, sep="\n")

Time complexity:

There is a loop in the above code. For this line, for i in range(n): we will get O(n) time complexity.

‍

2019 CCC Junior ProblemJ3: Cold Compress

Our third problem is a little bit tough but once you understand the main concept it will be very easy to understand. In this problem, your cellphone plan charges for every character you send from your phone. As you are sending sequences of symbols in your messages, a technique called compression is implemented. At first, let’s have an idea about the technique.

compression technique:

This compression technique is called run-length encoding. A block of the substring of an identical symbol (++++) followed by other blocks of substring is represented in compressed form. For example- “---+++!!!”. It is a long string with the block which is a substring of identical symbols.

Input description:

n =int(input())

Here the first line implies a number of lines in the message

lines= input()

The second line implies that each line will contain at least one and at most 80 characters, without spaces, i.e (+++===!!!!)

This is how input will be taken.

If I elaborate on the problem a little bit more, let’s consider this string“+++===!!!!”

here4 plus symbols are given, 3 equal symbols are given and 3 exclamatory symbols are given. With this given a sequence of characters in the string, it will encode them in this way which is basically our output. It will be encoded in “3+ 3 = 4 !” in this format. As there was a three-plus symbol so it is encoded “3+” , following “3 =” and “4 !”.

Flowchart:

Python Code:

n = int(input())

string = []

for i in range(n):
    lines = input()
    string.append(lines)

for j in range(n):
    count = 0
    message = " "
    k = string[j]

    for i in range(len(k)):
        if i!=len(k)-1 and k[i]==k[i+1]:
            count=count+1
        else:
            message = message+" "+str(count+1)+" "+k[i]
            encodedMessage = message[2:len(message)]
            count = 0
           
    print(encodedMessage)

‍

Time complexity: 0(n X 80) ≈ 0(n) 

2019 CCC Junior Problem J4/S1: Flipper:

This problem is a little bit tricky but if you can understand how horizontal and vertical flip is working it will be a piece of cake for you. There is a grid off our numbers:

At first, let us understand how flipping the grid horizontally or vertically would change the grid. When you will do a “horizontal” flip the original grid change in a horizontal manner. Similarly, if you do a “vertical” flip the original grid change in a vertical manner.

Horizontal flip

Vertical flip

In this way, your task is to determine the final gid after a sequence of horizontal and vertical flips.

Note:

two vertical flips -> no change in the grid

two horizontal flips -> no change in the grid

Input description:

Line= input ()

This line of input consists composed of a sequence of at least one and at most 1 000000 characters. Each character is either “H” (horizontal flip) or “V” (vertical flip).

‍

Python Code:

‍

line = input()

grid = [[1,2],[3,4]]

def horizontalFlip(grid):
    grid[0],grid[1] = grid[1],grid[0]
    pass

def verticalFlip(grid):
    temp = [grid[0][1], grid[0][0] ]
    temp1 = [grid[1][1] , grid[1][0] ]
    grid[1] = temp1
    grid[0] = temp
    pass


for i in range(len(line)):
    if line[i] == "H":
        horizontalFlip(grid)
    else:
        verticalFlip(grid)

for i in grid:
    for k in i:
        print(k, end=" ")
    print(" ")

Time complexity: 0(n) +0(2X2) ≈ 0(n)

‍

2019 CCC Junior Problem J5: Rule of Three:

This problem is a bit tricky. But once you understand the concept you will get a grip on it.

A substitution rule:

In this rule, a sequence of symbols is converted into a different sequence of symbols. In this problem, three substitution rules are given.

1. AA → AB

2. AB → BB

3. B → AA

Here for the string AA is a starting sequence of symbols and AB is a final sequence of symbols. Basically, string AA will be converted to string AB. The same rules apply to the other two substitution rules. Let me explain how this works.

Let us take a sequence “AA” and we will turn it into a new sequence “AAAB” in 4steps. According to 1st substitution rules, this sequence will be turned to “AB”. Then applying 2nd substitution rule sequence “AB” will turn to “BB”. Again using the 3rd substitution rule first “B” of sequence “BB” will turn to “AA”, and we will get “AAB”. Then again applying the 3rd substitution rule, “B” of sequence “AAB” will turn to “AA”. So the sequence we will get is “AAAA”. Now once again, using substitution rule 1 we will get “AAAB” which is our final sequence.

AA → AB→ AAB→ AAAA→ AAAB

There placed symbols in the sequences are marked bold in blue color.

Note: we will limit the number of steps we will use to convert a sequence into a new sequence.

Input description:

n =input()

Line= n.split()

We will be taking a string by splitting it and the string will contain all substitution rules mentioned. It will be of three lines. The next line will bean integer which is the number of steps we will use to convert a sequence of symbols into a different sequence of symbols along with another sequence of A’s and B’s. And there will be space between them.

Python Code:

‍