Google Interview Question
InternsCountry: CHINA
Interview Type: Phone Interview
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];
}
}
As discussed in other posts, this kind of approach does not seem to work. You lose information about the circle part. few cases where you solution fails (you can use my semi-brute force given above to find more):
v: 6 8 3
r: 7 3 1
Answer is 8, your code gives 9
v: 1 4 3
r: 9 0 3
Answer is 7, your code gives 5
v: 7 2 3 4 10 4 5 5 3 8
r: 5 5 2 6 6 1 2 4 3 3
Answer is 18, your code gives 19
@Miguel, you are right. As sequence matters, we can't simply split this circle in 2 parts and calculate them serperately. Maybe we have to use some sort of brute force.
The solution can be easily modified to be correct.
after detonating the first bomb, the circle is breaked up to a line;
after detonating every subsequent bomb, a line is breaked up into 2 lines.
Just need to handle the first bomb (loop through all bombs as the first bomb)
adds a factor of n in the complexity. But gonna be polynomial
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))
This does not work because the array is circular, meaning that when you consider position N-1 you must not take into account positions 0..r[N-1] because they are neighbors
See the python solution posted above. Besides "i" you also need an "up_to_j" variable because positions j+1..N-1 were affected before.
I dont think that it is missing any case even with a single variable i. Can you give some counter example?
For example:
v = { 1, 3, 1, 1, 1, 1 }
r = { 1, 2, 1, 1, 0, 0 }
The best is 4 by taking the 2nd and 5th bombs with value 3 and 1 (it affects the last bomb, so we can't add that one). However, following your description,
d = { 1, 3, 3, 3, 4, 5 } because for the last bomb, you have no way to check that that value 4 actually includes a bomb that affects the last bomb.
@Miguel Oliveria, isn't the ans for the test case given by you is 6:
v = { 1, 3, 1, 1, 1, 1 }
r = { 1, 2, 1, 1, 0, 0 }
The best is 6 by taking 5th, 6th, 4th and then 2nd bombs respectively.
@karaamaati no, it's not. Bomb 2 affects bomb 6, so we can't take both. Bomb 4 affects bomb 5, so we can't take both as well.
@miguel - if the bombs were exploded in the order mentioned by karaamaati, you can get value of 6. So, what karaamaati said is right.
I'm thinking about modifying alex solution:
(1) duplicate the input to make a circle
Ex. given: v[]= { 1, 3, 1, 1, 1, 1 }, r[] = { 1, 2, 1, 1, 0, 0 },n=6
duplicate it to be:
v'[] = { 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1 }
r'[] = { 1, 2, 1, 1, 0, 0, 1, 2, 1, 1, 0, 0 }
(2) let dp[i] = {max dp[j]+v[i] | i is not in range of r[j] (consider i and j in a circle)} or {max dp[j] | i is in range of r[j]},
note that the size of dp[] is n
(3) We need another loop: start at the i-th element in v', r' for internal dp; where 0<=i<n; At the end of each loop, let result = max{max of dp[], result};
I think I must have missed something...Could someone give a counter example?
No,but the idea which use a array dp[i][j] to solve this problem is right.So I think n^3 is OK.
when a bomb explodes, is the circle readjusted? I don't see anything pointing to that in the question but someone asked it and now that i checked the example it seems the order to explode the bombs matter.
If that's the case, then the problem is even much harder and the DP[i][j] solution above does not work.
I had assumed that we had to pick a set of "non-overlapping" bombs, like if they were detonated at the same time.
That was the most natural "dynamic programming" way for me to solve this question.
In this case, the above python solution does not work. I don't have an efficient solution for this, i'll think about it :)
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
no it doesnt. contradicting examples-
v 1 1 10 1
r 0 1 2 1
greedy solution (wrt range) will destroy the bomb with v 10.
another eg:
v 10 5 8
r 5 0 0
greedy solution wrt Value will destroy 5 and 8 both - which are part of actual solution (ans= 23).
No it does not. In the first example the greedy solution will take 1th and then 3th. (1th will dismiss 0, 3th will dismiss 2. In the second step, others would dismiss 10)
Second example: Firstly take 5 or 8, then take the second and then 10.
The greedy introduced looks good.
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)
Sorry forget to add actual update of cache dictionary
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)
cache[(i, j)] = val
return val
N = len(bombs)
return bombs_rec(0, N)
We should just leave the ith bomb in the circle rather than simply remove it when it is not denoted or be affected by others.
Maybe we can set the value of the denoted and affected bombs to 0, and assume that the bomb is still there but we'll never need to denote the bombs whose value is zero. Then we try in this circle over and over again until every bomb's value is set to 0.(It's just a rough idea and I don't know how to implement it for now.)
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;
}
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.
This takes O(2^N * N^2) time and O(2^N) memory. It's ok for N up to 20~22.
- Miguel Oliveira September 20, 2013To 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.