CodeChef:January2013 challenge: CHEFHACK (End of the World) Accepted :)

CHEFHACK is an interesting problem that appeared in the Jan 2013 challenge. I began solving it when the contest was on, but could not submit a solution in time. After 5 submissions, I was struggling with TLE (Time Limit Exceeded)

I tried optimizing:

1. The neighbours check (added update below)

2. Primes generation (noting the primality test link which suggests that primes are of the form 6k - 1, 6k + 1)

I even looked up 2 solutions of which one was extremely difficult to understand which I skipped (one of the things I have noticed is that some of the solutions are extremely hard to understand. This is the case on TopCoder, CodeChef and even some books.) I just had a glimpse of the 2nd one which used the Sieve of Eratosthenes for primes.
3. Tried the Sieve of Eratosthenes and it is really surprising. It is blazing fast. This book says you have to know this Sieve algo!

I got 'WA' (Wrong Answer!) after having created may test cases!
CHEFHACK is categorized as an easy problem!
24-Jan: The official editorial for the problem is just great. Simple to understand and pretty neat. It talks of Sieve of Atkin instead of Eratosthenes, also of DFS to mark the cracked neighbours. This is what is causing my implementation to go wrong! Rather, I now understand that I don't understand the problem.
Thank you Codechef for this EASY problem :-)
Update: I am now stuck with SIGSEGV or runtime error.
Update 15-Feb: Got accepted. Here's my solution. Thanks to Anton Lunyov for pointing out the problem: the usage of 2 arrays inside the DFS code was causing the SIGSEGV.

btw, I have started using Git + SmartGit/Hg4 app to maintain the source code. This app looks pretty interesting.

CodeChef:January2013 challenge: CVOTE problem solved

Just solved the CodeChef January 2013 Chef Vote problem. Used C++ with map, vector, string. This was quite simple. I can reduce the # of lines though!

CodeChef:January2013 challenge: Salary problem solved

Solved the Salary problem on CodeChef January 2013 challenge. This is simply a very interesting problem. My trials with O(n^2log(n)) and O(n^2) came up with TLE (Time Limit Exceeded). The time available is just 1 second. I had to find an O(nlog(n)) or O(n) solution at least. Found an O(nlog(n)) solution. Realized that I had used one of the hints stated in multiple books: Algorithm Design Manual, Algorithms For Interviews. 

I will post the details after the challenge ends.

Update: the challenged ended 15th Jan and here's the official editorial: http://discuss.codechef.com/questions/5144/salary-editorial
My solution:
The hint that I used is to take a small example and solve it by hand. This is a pretty neat hint. Go ahead and try it.
Here't the set of comments from my code:

//Example: 33 100 1 9 40

//1 9 33 40 100       <- font="font" salaries="salaries" sorted="sorted">
//61 69 93 100 100    <- 60="60" add="add" all="all" font="font" to="to">
//68 76 100 107 100   <- 7="7" add="add" all="all" font="font" to="to">
//75 83 107 107 107   <- 7="7" add="add" all="all" font="font" to="to">
//99 107 107 131 131  <- 24="24" add="add" all="all" font="font" to="to">
//123 131 131 131 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)
//147 155 155 155 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)
//155 163 163 163 155 <- 8="8" font="font" nbsp="nbsp">(add 8 to all)
//163 171 171 163 163 <- 8="8" font="font"> (add 8 to all)
//171 179 171 171 171 <- 8="8" font="font"> (add 8 to all)
//179 179 179 179 179 <- 8="8" font="font"> (add 8 to all)
//Steps:
//1. Sort the list of salaries
//2. Add the diff of last 2 numbers 1 time
//3. Add the diff of n-1 and n-2 2 times
//4. Add the diff of n-2 and n-3 3 times
//5. Add the diff of n-3 and n-4 4 times
//6. ...
//n-1. Add the diff of n-(n-2) and n-(n-1) n-1 times

The editorial seems to have a simpler solution, but does not explain the process of arriving at the solution.