Prezi is available on multiple platforms, so we have to convert some of the uploaded media files to other formats before we can display them on all devices. This conversion happens on virtual machines. The load (and thus the number of virtual machines needed) is very different during peak times and at night.

Your task is to create a program which receives conversion requests and issues commands to turn virtual machines on or off. Prezi pays for these virtual machine instances by the hour, so it’s best to terminate them near the end of the billing hour. The goal is to have conversion jobs spend no more than five seconds in the queue while minimizing the overall cost incurred. A new conversion job may be sent to one of three queues:

• export - Contains jobs which result in downloadable zipped prezis.
• url - These jobs download an image from a URL and insert them into a prezi.
• default - All other conversion jobs (audio, video, pdf, ppt, etc).

Your program should ensure that none of the conversion jobs wait in the queue for too long. If a job waits for more than 5 seconds, you will receive a penalty.

penalty is given by

3 * ( overrun - 5 )/120 

where overrun is the seconds a job is waiting in queue. The penalty is in hours.

If it waits for more than two minutes, your submission will be disqualified for the current data set.

Virtual machines take 2 minutes to boot, they will start processing thereafter.

A penalty of 1 hours is subtracted from final score to accommodate the 2 minute delay in starting the first vm. This can be taken care of by launching a VM immediately.

Input Format

The first line of the input is the name of the dataset file. The file will be present in the current directory.

DateSet Format

The first line contains an integer N, N conversion job requests follow each in a new line.
Each conversion job request will have 4 fields separated by a single space.

1378072800 2.133 9ea24acd-cee3-4248-bf43-fb33e7e9ac4b url

The fields are

1. The unix timestamp when the job was created (1378072800).
2. The duration of the job in seconds (2.133).
3. The unique identifier of the job (9ea24acd-cee3-4248-bf43-fb33e7e9ac4b).
4. The queue which received the job (url).

Constraints

1 <= N <= 10⁶
Duration of the job < 3000 sec.
Unique identifier is a alpha-numeric-hyphenated string of 36 characters.
queue can be any of {url, export , default}

Output Format

For every job that you receive, you can launch, terminate any of the different type of VMs with the following string printed to the output,

1378072800 launch url

to launch a VM that processes url jobs at timestamp 1378072800.
you can also terminate any existing VMs if any,

1378072800 terminate default

to put a job to a queue, you can use print the job to the output

1378072800 2.133 9ea24acd-cee3-4248-bf43-fb33e7e9ac4b url

this puts the job with the id 9ea24acd-cee3-4248-bf43-fb33e7e9ac4b to url VM instance at timestamp 1378072800.

The instance put into the queue can be assumed to enter the optimal VM for processing.

Data set 1
The input logs are publicly available here. There are also graphs for the number of concurrent jobs for the three queues: export, url, default.

Data set 2
The input logs are publicly available here. There are also graphs for the number of concurrent jobs for the three queues: export, url, default.

Data sets 3 and 4
These data sets are secret. They carry a much higher weight in your final score.

You are not allowed to buffer input and react to it later, that is, you can only base your terminate and launch commands on previously read input lines (and the current line).

Scoring

Your score is based on the number of virtual machine hours you used (plus any penalties incurred due to delayed conversion jobs). Conversion jobs for each queue will be automatically picked up by the optimal VM for that queue (if possible, the instance which is closest to the end of the billing period which can still finish). You do not need to worry about job-VM pairing. When your program issues a terminate command, the instance belonging to the given queue closest to the end of the billing period will be shut down.

You can view the source of the checker on github.

The evaluator is not fool proof, cheating submissions or submissions that buffer jobs are treated as invalid submissions.

The prize
The first place contestant will receive $1500 from Prezi.

TimeLimits

The timelimits for the challenge is given here

Getting started
To see an example solution to this problem, change the language the to Python 2:

Of course, you can use any of the available languages to create your submission. You are allowed to submit only 2 submissions/hour. Each submission takes anywhere between 20-40 minutes to process.