What should be the approach for challenge problems?

general
1

How do you, in general, solve a challenge problem? Are there some standard tricks/algorithms that you use?

Please elaborate.

2 Likes
2

Yup,Firstly read the data structure and then algorithm.
Book for data structure and algorithm - “Introduction to Algorithms” by Cormen et. al
and you also watch video -

 https://www.youtube.com/watch?v=q11MdcomARw

.

3

EDIT: I have made a video on solving challenge problems. Hope it helps. :slight_smile:

Solving the NP Problem

I am no expert. But my approach to a challenge problem is:

  1. First think of a brute force solution.

  2. Then I think of a fitness function. For any given situation, the current fitness can be calculated using that.

  3. Now think of how to maximize the fitness based on the question parameters.

  4. If you see a clear path, go for it. Else, make the computer search that vast search space using any evolutionary algorithm. I think simulated annealing, genetic algorithms, swarm intelligence, etc… fall into this category.

  5. For small inputs, brute force solutions. For larger ones, use the above techniques.

  6. Submit many solutions. Tweak the parameters and check what works best.

I used to do horribly at challenge problems. But last time GERALD09 went decently and this time my genetic algorithm did quite well. :slight_smile:

6 Likes
4

Are you sure you read the question? :stuck_out_tongue:

1 Like
5

@rajat_dtc come on dude you are suggesting him to watch this video and read a basic book first at least have a look at this http://www.codechef.com/users/balajiganapath

1 Like
6

sorry , i forgot to check your profile and Sorry for my post. I think , you need basic algorithm. So, i post this… sorry again.

1 Like
7

Thanks! This was really helpful :). I will learn those evolutionary algos.

1 Like
8

There are countless approaches that fit on different challenge problems. If the data are big, one common factor is that they all have to be greedy in some way. Here are some examples:

  • simple, straightforward greedy: here, “choose an order, then always pack the next piece to the first possible place” gave decent points AFAIK

  • many different approaches: here, I submitted multiple simple solutions that didn’t give many points before finding one that gave a lot

  • cost function: for example when determining the next turn in a game with complex states, but few options for that next turn, you can compute a simple function based on many parameters for each move and choose the optimal one

  • simplify: in this month’s challenge problem, I discarded the weights and delivered one item at a time for the most part of the problem

  • simplify a lot, then add more complex ideas: in that same problem, I started with “when you choose a delivery, move S -> its starting vertex -> its ending vertex -> S”, which reduced the problem to distances on a tree rooted at S + a knapsack with random weights/costs, so I just sorted by the ratio weight/cost and chose deliveries in that order; then, I added stuff like computing LCAs and sometimes updating S to the current delivery’s ending vertex and recomputing the tree rooted at S

Since data are usually generated randomly, it’s often good to make use of randomisation in your algorithm as well. Another generally good thing is adding a lot of parameters into your code and then tweaking them to the optimal values (not only in challenge problems…).

3 Likes