CareerCup

Some of the previous solutions are wrong as discussed in the comments. Since the order matters, I'm not seeing a very efficient (polynomial) solution.

However, we can still use dynamic programming. We can pick bombs step by step, marking the bombs that we already used. Before we pick a bomb, we need to check if any of the previous chosen bombs affects it. We can use bitmasks with bit i set to 1 if we already picked bomb i, 0 otherwise.
This leads to 2^N possible states.

int N, v[22], r[22], dp[ 1 << 22 ];  // init dp to -1 == not done

bool Contains(int mask, int i) { return mask & (1 << i); }

bool Conflicts(int i, int j) { // j affects i
	return (abs(i-j) <= r[j] || abs(i+N-j) <= r[j] || abs(j+N-i) <= r[j]);
}
int Go(int used_mask) {
    if (dp[used_mask] != -1) // already done before?
        return dp[used_mask];
    dp[used_mask] = 0;
    for (int i = 0; i < N; i++)
        if ( ! Contains(used_mask, i) ) {
            bool ok = true;
            for (int j = 0 ; j < N ; j++)
                if (Contains(used_mask, j) && Conflicts(i,j)) {
                    ok = false;
                    break;
               } 
           if (ok)
               dp[used_mask] = max( dp[used_mask], v[i] + Go(used_mask | (1<<i)));
       }
    return dp[used_mask];
}

int main() {
	int i;
	scanf("%d", &N);
	for (i = 0 ; i < N ; i++)
		scanf("%d %d", &r[i], &v[i]);
	memset(dp, -1, sizeof dp);
	printf("%d\n", Go(0));
	return 0;
}

This takes O(2^N * N^2) time and O(2^N) memory. It's ok for N up to 20~22.
To make it O(2^N * N) we can just use hashing instead of the nested loops. But it does not make a big difference here.

Let dp[i][j] be the max value from ith and jth bomb on the circle, forcing i no greater than j.
Actually by denoting any kth (i <= k and k <= j) bomb, we got a precisely sub problem with smaller size, such that:
dp[i][j] = Max{ dp[i][bkd] + v[i] + dp[fwd][j] } , where bkd and fwd is by denoting kth bomb, the backward and foward range that not get effected.

Note this is a circle, sequence does matter, so dp[i][j] assumes from i to j, there are bombs, but from j to i, no bombs.

public class BombGame {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BombGame bg = new BombGame();
		System.out.println(bg.maxValue(new int[] {1, 3, 2}, new int[] {1, 1, 0}));
	}

	private int[] v;
	private int[] r;
	private int length;
	private int[][] dp;

	public int maxValue(int[] v, int[] r) {
		this.v = v;
		this.r = r;
		this.length = v.length;
		this.dp = new int[length][length];
		for(int i = 0; i < length; i++) {
			dp[i][i] = v[i];
		}
		return maxValueInternal(0, length - 1);
	}

	private int maxValueInternal(int start, int end) {
		if(start > end) return 0;
		if (start == end || dp[start][end] != 0)
			return dp[start][end];
		
		for (int i = start; i <= end; i++) {
			// denote i
			int fwd = i + r[i] + 1;
			int bkd = i - r[i] - 1;
			//this is a little tricky, as we have to consider 
			//when the range is very big, it destroy the end
			//bomb, thus changing the end range
			int end_ = (bkd + length) % length;
			end_ = end_ < end ? end_ : end;
			
			dp[start][end] = Math.max(dp[start][end], 
					maxValueInternal(start, bkd) + v[i] + maxValueInternal(fwd, end_));
		}
		return dp[start][end];
	}

}

d[i]= the best value you can get at the ith bomb.
d[i]=max(when the ith bomb is included, when the ith bomb is excluded)
so, d[i]=max(d[j]+v[i], such that j<i is not within the range of i or max(d[j] such that j<i))

Bomb N-1 is neighbor to bomb 0?

Got me puzzled for a few minutes after which I realized this:-
Ever seen the MineSweeper Game on Windows OS. This is a popular game in which you find values and make sure that you bypass mines( or bombs :) ) .

Your problem is to find a WIN ( the best WIN actually) in MineSweeper. Ify ou can GOOGLE a little, you should get your answers.

First, if Bomb[i] is in effective range of Bomb[j], add a directed edge from j to i. Then we can compute strongly connected components. If we looks these strong connected component as a single node, then the original graph will transform to a DAG. In each node (strongly connected component) we can only get value from one bomb. We can get values from all node (strongly connected component) by detonating bomb start from the node with zero out degree.
This is not a DP, and I am not sure if this is correct.

will greedy algorithm work? Every time detonate the bomb that has least loss (Loss is the sum of the values of all the affected bombs). This is doable in n^3

Let bCnt be number of remaining bombs to be detonated
Let detList be an efficient datastructure that can store the detonated bombs
i-> ith bomb to be exploded

det(i,bCnt,v,r,detList) {
if(bCnt<=0)
return 0;
else{
if i is in detList
return det(i+1,bCnt,v,r,detList);
else{
int detValue1 = det(i+1,bCnt,v,r,detList);
add i to detList along with all neigbours in range of i's detonation
int detValue2 = det(i+1,bCnt-1-2*(r[i]),v,r,detList) + v[i];
remove i and all its neigbours from detList;
return max(detValue1,detValue2);
}
}

in C++, dynamic programming

int Calc(int **V, int v[], int r[], int i, int j, int n)
{
	if(V[i][j]!=0)
		return V[i][j];
	if(i > j)
		return 0;
	else
	{
		V[i][j]=max(Calc(V,v,r,i,j-1,n),Calc(V,v,r,max(i,j+r[j]-n+1), j-r[j]-1, n) + v[j]);
		return V[i][j];
	}
}

int bomb(int v[], int r[], int n)
{
	int** V = new int*[n]; //V[i][j] means the max sum of value from i to j;
	for(int i = 0; i < n; i++)
	{
		V[i] = new int[n];
		memset(V[i], 0, sizeof(int)*n);
		V[i][i] = v[i];
	}
	return Calc(V,v,r,0,n,n);
}

Can it be done this way. We first sort all bombs based on x co-ordinate, is x is same, sort on effect range. Our final solution is going to have some sequence of bombs exploding, let's say a1,a2...ak. We say that dp[i] is the solution when i is the last bomb in the sequence definitely detonated. We just calculate all other bombs from 1 to i-1 which can be detonated before i so that i can be detonated. Calculate the value obtained. That is dp[i]. Ans is max (dp[i] | 1 <=i <= n)

Same idea, as described before, implementation using bool vector for used marker, probably slower than bitsets, but code is cleaner

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;

struct Bomb {
  size_t range;
  size_t value;

  Bomb(size_t new_range = 0, size_t new_value = 0): range(new_range), value(new_value)
  {}
};

size_t getMaxBombValueRecursive(const vector<Bomb>& data, vector<bool>& used, unordered_map<vector<bool> , size_t>& cache);

size_t getMaxBombValue(const vector<Bomb>& data) {
  if(data.empty()) {
    return 0;
  }

  vector<bool> used = vector<bool>(data.size(), false);
  unordered_map<vector<bool> , size_t> cache;
  return getMaxBombValueRecursive(data, used, cache);
}

int getIndex(const vector<Bomb>& data, int initial_index) {
  if (initial_index < 0) {
    return getIndex(data, data.size() + initial_index);
  }

  if (initial_index >= data.size()) {
    return getIndex(data, initial_index - data.size()) ;
  }

  return initial_index;
}

void toggleBomb(const vector<Bomb>& data, vector<bool>& used, int bomb_index) {
//  used[bomb_index] = true;
  for (int i = 0; i <= data[bomb_index].range; i++) {
    used[getIndex(data, bomb_index + i)] = true;
    used[getIndex(data, bomb_index - i)] = true;
  }

}

size_t getMaxBombValueRecursive(const vector<Bomb>& data, vector<bool>& used, unordered_map<vector<bool> , size_t>& cache) {
 auto cache_search =  cache.find(used);
 if(cache_search != cache.end()) {
    return cache_search->second;
  }
  size_t max = 0;
  size_t working_value;
  for(int i = 0; i < data.size(); i++) {
    if (!used[i]) {
      vector<bool> new_used = used;
      toggleBomb(data, new_used, i);
      working_value = data[i].value + getMaxBombValueRecursive(data, new_used, cache);

      if(working_value > max) {
        max = working_value;
      }
  }
  }

  cache.emplace(used, max);
  return max;
}


int main()
{

  vector<Bomb> in_data = {{5,7},{5,2},{2,3},{6,4},{6,10},{1,4},{2,5},{4,5},{3,3},{3,8}};


  cout << getMaxBombValue(in_data) << endl;
  return 0;
}

First lets solve this problem as an array, rather than a circle.

dp[i][j] denotes the maximum value we can get, when in the first i bombs, the last bomb activated is j.
val[i] is the value of bomb i. effect[i] is the influence range of bomb i.

dp[i][i] = max(dp[i-1][k])+val[i], where k<j and k+effect[k]<j and j-effect[j]>k
dp[i][j] = dp[i-1][j] when j<i (obviously, cuz in this case no new bomb is activated);

The answer is max(dp[n][i], i=1...n)

How do we apply this to a circle? It's easy, lets just duplicate the N elements to form 2N element array so that bomb[1..n] are the original elements, bomb[i = n+1...2n] = bomb[i-n];

Then we can apply the above dynamic function. But notice that any bomb on a circle can be the starting bomb, so we need to iterate through 1 to N as the starting bomb, and make sure when it is the starting bomb, it is activated.

The code is as follows:
1. Duplicate N-element circle into 2N elements array
Int ans=0;
For (int i=0;i<n;i++) {
Dp[i]=val[i];
Ans=max(dp[i],ans);
For (int j=i+1;i<=i+n-1;j++) dp[i]=-1;
For (int j=i+effect[i]+1;j< i+n-effect[i];j++)
If (j-effect[j]>I && j+effect[j]<i+n)
{
For (int k=j-effect[j]-1;k>=I;k--)
If (k+effect[k]<j)
Dp[j]=max(dp[j],dp[k]);
Dp[j]+=val[j];
Ans=max(ans,dp[j]);
}
}

My python solution with memoization.

def bombs(bombs):
    """Maximise bomb value

    Optimbal substructure:
        e(i)    - effect
        v(i)    - value
        N       - bomb count
        V(i, j) - maximum value of blowing bombs in range [i..j)

        V(i, j) =
            | i >= j    = 0
            | otherwise = max{V(i + 1, j),
                              V(i + 1 + e(i), min{j, N + i - e(i)}) + v(i)}

    Example:
        >>> bombs([(0, 2), (1, 1), (1, 3)])
        5
    """
    cache = {}
    def bombs_rec(i, j):
        val = cache.get((i, j))
        if val is None:
            if i >= j:
                val = 0
            else:
                ei, vi = bombs[i]
                val = max(bombs_rec(i + 1, j),
                          bombs_rec(i + 1 + ei, min(j, N + i - ei)) + vi)
        return val
    N = len(bombs)
    return bombs_rec(0, N)

Algorithm sketch:
max_bomb(v, r, denote_nothing) = max { v[i] + max_bomb(v, r, denote_i | i = 0 .. n-1}, where denote_nothing represent the initial state.

#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

bool in_range( vector<int> r, int j, int i ){
  if (j < r.size() && i < r.size() && abs(j - i) <= r[i])
    return true;
  else
    return false;
}

int max_bomb( vector<int> v, vector<int> r, vector<bool> destroy){
  int n = v.size();
  int max = 0;
  vector<bool> flip; // for recovery
  for(int i = 0; i < n; i++)
    flip.push_back(false); // change from valid to destroy

  for(int i = 0; i < n; i++ ){
    if( ! destroy[i] ){
      destroy[i] = true;
      for( int j = 0; j < n; j++){
	if( in_range(r, j, i) && !destroy[j]){
	  destroy[j] = true;
	  flip[j] = true;
	}
      }
      int cur = v[i] + max_bomb( v, r, destroy);
      max = cur > max? cur : max;
      // recover
      destroy[i] = false;
      for( int j = 0; j < n; j++){
	      if(flip[j] == true){
	        destroy[j] = false;
	      }
      }
    }
  }
  return max;  
}

int main(){
  vector<int> v;
  v.push_back(2);
  v.push_back(1);
  v.push_back(3);

  vector<int> r;
  r.push_back(0);
  r.push_back(1);
  r.push_back(1);

  vector<bool> destroy;
  for(int i = 0; i < v.size(); i++)
    destroy.push_back(false);

  int max = max_bomb(v, r, destroy);
  cout << max << endl;
}

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

namespace std{
  template<typename T>
  struct hash<pair<T, T>>{
    inline size_t operator()(const pair<unsigned int, unsigned int> & v) const{
      return v.first << 8 + v.second;
    }
  };
}

template<typename TR, typename TV, typename TI>
TV bomb(const vector<pair<TR, TV>> &bombs, const TI &i, const TI &j){

    static unordered_map<pair<TI, TI>, TV> mem;
    
    auto el = mem.find(make_pair(i, j));
    if (el != mem.end()){
        return (*el).second;
    }

    if (i > j){
      return 0;
    }
    
    TV ei_v = bombs[i].second;
    TR ei_r = bombs[i].first;
    
    TV no_ith = bomb(bombs, i+1, j);
    TV with_ith = bomb(bombs, i+1+ei_r, j) + ei_v;
    
    TV local_max = max(no_ith, with_ith);
    
    mem.emplace(make_pair(i, j), local_max);
        
    return local_max;
}

int main(){
   vector<pair<int, int>> bombs = {{0, 2}, {1, 1}, {1, 3}};
   cout << bomb(bombs, 0, static_cast<int>(bombs.size() - 1)) << endl;
}

Matrix chain multiplication.

PS: negative vote people first read this algorithm and then try to relate that. you will find answer. and if you can't. just don't vote -ve