COMP 321: Programming Challenges Assignment 3

COMP 321: Programming Challenges
Assignment 3
This assignment includes two problems, one problem on kattis and one separate.
Please remember that the assignment must be solved individually. What I expect from
you is to upload the following in the “Assignment 3” folder:
1) The codes that you used for solving the problems. The files must be named
Problem_ IDi.extension, where ‘Problem’ is the problem ID, IDi is
your McGill id and ‘extension’ is the program extension (.java).
NOTE: Make sure to add comments to your code.
2) A .pdf file for kattis problems. This .pdf must be named Assignment3_IDi.pdf, where
IDi is your McGill id number. Inside the pdf file, include a screenshot of the acceptance
notification that you received on your Kattis account. Please make sure your name
appears in it.
The due date for this assignment is Sunday October 7th before 11:59 PM.
A. Kattis problem
For this assignment, we will solve the following problem on kattis:
1. All about that base: https://open.kattis.com/problems/allaboutthatbase
B. Separate problem
Problem: Sofas Collection
ProblemID: sofas
Mr. Caron owns a small company, called Gazo, selling home furniture in a French village.
Mr. Caron buys the furniture from a bigger company, called Mazo, and sells it at slightly
higher costs to make a profit. Today, he found a good deal at Mazo on nice sofas. These
sofas are each characterized by a style and a color. There are 36 different styles and 36
different colors. In total, there are 1296 different sofas. However, today, not all these sofas
are available at Mazo.
To satisfy customers and still take advantage of the deal, Mr. Caron decided to get from
Mazo today all combinations of 𝑘 styles and 𝑘 colors, for a 𝑘 value that is as large as 
possible. However, he has discovered that determining this 𝑘 for a given collection is not
always trivial. Can you help him?
Input
On the first line of the input, there is a single positive integer 𝑛, telling the number of test
scenarios to follow. Each test scenario begins with a line containing a single positive
integer 𝑚 ≤ 100, the number of sofas available at Mazo. Then follow 𝑚 lines, one per
sofa, each with a pair of numbers, 𝑠𝑖 and 𝑐𝑖
, separated by a single space,
where 𝑠𝑖
(0<𝑠𝑖≤36) indicates the style of the 𝑖th sofa, and 𝑐𝑖
(0<𝑐𝑖≤36) indicates its color.
Output
For each test scenario, output one line containing the maximum 𝑘, such that there
are 𝑘 styles and 𝑘 colors for which Mr. Caron’s sofas collection contain all 𝑘 ⋅
𝑘 combinations of those styles and colors.
Sample Input 1
2
5
11 13
23 5
17 36
11 5
23 13
2
23 15
15 23
Sample Output 1
2
1