This is my submission for the JetBrains AI-Powered Code Assistance with GPT-3 and Codex Summer Internship test task. Students were asked to propose an algorithm to solve a problem and implement it in any language. I chose Python3.
Given N hours to prepare for an exam, how can a programmer optimize their time given M topics to cover. A topic i requires Ti time to study, and has a certain number of questions Ki that could appear on the exam. The exam comprises of L questions chosen randomly with an equal probability. What is the best way to use the limited time to maximize the chances of getting the best possible grade?
To maximize their chances of getting the best possible grade, the programmer should dedicate the most hours to the topics that have a higher probability of appearing on the exam and take the least amount of time to study. Let Ji be defined as the number of hours it take to study a question in i, we have Ji = Ti/ki. We then greedily study these topics until the sum of their time = N.
My program takes as input a .txt file with the following structure. The input starts with one line containing three positive integers, N, M & L separated by a space. Then follow M lines containing two integers Ki & Ti.
(This input format is similar to the one found on the Kattis platform).
- N >= 0
- M >= 0
- Ti > 0
- Ki >= 0
The output is printed to the console and contains values H1, ..., HM separated by a space, indicating how much time must be dedicated to studying topic i.
The algorithm runs in approximately O(n + nlogn) where n is the number of topics. Sorting the topics is the operation that takes the longest at O(nlogn).
The program can be run from the command line with
python3 script.py < '<path/to/input/file>'For convenience, I have provided some sample input files in the SampleInputs directory.
In the Tests directory, run the following command:
python3 -m unittest discover