Blog

Challenge Problems

In this blogpost, we talk about what Challenge problems are and how to solve them. I find them the most attractive questions in a long contest. However, students new to competitive programming often avoid them because they seem weird at first. Lets try and change that.

What are Challenge problems?

A challenge problem in a programming contest uses NP problems to test a candidate. With no perfect answer, the candidate is tested on how good he/she is at finding approximate solutions. This is why the evaluation is score based.

The top scorer is given a score of 100 while the others are given scores as per their closeness to the top score. Usually, problem statements are simple and allow candidates to find interesting nuances while solving. Because of the generality of the problem, a candidate can choose numerous approaches to optimise his/her score. These include Number Theory, Graphs, Data Science, etc…

Some problems require prior knowledge of algorithms, but the best challenge problems are those which have simple explanations and lots of scope for improvement. Such problems allow beginners to try and test their approximate solutions while making sure that the experienced players are tested too.

How do we solve this

MIT professor Patrick Winston makes a brilliant note on problem solving at 42:30 in this video. Here is a summary:

  1. Definition
    Does the problem reduce to Knapsack? Subset sum? Something else?
  2. Representation
    Should the main data structure be an array, a list or a tree?
  3. Approach
    Dynamic Programming? Graph Algorithm? etc…
  4. Algorithm
    DFS / Sorting / Edit Distance –> Simulated Annealing / Genetic Algorithm
  5. Experiment

A key point is that drawing and discussing ideas are far more important than jumping into code. The other super important thing is you can’t follow this process in just one shot. It has to be repeated again and again, with each iteration improving your solution.

First, you need a base solution. Choose a simple, clear cut algorithm(like the first three mentioned below point 4). This is the foundation, setting a minimum guarantee to your score. Invest your time in this, because a weak base solution will directly result in a poor score.

You now need to tweak the best solution you have, updating if you get something better than the current best. Hill climbing, Simulated Annealing or any Evolutionary Algorithm will help you here. Most of the time after this will be spent improving the parameters of the algorithm and improving the time complexity.

Time required to solve them

optimise-challenge-problem

They can’t be solved in half a day, to be practical. Unless you are looking for an okay score and minimum effort, be prepared to invest significantly.

Also beware of the law of diminishing returns. In general, the more time you invest in these problems, the smaller improvements you will see. The first few hours will give you interesting solutions => perhaps a score of 75 – 85, the next few days might take you to 95-100. And staying there takes tons of effort.

The primary reason why these problems are difficult is because we have to customise and optimise our solutions every time. You can create a general framework for Simulated Annealing to help in the coding phase. However, the ‘representation’ part will change every time.

Upto what point do I keep optimising

Until you feel that there is very little progress being made. To be practical, the other problems will give you many more points for the same amount of effort. When you hit problems beyond your league, come back to improving on the challenge problem solution. Remember that the people at the top have access to the same resources as you do. There is no reason why they should get a better score than you.

When should I start with this problem

This problem will stay at the back of your mind throughout the contest. So it is better to start a little late. More often than not, the problems within our league are solved within the first 80% time of the contest. The challenge problem can be started then.

Final tips and tricks:

batman-robin-challenge-problem

  1. Do not jump into meta-heuristics (Genetic Algorithms, Simulated Annealing) without creating a strong base solution.
  2. When optimising, try to keep the code clean for later.
  3. Your nested loops need the most attention, because that where you get maximum gains.
  4. Greedy is good. Keep your heuristics simple and easy to change.
  5. If some idea feels too complicated, it is. Save it for the next contest, after reading a little more and being confident about it.

I speak about other topics from competitive programming on my Youtube Channel. You can check them out here.

College Life

To avoid offending too many people, let me start off with a clarification. Whatever generalisations I make are exactly that: generalisations. They apply on the collective, and not to anyone specifically.

As a child, I never studied. It was such a hateful task. Memorizing pages and pages of weird stuff. My teachers would instil hope in my parents by calling me ‘smart’. Then they would turn them against me by labelling me ‘lazy’. 

Each class would have a group of ‘exceptional’ students, whose scores would be displayed on the black board during a parents-teachers meeting. Conveniently put up for comparison.

So after the end of an exam, I would find myself sheepishly looking at the floor while my parents wondered how on Earth would their son ‘Stand on his feet’. I was hoping that this would pass in time, like plagues usually do. If anything, the feeling intensified. Rote learners pretended they weren’t while parents and teachers discussed the ‘brilliance’ of 13 year olds for hours together.

We now come to the main topic. The above anecdote is important. It explains the kind of system we have grown up in, and the kind of expectations our teachers have from us until we step into college.

Ah. College.

Here, a small group of students scored the most in nearly every subject. And not just in theory: their assignment and practical scores were rather astounding. The most devoted and zealous students were those who had joined us in our second year directly, after completing their diploma.

I was surprised. On average, a diploma student:

  1. Scored higher in their tests
  2. Completed assignments faster with high emphasis on neatness and volume
  3. Submitted documentation of their practicals earlier

However, on average, a diploma student…

  1. Had far poorer communication skills
  2. Was better at coding. Yet, he/she coded better and programmed worse: memorizing the ‘how’ without understanding the ‘why’
  3. Focused on lame topics

Concepts such as data structures and soft computing got little priority. When asked how our lectures could be improved, a friend of mine said she wanted to learn ‘current’ stuff.

“These technologies are all obsolete.” She sighed. “They can’t possibly teach us what is current in the Industry.

There we have it. ‘Industry’ was a key element in a student’s education. It defined how and what we should study. The industry did everything perfectly, and had no issues it couldn’t solve. This speaks for our research capabilities. We suck at it so much, the industry teaches us what to do instead of the other way round.

It also gives rise to skewed thinking. Instead of focusing on what we can learn from Galileo’s telescope, we spend our time comparing it with Hubble’s.

Anyway, we come to the fourth year of graduation. My college decided that it would conduct aptitude tests to prepare us for placements. Our then Training and Placement Officer stormed into class.

“Students need to improve on logical reasoning and quantitative analysis.” the TPO droned. “Clearing these tests are mandatory for anyone applying for campus placements.”

A volcano erupted. We didn’t know what to expect. This was something that was potentially going to stop someone from getting a hard-earned job on campus. Strong opinions were on both sides. Personally, I thought it was a good idea.

However, the students in my class, especially those from diploma, were keen on clearing these tests the usual way. This meant that there would be a set of questions, called a question bank, given to the entire class. This question bank would then be ‘sampled’ from to generate the test. To be precise, this was the only way we knew to clear tests.

Giving rise to the time I was most disappointed by my college TPO: He agreed to give away the aptitude test question bank.

I couldn’t believe when he did. An aptitude test, based on the memorization of questions? And their answers. It seemed like a farce, and after bitching about it for some time, I jumped at the solutions and memorized the entire set.

What followed was a silent disaster. Nearly all of us studied for the test. Nearly all of us passed. But none of us was tested. A complete anti-climax, with answers we remembered better than the questions.

After that, placement season started. Most of the mock test’s top scorers failed their applied company’s quiz. Elsewhere, there was an even bigger surprise. Despite having an image of being good coders, no one from the diploma group cleared their coding tests.

The atmosphere didn’t get better after this either. Interviews were scheduled to start. And here students started studying their pyjamas off. About things like merge sort. Maybe they thought this was like another exam, where you can cram in as much as possible to puke it out immediately after. Maybe they thought practicals still meant completing write ups and copying printouts.

They couldn’t be more wrong. You can’t learn algorithms a few hours before the interview.

For those of you with the question “Are algorithms really necessary?”, let me strongly emphasise here: The people who innovate using software are those with algorithmic skills. The others are usually arguing about why something is impossible. Or why something is so good. They can barely innovate, and are essentially maintainers. Creators are found among those who speak the language of logic.

A short story explains our plight. TCS had been kind enough to ‘train’ us for placements before they started. After some mumbling about how great the company was, we were treated to a ridiculous series of lectures. On life and Hadoop. Capping it off, they asked us to join their own social network called Campus Commune.

There has never been a more cringe-worthy request from a company.

“Your campus commune scores will be used in placements.” A moron named Robin warned. “Oh, and I would prefer candidates who can get a few hundred likes for their Facebook posts.”

Hilariously, students started asking random and non-sensical questions on the networking site. To salvage a placement. It was both saddening and pitiable. I wonder if Robin went to a bar later to laugh his head off. I certainly hope he wasn’t as stupid as he looked.

In any case, there you have it folks. A nice soup:

  1. Students desperate to get placed
  2. TCS

At the end of my graduation, I looked around at the class one final time. At most 10% of them deserved to be called Engineers. The rest would either pursue other goals or become TCSians. From the corner of my eye, I noticed my parents looking at me proudly. It was my turn to collect my degree. What an achievement.

To conclude, I point the finger of blame at our education system and hype-intoxicated parents. In their exaggerated concern to see children do well, they teach one to sacrifice learning for scoring. I hope our outlook changes by the next generation.