Are you a major programming enthusiast? The head of your college coding club? Are you looking to develop the best programming questions for your fellow members to practice on? Or are you a teacher wanting to expose your students to the art of programming? A company looking to hire programmers? Or just a major programming enthusiast and/or problem setter?
If you have answered yes to any of these questions, then this one is for you!
I will show you how to create the bestest, uniquest, awesomest programming questions out there! Never again will you have to spend sleepless nights wondering when or where your next question comes from. All you have to do is to strap on your seat belt and get ready for the ride of your life.
I promise to not make it bumpy. Alright, get ready, set go …
Screeeeeeeeeeeech! Let’s hit the brakes for a bit.
Before I take you on this wild ride, let me tell you a little bit about myself.
I’m Bharat Ramakrishna. I create problems at Skillenza. The problems I create are tested and true. And before too long, you will be making tried and tested problems as well!
Don’t believe me? Ask the audience at hacktalks. Hacktalks was a full day session in which various speakers spoke about everything hackathon-related. The topics ranged from problem creation to platform development, leveraging hackathon events, and building communities. Basically, everything centered around what we at Skillenza do!
My part, was of course, on the problem creation bit. I talked about some of the pitfalls to watch out for and some ideas to help you generate problems. I think that the audience received this quite well. They bombarded me with questions, and several even wanted to help us with our own problem creation!
Anyway, the time for the talk was short. Hardly 12 min, and so I didn’t have time to go into detail. So, I’m writing this post to bring more clarity to everything. And to elaborate.
But before I go into the details of the how … I ask you – why do you need to create original and tested problems? And why should you use these to check competency of developers? After all, hackathons seem to be an awesome way to do this. Right?
I will answer the second question first. In a nutshell, it’s because some positions need developers to be in touch with their basics. Especially those that require good algorithmic knowledge.
The answer to the first question? Part of the answer is of course, encapsulated in the answer to the second question! I guess the point is, why should the problems be original? Simple.
If you are using these for a contest, people should not be able to Google the answer! Also, if you are using these as a test on your own platform, you may run into copyright issues. Other speakers in the talk gave more details regarding the why. For more details, I will refer you to the video. (At the time of writing, the video isn’t available. But once it does become available, I will update the link.)
Alright. With the why questions out of the way, let’s move on to the how. So it’s time to strap on your seat belts again!
To understand the details, we should know how an online evaluator works. This is assuming the solutions to problems are auto-evaluated. If it’s a manual evaluation, then feel free to skip this part. 🙂
Basically, you put up your problem statement on the evaluator. Once that’s done, the evaluator expects a set of input files, and a set of output files. The input files contain all the inputs to the program. For each set of inputs, there are a set of expected outputs. These outputs are also fed into the evaluator.
Now, when the poor soul who wants to solve your problem comes along, he uploads his program on to the evaluator. The set of inputs is fed into his program, and an output file is generated. The evaluator compares these outputs to the output file, and if they match, the program passes the test cases. The evaluator also keeps track of the time taken for the program to pass the test cases. This is a measure of the efficiency of the program. (So the test case files are generally large. Up to 10 MB in some cases.)
We will talk more about how an evaluator works, and test case generation later on.
For now, let’s move on to the ideal flow of problem generation.
First, there’s a problem creator. The creator gets an idea and creates a problem. Then he passes on the problem to the problem validator. The problem validator ensures that the problem is valid (no ambiguities etc.), comes up with a solution, and generates the test cases. (Remember the input and output files I talked about?). These are passed on to the problem tester. The tester does a final check on the problem. The tester also ensures that the test cases are valid ones. Depending on the complexity of the problem, the tester may also write up another solution and ensures that the test cases are correct!
Sometimes, there are only two people involved in the problem creation process. Either way, I suggest that you must have at least two people involved. Otherwise, there will be problems with the problem!
Okay. The ideal flow is all fine and dandy, but how on earth are we to create the problem in the first place?
Where does the idea come from?
Well, that’s my next blog post.
For the purpose of this post, let’s just say, one of the best ways to come up with your own programming problem is to modify what others have done before.
But in such a way, so that the answer is not Googleable!
For example, one day, I was going through the internet as usual and came across an interesting problem. In a nutshell, the problem was several sticks on the ground of integer length. The setter had asked, ‘how many ways are there to pick up three sticks from among them to make a triangle?’
Interesting problem. And there were solutions to it found online as well. So, you can’t use the problem as is. So you have to modify it. What’s a good way?
Think about it for a second.
There are many ways! But this is what struck me. First, instead of sticks on the ground, I modified it to toothpicks. That is, there are a bunch of toothpicks on the table. And then instead of triangles, I changed it to … quadrilaterals! So, the story goes that there is a guy picking his teeth with these toothpicks. He then wonders what’s the probability of him forming a quadrilateral if he picks up four toothpicks at random.
Get the point? Several changes: toothpicks instead of sticks, table instead of ground, quadrilaterals instead of triangles, and probability instead of number.
Hard to Google the answer now, eh?
Alright, now let’s get back to the auto-evaluator and test case generation. I explained earlier how the evaluator works in terms of comparing input and output files. But how do you even come up with the input file? (Getting the output file is easy, solve the problem, run your inputs through your solution and obtain the output!)
Well, depending on your input format, there are test case generators out there that do the job for you. But if you have specialized input, then what? In this case, you might have to write up your own test case generator to do so. And I must warn you. Sometimes test case generation may be even harder than actually solving the problem!
And what’s an ideal format of a question? Instead of using a hundred million words to explain, here’s an example of a well formatted question.
As you can see, the sample input and sample output formats are explained in detail. This will help in ensuring that everything is kosher with the test cases. And in this particular problem, it’s quite easy to generate test cases. I will leave that to you as an exercise. 🙂
Interested in creating problems? Drop a line to firstname.lastname@example.org, and we will get back to you. However, if your interest lies in problem solving, then check out our webpage for the latest in programming contests and the like. We are sure you will find one that appeals to you!