UVA: 11942: Lumberjack Sequencing and 11461: Square numbers

Got both problems Accepted.

11942: Lumberjack Sequencing - tried binary search and found it to be tedious to program and difficult to get right. Switched to linear search and it simplified the number of cases to be handled.

11461: Square numbers - interesting thing here is that we need to remember the length of the beards as we proceed. I was thinking of comparing diff(i - 1, i) with diff(i, i + 1), but again, need to remember the history. So, I kept the implementation simple by remembering the last diff and the current.

Small problems can teach us quite a bit.

Thanks to Alluri for solving the problems ahead of me and recommending them to me.

CodeChef March challenge 2013 problems

Solved Approximately (APPROX) and Tourist Translations (TOTR). APPROX could have been solved a bit more mathematically and TOTR could have been more efficient.
A question that an algorist has to ask: Can I do better?

Competitive programming skillset links

This link is on the dot. Must know if you really want to make progress. I was planning to construct one, now, I can just reuse.

I landed up there from uHunt training series.

This is their programming site.

BTW, I have their book: Competitive Programming 2.

UVA 10035 - Primary Arithmetic : Accepted

UVA 10035 - Primary Arithmetic accepted :) sweet :) but, it was on the 7th attempt.

Tip: if you are printing the output, add the '\n' after every output.

I tried solving it in two ways: 

1. Taking the numbers into char arrays:

The char array solution was difficult to code because I reversed each array, started to iterate until the array with min length, then traverse until the end of the longer array to get to the final answer. I made a number of mistakes here:

* Instead of iterating over revNum1, I iterated of num1

* The minLen was using the length of the larger array (mainly due to copy paste)

* I had to construct quite a few testcases to assure myself of the correctness

2. Taking the numbers as numbers:

This was simpler to code and I knew that I had the correct answer without crossing my fingers unlike the previous option. Keeping the implementation simpler assures you of the 'Accepted' state and you know that a 'WA' in this case means that something is wrong in the output format and not your code :-)

Also I could reuse the logic from my earlier solution to 10018 - Reverse and Add.

UVA 469 Wetlands of Florida Accepted

Solved yet another UVA problem: Wetlands of Florida. Feels good. One odd thing in this problem was handling the input. In the solution, I initially went with the recursive DFS which failed on my test case containing a 99x99 'W' wetlands map. I changed to follow one of the good implementations of Chefhack by msasha. Some implementations are so very user friendly than machine friendly.

Many thanks to the codechef CHEFHACK editorial to list this problem.

Email excerpt from the online judge: "Your submission with number 11309634 for the problem 469 - Wetlands of Florida has succeeded with verdict Accepted."

UVA 352 Seasonal War : Accepted :)

This link from CodeChef is the editorial for CHEFHACK. It had the link to another similar problem in UVA which is Seasonal War. I started to solve the problem and had just one thing that sounded unclear to me: "Cells with adjacent sides on common vertices, which contain binary ones, comprise one war eagle. A very large image of one war eagle might contain all ones." Looking at the sample cases it became clear. Coded the changes, created my own test cases and seeing that all was well, I submitted the solution. This is what the judge told: "Your submission with number 11293947 for the problem 352 - The Seasonal War has succeeded with verdict Accepted."

Link with 4 interesting problems I saw while visiting uva.onlinejudge.org...

I have made uva.onlinejudge.org my homepage in Firefox and when I went there yesterday, I saw this link. I checked the link and it had 4 problems: Different (very easy), Reverse Binary (easy), Coastal length (medium) and CatVsDog (Hard). 

I was able to solve Different and Reverse binary in one attempt. Then, I started to code for Coastal length and found some interesting cases to solve. Need to find the right algorithm for this problem.

CodeChef:February2013 challenge: BUY1GET1 solved

BUY1GET1 solved. There is nothing much to say except that people have solved this problem using much lesser memory! 

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!