Kattis Challenge: Disastrous Downtime
SPOILER ALERT: This post contains an answer for an online programming challenge (https://open.kattis.com/problems/downtime). Try it yourself first :)
Programming challenges are one of those things that seem incredibly boring until you get sucked into doing one. I came across this site called Kattis (https://open.kattis.com/), where you submit source code to solve programming challenges online. Your program is compiled, tested against secret input, and then it tells you it’s wrong and then you swear a lot. I think that’s how it’s supposed to work.
I like the ‘medium’ difficulty ones because I can usually come up with something before I start losing sleep. Today we’ll try Disastrous Downtime : https://open.kattis.com/problems/downtime
We’re asked to write what is basically a simple calculator for parallel computing tasks: Tasks come in at a given time point, must be executed immediately, and run for exactly one second. The main challenge here is to find out the most tasks that can be running at any given time.
One could imagine each task as a bar in a graph, where our goal is to see where the bars overlap the most. Unfortunately, what’s easy with our eyes isn’t as easy with a computer. How can an algorithm figure this out?
Well, we can assume that nothing interesting happens unless a task is being started, so we can perform any calculations only when a new task enters the system. My first thought was to create a Request object which holds the start time and the end time (advanced calculus: start time + 1000), as well as an IsRunning() method that takes a time point and tells us if the task is active.
class Request
{
public int tStart;
public int tEnd;
public Request(int tStart)
{
this.tStart = tStart;
this.tEnd = tStart + 1000;
}
bool IsRunning(int currentTime) {
return currentTime >= tStart && currentTime < tEnd;
}
}
Cool, so read all the input, create a List of requests, and then count how many are active at every time point where a new task enters the system, I excitedly wrote a hella elegant LINQ query to do this and…success! Both example cases return the expected value.
Now to proudly submit it and wait for the internet robot cat to tell me I’m the best computer guy ever…
Kattis: Time Limit Exceeded
WHAT?! My glorious LINQ has failed me?! Impossible! Well, actually, it’s pretty clear why: This algorithm has to compare every input to every other input, and there can be up to 100 000 of them! I wrote a simple Python script to generate an input with 100 000 tasks running all in one second, and it ain’t pretty: The program barely gets past the first 100 jobs after running for 30 seconds.
Welp, as the saying goes: First make it work, then make it efficient. A clue here is that we can clearly eliminate some tasks from the comparison. I don’t care about the event at t=0 when we’re at t=1000. I thought about rewriting this code in C++ where I could do a nifty table lookup with std::lower_bound and std::upper_bound, or implementing something similar in C#, but then I realized this would still have some performance limitations: Binary (or red-black tree) search is faster, but not instant. There must be something even better, where we can only compare what needs to be compared and ignore everything else…
Then I realized that maybe I was looking at this all wrong: Instead of loading all the input and analyzing it, why not emulate a system actually processing incoming data? The fact that incoming requests are chronologically sorted is important here: We could use a queue that holds active requests, checking for finished requests and purging them when new ones arrive. The major advantage here is that we only have to compare each request with only one other request (the oldest one currently in the queue):
List<Request> requestList = new List<Request>();
int maxSimultaneousRequests = 0;
for (int i = 0; i < nRequests; i++)
{
int requestTime = int.Parse(Console.ReadLine());
requestList.Add(new Request(requestTime));
while(true)
{
if(requestList.First().tEnd <= requestTime)
{
requestList.Remove(requestList.First());
} else
{
break;
}
}
maxSimultaneousRequests = Math.Max(maxSimultaneousRequests, requestList.Count);
}
Alright, so the while(true) bit would generate a lot of colourful comments on a code review, but that’s the basic idea. We just need to maintain a value that represents the maximum size of the queue at any time, easy.
Aaaaaand let’s not forget we want to find out how many servers we need, so we have to divide by the number of simultaneous tasks supported by a single server:
int nServers = (int) Math.Ceiling(maxSimultaneousRequests / (double)serverParallelism);
With newfound confidence I submitted my code to the glorious cat god:
Kattis: Accepted
Yippee! My code ran in 0.25 seconds, the fastest code ran in 0.05s. The use of objects to deal with this is likely overkill, and purging elements one at a time in a loop is not the most efficient. But hey, close enough, right?
It’s almost painful seeing how few lines of code I needed to solve this problem considering how much time I spent thinking about it =/