Your cart is currently empty!
Problem Description The 2018 FIFA World Cup will be the 21st FIFA World Cup, a quadrennial international soccer tournament contested by the men’s national teams of the member associations of FIFA. It is scheduled to take place in Russia from 14 June to 15 July 2018. The tournament organizers want to divide the…
Problem Description
The 2018 FIFA World Cup will be the 21st FIFA World Cup, a quadrennial international soccer tournament contested by the men’s national teams of the member associations of FIFA. It is scheduled to take place in Russia from 14 June to 15 July 2018.
The tournament organizers want to divide the qualifying national teams into a given number of groups for the 2018 FIFA World Cup. The teams within each group will all play each other, so your goal is to distribute the teams across the groups to balance capability and geography as much as possible. The qualifying teams for the FIFA World Cup come from six continental confederations:
To balance the groups in terms of capability, the teams were allocated to K pots based on the 2017 FIFA World Ranking1. Pot 1 contains N1 teams including Russia (which is the host for the 2018 FIFA World Cup) and the N1 − 1 highest-ranked teams in the 2017 FIFA World Ranking. Pots 2 to K contain the next Ni highest-ranked teams, i = 2, …, K.
Your task is to take the list of qualifying teams and assign them to groups based on which confederation and pot they are in. The draw must satisfy both of the following constraints:
C1. No group can have more than one team from any pot.
C2. No group can have more than one team from any continental confederation, with the exception of UEFA, which can have up to two teams in a group.
There is no limit (minimum or maximum) on the number of teams in each group.
You can use any algorithm for this homework. We have included an example of the hardest grading test case in the sample test cases. You should use the sample test
1
cases to optimize your program and make sure that it can handle all of them in less than 3 minutes.
An Illustrative Example
In order to make the problem description clearer, consider the following example with 32 national teams which are supposed to be divided into 8 groups. The classification of teams based on their continental confederations has been shown in the figure below.
Furthermore, the figure below indicates Pots 1 to 4.
The figure below shows a valid division of these teams into 8 groups.
File Formats
Input format:
<GROUP COUNT>: The number of groups for the 2018 FIFA World Cup draw.
<POT COUNT>: The number of pots for the 2018 FIFA World Cup draw.
<POTS DIVISION>: It contains <POTS COUNT> lines, where the first line is a comma-separated list of the teams belonging to Pot 1, and the following lines show the teams of Pots 2 to <POTS COUNT>, respectively.
<TEAMS CONFEDERATION>: It contains 6 lines where each line begins with the name of one of the continental confederations (AFC, CAF, CONCACAF, CONMEBOL, OFC, or UEFA) followed by a colon “:” and then the names of the teams from this continental confederation separated by commas “,”. If there is no team from a continental confederation, it is denoted by “None”.
Note: You will not be given an invalid input file. You can assume that every team that appears in the input file will be in exactly one pot and exactly one confederation. Furthermore, you will not be given any input file with <GROUP COUNT> or <POT COUNT> equal to zero.
Output format:
<YES/NO>: A single line containing “Yes” or “No” to indicate whether or not there is a solution for this instance of the 2018 FIFA World Cup draw. If there is a solution, output “Yes” in the first line; otherwise, output only a single line “No”, with nothing else in the output file.
<A SOLUTION>: If there is a solution, you need to provide just one of the possible solutions. (Note that there may be more than one possible solution, but your task is to provide only one of them). In this case, after the first line (which is “Yes”), you need to output <GROUP COUNT> number of lines, where the first line indicates the names of teams for group 1 separated by commas “,” and so on for groups 2 to <GROUP COUNT>. If there is no team in a specific group, you should output “None” for the line corresponding to that group.
Note: there should not be any empty new line after the last line in the “output.txt” file generated by your code.
Grading
Your homework submission will be tested as follows: Your program should take no command-line arguments. It should read a text file called “input.txt” in the current directory that contains a problem definition. It should write a file “output.txt” with your solution. The formats for files “input.txt” and “output.txt” are specified below. End-of-line convention is Unix (because Vocareum is a Unix system).
During grading, 50 test cases will be used. If your homework submission passes all 50 test cases, you receive 100 points. For each test case that fails, you will lose 2 points.
Note that if your code does not compile, or somehow fails to load and parse input.txt, or writes an incorrectly formatted output.txt, or no output.txt at all, or OuTpUt.TxT, you will get zero points.
Sample Test Cases
You are provided with 7 sample test cases and outputs. Please find them in the Homework 2 folder.
Homework Rules
6