TopCoder SRM 565 Div2 500points: MonstersValley2

I thought this was a very simple problem, but not so :-)

Compressed problem statement: Given a list of monsters with their dread score (scariness score) and the price to be paid for bribing, what is the total minimum bribe to be paid. Monster 1 has to be bribed. You bribe a monster and it becomes a part of your troop. You don't need to bribe monster[i] if the total scariness of the monsters with you exceed the scariness score of monster[i], otherwise you better be wise to bribe.

I get the idea that while maximizing the dread score, we need to minimize the total price. Interesting combination. What algo fits here? Found it - Dynamic programming. Now, it is time to understand, write code and get practice points :-)

TopCoder:SRM233:SmartWordToy

This entry is about SmartWordToy problem from the Single Round Match 233 of TopCoder Division 1 and it is a 500 point problem:

Have you visited the TopCoder Algorithm tutorials page? You must have seen the mention of BFS (Breadth First Search) there and probably started to try the first problem listed there: SmartWordToy. I started too.

It seemed an interesting problem: there are 4 letter blocks; each block contains 2 buttons; left makes the letter go the previous letter in the sequence; right button takes the letter one step forward; given a start, end and a set of disallowed combinations, what is the minimum number of button presses required to reach the end?

The sequence of letters are cyclic which means that if you are seeing 'a' and press the left button, you will see 'z'. Also, if you are at 'z' and press the right button, you will see 'a'. Every time a button is pressed, the total score adds up until the end is reached.

The first test case in the problem being:
start = "aaaa"
end = "zzzz"
forbidden = { "aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza"}

v0.1:
I created a graph that would generate 8 new strings (or state) from a given string (state). For instance:
aaaa = zaaa baaa azaa abaa aaza aaba aaaz aaab
This is the set that results from pressing 1 button (left or right) on each block.
The graph generation took about 9 seconds to finish and if i had submitted this version, it would say 'Time Limit Exceeded'. We will come to this problem later.

After this, I added the start state to the queue and started the BFS. Pick the first state from the queue, check if it the goal state, if not, add it to the visited states, get the 8 possible states from this state, add it to the queue. If it is the goal state, end.

Problems with this approach:
1. Graph has been generated taking really long time.
2. How do we count the button presses?
3. On looking at the program trace, you see that the path taken does not go towards the goal. Even if the goal state was reached, it is certainly not the optimal path. This raises the question: how do we really use BFS?

v1.0
1. Addressed the early graph creation by adding the start state to the queue. Picking the item off the queue, checking if it is present in the graph, if not, add it to the graph along with the set of states that it generates.
2. Added a cost to each state by computing the distance from a given state to the goal state. This was interesting because there are 2 possible costs: forward cost (distance from a to z is 25) and reverse cost (distance from a to z is 1)
3. Now, I used Dijkstra's min path algorithm to pick the state with the least cost and then go towards the goal.

This solution passed all the sample test cases for the problem and some of my own. With confidence, I submitted the solution and got 469 out of 500. I then ran the system tests and saw that one test case fails:
String start = "aaaa";
String finish = "xxxx";
String[] forbidden = { "xz xz xz z", "xa xa xa b" };
Expected = 12, my output is 14. Need to find the root cause and fix it.

Learnings:
1. Just in time execution
2. Go towards the goal :-)

Topcoder SRM 562 Div2 250 point problem: Cucumber Market

Problem in short: Kid goes to cucumber market with a budget and chooses k items out of available n items.  He can choose any of all possible k combinations and the return is 'YES' if he can successfully buy any such combination, otherwise 'NO'. The inputs being the array of prices and the number k.

My approach: Initially, I sorted the price array and got totals of k items (0..k, 1..k+1, 2..k+2, so on until n) and found test cases to pass except the 2nd one. I seemed to have gotten lost when I needed to sum up items 0, 2, 3,.. which is basically taking any of the k elements from the n elements.

Now, the problem seemed to need all possible k combination from n items. I thought of looking up how to get all the k combinations and then coding phase time ran out. 

Challenge phase: In this phase, I looked up one solution which had picked up the worst possible set of k items and if that did not satisfy the criterion, it returned 'NO'. This felt rather intimidating. How could I possibly miss this?

Anyway, one thing I need to learn is to figure out how to find all k items from n items.

Found an interesting link in StackOverflow:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n