Only Python coding is required

Problem Statement: On the playdate for all middle school students, their teacher has decided to take them to Zenith an arcade game arena near the school. The arena has exactly one unit of each type of arcade game like pinball, car racing, shooting etc. and all these games are single-player games, that mean only one player can play the game at a time. In order to keep the students happy and avoid any conflict or fights, the teacher shared a list of arcade games with the students and asked them to pick their favorites. After receiving the forms from each student, the teacher now wants to know how many combinations can she come up with such that: 1. Every student is playing a game of their liking 2. No student is left without a game of their choice 3. No two students are found fighting for the same game. Assuming that all games take the exact amount of time to complete before students have to switch to another game, if there are 10 games and 10 students, find out the number of combinations the teacher has to shuffle students between each of the games.

Games: G1, G2, G3, G4, G5, G6, G7, G8, G9, G10

Students: S1, S2, S3, S4, S5, S6, S7, S8, S9, S10

Requirements:

1. Formulate an efficient algorithm using Dynamic Programming to perform the above task.

2. Analyse the time complexity of your algorithm.

3. Implement the above problem statement using Python 3.7

Sample Input: Input should be taken in through a file called inputPS15.txt which has the fixed format mentioned below using the / as a field separator:

Student i / < Game 1> / / .

Ex: S1 / G1 / G3 / G4 / G6

S2 / G2 / G5 / G1 / G4

S3 / G2 / G1 / G3 / G10 / G9 / G6

S4 / G2 / G5

S5 / G2 / G1 / G3 / G4 / G7 / G8

S6 / G2 / G5 / G3 / G4 / G7 / G6

S7 / G7 / G8 / G10 / G9 / G6

S8 / G3 / G4 / G7 / G8 / G10

S9 / G2 / G5 / G1 / G6

S10 / G2 / G5 / G1

Note that the input/output data shown here is only for understanding and testing, the actual file used for evaluation will be different.

Sample Output: The total number of combinations possible is: 220

Note that the input/output data shown here is only for understanding and testing, the actual file used for evaluation will be different. Display the output in outputPS15.txt. 2. Deliverables 1. Word document designPS15_.docx detailing your design and time complexity of the algorithm. 2. [Group id]_Contribution.xlsx mentioning the contribution of each student in terms of the percentage of work done. Download the Contribution.xlsx template from the link shared in the Assignment Announcement. 3. inputPS15.txt file used for testing 4. outputPS15.txt file generated while testing 5. .py file containing the python code. Create a single *.py file for code. Do not fragment your code into multiple files The Code must be in Python 3.7 followed by Dynamic Programming