harcisis
BAN USERSame 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;
}
RepSpent 2001-2007 promoting augmented reality integrated through social media in West Palm Beach, FL. Won several awards for merchandising Roombas ...
O(Nlogk) solution. k - number of servers + (time to request and pass n/2 numbers between the servers)
- harcisis December 06, 2014Inspired by Saurabh's second solution.
1. Sort billion numbers individually on each server. Since its a fixed sized 32 bit long integers, we can use radix sort to sort in O(N) time.
2. Let's introduce min heap on one of the machines. Heap size would be equal to 10000 (k).
3. Ask each machine for min value and insert this values to the heap (keeping information which server this value came from)
4. Let's introduce counter to keep track of how many values we have considered.
5. Get min value from the heap, ask server-origin of this value for next min value and insert it into the heap. Increment the counter (O(logk) + query time)
6. Do step 5 till we get through half of the values. Compute median by picking exact value (if we can have one) or finding average of two values at the center.