lemonedo
BAN USERWell, it's a simple, recursive solution.
Suppose that for an integer sequence S, there is a function f that returns a set of sequences f(S) where all sequences in f(S) makes the same binary search tree.
If S has only one element, then f(S) is a set of size 1 and it has S as an element.
If S has more than one element, we can split it into one element r and two sequences A and B, where r is the first element of S, A is such that x < r for all x in A, B is such that x >= r for all x in B. If you make a binary search tree from S, then r would be the root and all elements in A will be descendants of the left child of the root and all elements in B will be descendants of the right child.
Now we can create new sequences which make the same tree by "mixing" elements A and B and inserting r at the front, but preserving the orders in A and B; for example, if A is [1, 2, 3], and B is [4, 5, 6], mixing A and B would produce sequences like [1, 4, 2, 5, 3, 6] and [1, 2, 4, 3, 5, 6].
But note that in the tree of S, A and B each makes a subtree of their own. Therefore we need to mix all combinations of f(A) and f(B).
Here is the summary of the algorithm:
For an integer sequence S, f(S) is a set of sequences which make the same binary tree as S.
If the size of S is 1, f(S) = {S}.
If the size of S is more than 1, split S into r, A, B where r is the first element of S, A is a subsequence of S where x < r for all x in A, B is a subsequence of S where x >= r for all x in B. Then f(S) = {X | X = (r, W)} for all W ∈ g(Y, Z) where Y ∈ f(A), Z ∈ f(B), and g(Y, Z) is a function returning a set of sequences which have Y and Z as subsequences.
For each point, test if the origin is on the line or on the same side as the current point when the plane is split by the line that the other two points make.
from collections import namedtuple
Point = namedtuple('Point', 'x y')
ORIGIN = Point(0, 0)
def contains_origin(points):
for i in xrange(len(points)):
p = points[i]
rest = points[:i] + points[i + 1:]
origin_position = above_or_below_or_on(ORIGIN, rest)
if origin_position == 'on':
return True
elif origin_position != above_or_below_or_on(p, rest):
return False
return True
def above_or_below_or_on(point, rest):
a = rest[0]
b = rest[1]
d = float(a.y - b.y) / (a.x - b.x) * (point.x - b.x) + b.y
if point.y > d:
return 'above'
elif point.y < d:
return 'below'
else:
return 'on'
if __name__ == '__main__':
print(contains_origin([
Point(1, 0),
Point(0, 3),
Point(-2, -1),
]))
from __future__ import print_function
import itertools
import re
import sys
def iter_binary_tree_permutations(numbers):
"""Iterates all permutations of a given sequence such that the permutation
makes the same binary search tree as the original sequence.
"""
if not numbers:
yield []
return
root = numbers[0]
left = []
right = []
for n in itertools.islice(numbers, 1, None):
if n < root:
left.append(n)
else:
right.append(n)
for lp, rp in itertools.product(iter_binary_tree_permutations(left),
iter_binary_tree_permutations(right)):
for p in iter_splices(lp, rp):
yield [root] + p
def iter_splices(a, b):
"""Iterates all splices for two given sequences.
>>> for splice in iter_splices([1, 2], [3, 4]): print(splice)
[1, 2, 3, 4]
[3, 1, 2, 4]
[3, 4, 1, 2]
[1, 3, 2, 4]
[1, 3, 4, 2]
[3, 1, 4, 2]
"""
if not a:
yield b
return
indices = range(len(b) + 1)
for partitions in iter_partitions(a):
k = len(partitions)
for pivots in itertools.combinations(indices, k):
ret = b[:pivots[0]]
for i in xrange(k - 1):
ret.extend(partitions[i])
ret.extend(b[pivots[i]:pivots[i + 1]])
ret.extend(partitions[k - 1])
ret.extend(b[pivots[k - 1]:])
yield ret
def iter_partitions(a):
"""Iterates all partitions for a given sequence.
>>> for partitions in iter_partitions([1, 2, 3]): print(partitions)
[[1, 2, 3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1], [2], [3]]
"""
yield [a]
indices = range(1, len(a))
for num_pivots in xrange(1, len(a)):
for pivots in itertools.combinations(indices, num_pivots):
ret = [a[:pivots[0]]]
for i in xrange(num_pivots - 1):
ret.append(a[pivots[i]:pivots[i + 1]])
ret.append(a[pivots[num_pivots - 1]:])
yield ret
if __name__ == '__main__':
numbers = [4, 3, 1, 2, 6, 5, 7]
# numbers = [int(n) for n in re.split(r'\s*,\s*', sys.stdin.read().strip())]
for p in iter_binary_tree_permutations(numbers):
print(p)
// Assumptions:
// 1) Intensity is represented by an integer.
// 2) A pixel is reacable by another pixel if they are facing each other
// vertically or horizontally, but not diagonally.
#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;
// Input format:
// i j
// n
// [n * n numbers]
//
// * (i, j) denotes the given pixel at (i + 1)th row, (j + 1)th column
// * n is the width and height of the screen
// * Each number is separated by whitespace characters.
//
// Sample input:
// 2 2
// 5
// 0 0 1 2 0
// 0 1 3 1 0
// 0 0 0 1 1
// 1 2 0 0 4
// 0 0 0 0 0
//
// Sample output:
// 13
int main() {
int i, j, n;
cin >> i >> j >> n;
int index = i * n + j;
int size = n * n;
int* screen = new int[size];
for (int i = 0; i < size; i++) {
cin >> screen[i];
}
int target_intensity = screen[index];
int count = 0;
unordered_set<int> visited;
stack<int> s;
s.push(index);
while (!s.empty()) {
int cur = s.top();
s.pop();
if (visited.count(cur) != 0) continue;
visited.insert(cur);
if (screen[cur] != target_intensity) continue;
count++;
int cur_i = cur / n;
int cur_j = cur % n;
if (cur_i > 0) s.push(cur - n);
if (cur_j > 0) s.push(cur - 1);
if (cur_i < n - 1) s.push(cur + n);
if (cur_j < n - 1) s.push(cur + 1);
}
cout << count << endl;
delete[] screen;
}
How can you find the corresponding number in O(1) in the double loops? It's impossible if you want keep memory usage in O(1) (other than the input). If you use a hash set, then the space complexity would be O(n). Also you must take zeros into account (if you don't, your algorithm will output duplicate combinations). Actually there are four cases where three numbers sum to zero:
1. n + n + p = 0
2. n + p + p = 0
3. n + z + p = 0
4. z + z + z = 0
where n is for negative, p for positive and z for zero. The corrected algorithm would be as follows:
1. Sort the input in ascending order. O(nlogn)
2. Find the indexes where zeros and positive numbers start. O(n)
3. Make a hash set S for negative and positive numbers. It is used to test whether a number is in the input. O(n) for both time and space.
4. Run a double for-loop on negative numbers. For a pair of two negative numbers (a, b), find the corresponding positive number c such that c = -(a + b) using the hash set S. Print the three numbers (a, b, c) if such c is found. O(n^2)
5. Run a double for-loop on positive numbers in a way similar to 4. O(n^2)
6. If there is a zero in the input, run a single loop on negative numbers. For each negative number a, find a positive number b using the hash set S which has the same absolute value, i.e. b = -a. Print (a, b, 0) if such b is found. O(n)
7. If there are three or more zeros, print (0, 0, 0). O(1)
Overall: O(n^2) for time, O(n) for space
EDIT: it still can output duplicate combinations. The algorithm should be modified to handle separately numbers appearing only once and twice or more.
If the screen array can be modified, my algorithm can be changed so that the set is not necessary. It's obvious it can be modified in my code since they are just holding the input. But if it is written as a reusable function like Nitin's, then the assumption that the screen array can be modified may not always be true. And if it is not true, using a hash set is more memory efficient way than creating a copy of the screen array. Also Nitin's takes more memory for its call stacks. As N goes to large, the difference becomes significant.
- lemonedo April 28, 2014