trevorvanloon
BAN USERI have found a nice O(N) time and O(1) space algorithm for this problem (I know its been 4 years but bear with me). A few observations led me to this algorithm:
1. If we idealize and imagine we have O(N) space we can cache the heights of each node we've considered before and for later nodes we can simply go up the tree until we hit a parent in the cache when we instantly know the height and can add all nodes we saw on that path to the cache with their corresponding heights. This is what many people have done in their O(N) time O(N) space solutions. Its clear that this runs in O(N) time as each node in the tree is considered at most twice (except the root).
2. A natural extension to obtain a constant space algorithm would then be to try to use the existing array as a cache. This is exactly what I have achieved. I realized that if we cache the heights directly in the array, we will have no way to tell on successive iterations when to "bail out" and compute the heights from the cached value, as they'd be indistinguishable from other nodes in the array. For example, if we have an array:
[2,0,-1], computing and caching the height of node 0 and its predecessors yields an array that looks like [2,1,-1], but when we consider node 1, it will naively think the value at arr[1] is the predecessor and we will get nonsense output.
Thus, in order for nodes to distinguish between cached values and predecessor values, I cache N+height_of_node. Then, caching works as described in part 1, if I perform comparisons of the predecessor value with N to determine if it is a cached height or not.
Here is the algorithm in C++ (feel free to comment or ask questions):
//This function runs in linear time because each node that is "observed" is set to N+k for some k.
int findTreeHeightFromArray(vector<int> arr) {
int max_height = 0;
int N = arr.size();
for (int i = 0; i < arr.size(); i++) {
if (arr[i] >= N) {
//its been marked by a lower node so continue:
continue;
}
int node = i;
int height = 0;
while (arr[node] != -1 && arr[node] < N) {
node = arr[node];
height++;
}
//now go up the tree from i until node and set their values
int top_height = 0;
if (arr[node] >= N) {
top_height = arr[node]-N;
}
node = i;
int tmp_height = N + top_height + height;
while (arr[node] != -1 && arr[node] < N) {
int temp = arr[node];
arr[node] = tmp_height;
tmp_height--;
node = temp;
}
}
for (int i = 0; i < arr.size(); i++) {
if (N - arr[i] > max_height) {
max_height = arr[i] -N;
}
}
return max_height;
}
I have a nice one:
1. Starting with the first Person in the array, scan until you find someone that A knows. If there is no such person, A must be the celebrity. Else, we find some person K. Continue scanning left to right in our array until you find someone K knows. Repeat this process until we reach the end of the array. Then the last person L we considered is our only candidate celebrity as at most one celebrity can exist and:
a. Our celebrity can't have occurred before L or else some previous person would have detected L in our pass.
b. The celebrity can't occur past L in the list or else we would have seen it in our pass from L->end of list.
These observations imply either L is the celebrity or there is no celebrity at all (which can occur if and only if L knows someone earlier in the list.) So we do a final scan of the list and check that L knows nobody.
Short and sweet O(N^2) solution by finding all palindromes "anchored" at a char or a pair of chars.
void match(vector<string>& results, string s, int left, int right) {
int n = s.length();
while (left >= 0 && right < n && s[left] == s[right]) {
results.push_back(s.substr(left, right - left + 1));
left--;
right++;
}
}
vector<string> findPalindromicSubstrings(string s) {
vector<string> results;
int n = s.length();
for (int i = 0; i < n; i++) {
match(results, s, i, i + 1);
match(results, s, i, i);
}
return results;
}
- trevorvanloon April 17, 2017int main() {
string s;
cin >> s;
list<int> digits = { 1,2,3,4,5,6,7,8,9 };
int index = 0;
list<int> frequencies;
int count = 1;
int lastChar = s[0];
char firstChar = s[0];
for (int i = 1; i < s.length(); i++) {
if (s[i] != lastChar) {
//add segment to list:
frequencies.push_back(count);
count = 1;
lastChar = s[i];
}
else {
count++;
}
}
frequencies.push_back(count);
bool isD = firstChar == 'D';
string result = "";
bool isFirst = true;
while (!frequencies.empty()) {
if (isD) {
auto f = frequencies.front();
string digits_string = "";
for (int i = 0; i < f; i++) {
digits_string += to_string(digits.front());
digits.pop_front();
}
if (isFirst) {
digits_string += to_string(digits.front());
digits.pop_front();
isFirst = false;
}
std::reverse(digits_string.begin(), digits_string.end());
result += digits_string;
frequencies.pop_front();
isD = !isD;
}
else {
auto inc = frequencies.front();
frequencies.pop_front();
for (int i = 0; i < inc - 1; i++) {
result += to_string(digits.front());
digits.pop_front();
}
if (isFirst) {
result += to_string(digits.front());
digits.pop_front();
isFirst = false;
}
auto d = frequencies.front();
std::list<int>::iterator i = digits.begin();
std::advance(i, d);
result += to_string(*i);
digits.erase(i);
isD = !isD;
}
}
cout << result << endl;
}}
- trevorvanloon April 09, 2017Here's a recursive solution. The idea is that for each Node n, we can set that Nodes value as the sum of nodes larger than it that come before it in a preorder traversal plus the sum of the right subtree of that node, plus its value. Hence we can have our function's return value yield subtree sizes, and use a parameter sum_above to pass in the sum we've seen so far larger than the current value. Thus we can compute the solution recursively in linear time and constant space:
int replaceNodes(TreeNode*& root, int sum_above) {
if (root == 0) {
return 0;
}
int sum_right = replaceNodes(root->right, sum_above);
int sum_left = replaceNodes(root->left, sum_right + sum_above + root->data);
int temp = root->data;
root->data = sum_right + sum_above + temp;
return sum_right + sum_left + temp;
}
- trevorvanloon April 07, 2017It can be done in O(N+M) time and O(min(N,M)) space by creating a hash map recording the frequencies of occurrence of each element of the smaller list first. Then we iterate through the other list and for each element x, add H(n-x) to our total count, where H(n-x) obtains the frequency of n-x in the smaller list. This yields the total pair count.
- trevorvanloon April 07, 2017Assuming the problem is: Given a sorted array, find how many times an element occurs in sublinear time. Here's some code to do just that in O(logn) which uses a modified binary search to find the left most occurrence of the element and the rightmost occurrence and taking the difference plus one to get total occurences.
int binarySearch(vector<int> arr, int left, int right, int x, bool go_left) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] == x) {
if (go_left && mid-1 >= 0 && arr[mid-1] == x) {
return binarySearch(arr, left, mid - 1, x, go_left);
}
else if(!go_left && mid + 1 < arr.size() && arr[mid + 1] == x) {
return binarySearch(arr, mid + 1, right, x, go_left);
}
else {
return mid;
}
}
else {
if (arr[mid] > x) {
return binarySearch(arr, left, mid - 1, x, go_left);
}
else {
return binarySearch(arr, mid + 1, right, x, go_left);
}
}
return -1;
}
int main() {
int N,X;
cin >> N >> X;
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
int left_index = binarySearch(a, 0, a.size() - 1, X, true);
int right_index = binarySearch(a, 0, a.size() - 1, X, false);
if (right_index == -1 || left_index == -1) {
cout << -1 << endl;
}
else {
cout << right_index - left_index + 1 << endl;
}
}
- trevorvanloon April 07, 2017Using a Heap to keep track of the bucket with minimal weight, a greedy algorithm yields an O(n*logn) solution.
class HeapNode {
public:
int weight;
int bucket_index;
HeapNode() {};
HeapNode(int w, int b) : weight(w), bucket_index(b) {};
friend bool operator<(const HeapNode& h1, const HeapNode& h2) {
return h1.weight < h2.weight;
}
friend bool operator>(const HeapNode& h1, const HeapNode& h2) {
return h1.weight > h2.weight;
}
};
typedef priority_queue<HeapNode, vector<HeapNode>, std::greater<HeapNode>> min_queue;
void findBestDistribution(vector<vector<int>>& buckets, const vector<int>& a, min_queue& q) {
for (int i = a.size()-1; i >= 0; i--) {
//find bucket with minimal weight using our heap:
HeapNode h = q.top();
q.pop();
int bucket_index = h.bucket_index;
buckets[bucket_index].push_back(a[i]);
q.push(HeapNode(h.weight + a[i], bucket_index));
}
}
int main() {
int N,K;
cin >> N >> K;
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
vector<vector<int>> buckets(K, vector<int>());
min_queue q;
for (int i = 0; i < K; i++) {
q.push(HeapNode(0, i));
}
findBestDistribution(buckets, a, q);
for (int i = 0; i < K; i++) {
vector<int> bucket = buckets[i];
for (int j = 0; j < bucket.size(); j++) {
cout << bucket[j] << " ";
}
cout << endl;
}
}
This is from the google code jam this year lol
- trevorvanloon April 21, 2017