Tuesday, January 22, 2013

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)
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.

No comments:

Post a Comment