Algorithms – Developing a Number Game Algorithm

algorithms

Problem Link – http://www.iarcs.org.in/inoi/2011/zco2011/zco2011-1b.php

The task is to find the maximum score you can get in the game. Such problems, based on games, where you have to simulate, predict the result, or obtain the maximum possible score always seem to puzzle me.

I can do it with recursion by considering two cases – first number picked or last number picked, each of which again branches into two states similarly, and so on… which finally can yield the max possible result.

But it's a very time-inefficient approach, since time increases exponentially, due to the large test cases.

What is the most pragmatic approach to the problem, and to such problems in general?

Best Answer

The trick is thus:
Consider 2,5,3,3,2,1.

Your move: Pick Left
Opponent move: Pick Right
Current state: 5,3,3,2.

vs.

Your move: Pick Right
Opponent move: Pick Left
Current state: 5,3,3,2.

Using recursion, you will end up calculating how many more points you can get for 5,3,3,2 twice!

So, the solution is to use memoization (dynamic programming)

The first time you call your function on 5,3,3,2, store the score for that (e.g., in a two dimensional array where the first index is how many numbers have been removed from the left and the second index is how many numbers have been removed from the right). The next time you are about to call it, just load the score from the previous time.

A nice benefit of this strategy is that you can use your existing recursive algorithm with only minimal modification.

Related Solutions

How is the “Pizza picking problem‍” solved using dynamic programming techniques

Start by considering the slices just placed on a row and you can pick from one of the two ends. In this case supposing it's your turn to chose it's clear that pizzaAmount(slices) is

If there's no pizza left result is 0
If there's only one slice result is that slice
If there are at least two slices then the result is:

(using Python syntax)

max(slices[0] + sum(slices[1:]) - pizzaAmount(slices[1:]),
    slices[-1] + sum(slices[:-1]) - pizzaAmount(slices[:-1]))

in other words you should consider both alternatives and that after taking your slice you will get all the remaining pizza except the result of the recursive call (because your friend will use the same strategy).

You can implement this with DP (or memoizing) because the array is indeed fixed and you can just consider as parameters the first and last slice index.

To solve the original full problem you just need to try all slices as starting slice and chose the one that maximizes the result.

Algorithms – Solving the Equal Gifts Algorithm Problem

Just winging this off the top of my head before morning status meeting:

Sort books descending by value
Give first book to Lavanya
while books remain
    while Nikhil's values < Lavanya's values
        Give first book to Nikhil
    while Lavanya's values < Nikhil's values
        Give first book to Lavanya

Will that do it?

Best Answer

Related Solutions

How is the “Pizza picking problem‍​” solved using dynamic programming techniques

Algorithms – Solving the Equal Gifts Algorithm Problem

Related Topic

How is the “Pizza picking problem‍” solved using dynamic programming techniques