anotherguy
BAN USERWater is stored at a point if there are buildings at both sides of it.
If for some X, we know the max. height of the building to the left and the right and the height of the building there, we can calculate the height of water at X.
Let us take the case height = {3, 2, 1, 5}. Let's make two arrays Lmax and Rmax, which store the max. height of the building to the left and to the right. We can do this in O(n):
Lmax = {0, 3, 3, 3}
Rmax = {5, 5, 5, 0}
Now water_height[i] = max(0, min(Lmax[i], Rmax[i])-height[i])
So water_height = {0, 1, 2, 0} and thus total water height = 3
Total time complexity = O(n)
Total space complexity = O(n)
sorry, yes the running time should be O(n log k)
- anotherguy October 17, 2013If I'm not wrong, this should be O(n + k log k). Anyways, nice solution.
- anotherguy October 17, 20132348 would have 2, 3, 4, 8, 2*3, 2*4, ....
as you can see 8 comes twice, and hence 2348 is not valid
As @@@@@@@ said, checking against {2, 3, 6}, {2, 4, 8}, {3, 4, 6, 8} will suffice because {2, 3, 4, 6} and {2, 3, 6, 9} are supersets of {2, 3, 6}
- anotherguy October 14, 2013First thing which should be done is make a set of all digits in the number.
Case 1. If any digit is present twice in the set, then our number is not valid.
Case 2. If the digit 1 is present, then it is not valid.
Case 3. If all digits are unique and 1 is not present, then there must be two subsets, say {d1, d2,.. dk} and {e1, e2, .. el} s.t.
d1*d2*..dk = e1*e2*...el
If some of the digits on both sides are the same, then remove them from both. So we have two non-intersecting subsets such that
d1*d2*..*dk = e1*e2*..*el
Suppose the digit 7 is present on either side. Then the other side should also have 7 as a factor, which is not possible(because 7 cannot be repeated and no other digit is divisible by 7). Same thing with 5.
So both sides can only have 2 and 3 as prime factors. Let us enumerate all such possible cases:
2*3 = 6
2*4 = 8
2*6 = 3*4
2*8 = No other combo
2*9 = 3*6
3*4 = 2*6
3*6 = 2*9
3*8 = 4*6
3*9 = No other combo
4*6 = 3*8
4*8 = No other combo
4*9 = No other combo
6*8 = No other combo
6*9 = No other combo
8*9 = No other combo
So a number is invalid if
1. Digits repeat
2. The digit 1 is present
3. Any one of these is a subset of the digits: {2, 3, 6}, {2, 4, 8}, {2, 3, 4, 6}, {2, 3, 6, 9}, {3, 4, 6, 8}
Can you please explain how it is equivalent to vertex cover?
- anotherguy October 06, 2013@Nitin: Goku can attack only one row OR one column at a time. So first he will attack the last row and then the first column!
- anotherguy October 06, 2013Wrong solution. Counter example:
Suppose the grid is(d denotes a demon)
d - -
d - -
d d d
count_row = 3, count_col = 3, your output will be 3.
optimal solution = 2(first row, first column)
Okay, this is my solution which uses O(sqrt N) space, operation 1 can be done in O(sqrt x) and operation 2 can be done in O(1). Worse time complexity than Fenwick tree but better space complexity and better complexity for operation 2.
Store sums in an array s like this:
s[0] = sum(arr[0^2..1^2])
s[1] = sum(arr[1^2..2^2])
s[2] = sum(arr[2^2..3^2])
s[3] = sum(arr[3^2..4^2])
s[4] = sum(arr[4^2..5^2])
.
.
Extra space = O(sqrt N)
Now operation 1 can be done by adding elements of s from 0 to floor(sqrt x) + elements of arr from 2^(floor(sqrt x)) to x = O(sqrt x)
Operation 2 can be done in O(1) time, just add/subtract value t from the corresponding element in s.
Wait, I don't get what is meant by "TWO EQUAL PARTS"? Is it necessary for them to be the two equal halves or can they be any two subsequences of the string. If it is the former, look at my answer above, otherwise it is a special case of the "2-partition problem" and is weakly NP-complete, i.e. it can be solved in pseudo-polynomial time using DP. I'm giving a recursive solution in python here(for each element choose whether it is to be included in the first part or the second):
def any_equal_sum(str):
lis = map(lambda(x): ord(x)-ord('0'), list(str))
if(len(lis)%2 != 0 or sum(lis)%2 != 0): return str
if(is_subset_with_sum(lis, sum(lis)/2, len(lis)/2)):
return "12345"+str
else:
return str
def is_subset_with_sum(lis, s, length):
if(length>len(lis)): return False
if(length==0): return s==0
return (is_subset_with_sum(lis[:-1], s, length) or is_subset_with_sum(lis[:-1], s-lis[-1], length-1))
any_equal_sum("667788")
returns
"12345667788"
and
any_equal_sum("66788")
returns
"66788"
Here is some python code, which I believe does the trick. Basically you make a list of characters from the given string and then make a list of ASCII values named 'lis'. Then you check two conditions: the length of lis should be even, and the sum of the first half should be equal to the sum of the second half. If the conditions hold, then prepend "12345" to str and return it, otherwise return it as it is:
def is_equal_sum(str):
lis = map(ord, list(str))
if((len(lis)%2 == 0) and sum(lis[:(len(lis)/2)])==sum(lis[(len(lis)/2):])):
return "12345"+str
else:
return str
is_equal_sum("678876")
returns
'12345678876'
is_equal_sum("67887")
returns
'67887'
T is the cost, losses must be added and gains must be subtracted from cost. So we add K, K/3 and subtract C!!
- anotherguy September 15, 2013Prob.(successful first launch) = 0.8
T(successful first launch) = K - C
Prob.(successful second launch) = (0.2)(0.8)
T(successful second launch) = K+(K/3)-C
Prob.(successful third launch) = (0.2)^2(0.8)
T(successful second launch) = K+(2K/3)-C
Prob.(successful fourth launch) = (0.2)^3(0.8)
T(successful second launch) = K+(3K/3)-C
Prob.(successful fifth launch) = (0.2)^4(0.8)
T(successful second launch) = K+(4K/3)-C
Prob.(unsuccessful experiment) = (0.2)^5
T(successful second launch) = K+(4K/3)
This is the probability distribution of T:
Prob.(T = K - C) = 0.8
Prob.(T = 4K/3 - C) = 0.16
Prob.(T = 5K/3 - C) = 0.032
Prob.(T = 6K/3 - C) = 0.0064
Prob.(T = 7K/3 - C) = 0.00128
Prob.(T = 7K/3) = 0.00032
Suppose the dictionary has {"ad", "ae", "aeg", "age"}. It will look like:
{}
2|
{}
7/ \3
{} {"ad", "ae"}
3| |4
{"are"} {"aeg"}
Can you please provide a solution for those of us who don't know "the celebrity problem"? Thank you so much!
- anotherguy September 11, 2013Does not work, even for positive numbers.
Just tried running your code with {1, 2, 3, 0, 4, 5}, gives 120
How do you get the greater than or equal to sign? I swear I typed it like that but it was converted to a semicolon! The ++ was a typo.
- anotherguy September 09, 2013@Erasmus:
What if you have an array with all negatives? You are not considering any negative products, so your answer will be undefined in this case.
I think we should initialize the max. global sum to -infinity, then consider all positive products as you suggested, and all non-positive numbers individually as well!
@hj:
both varun and venkatesh's solution are based on counting sort coupled with the fact that every element <= n-1. Thus if we divide any element by n, it is 0. So they use counting sort in-place and add n to elements. In the second pass, while dividing by n, the original content does not matter and we get the frequency. So we are not using any 'extra' space!
Newton busted that one!
- anotherguy September 08, 2013@Nitin: No, he's considering all the cases. Let me explain his strategy with an example,
[1, -2, 3, 4, -5, 0, 2, 5, 1, 0, 8, -3, 1, 0, 0, 1, 3, -5, 7, -6, 2, -2, 2]
Consider all maximal non-zero subarrays:
[1, -2, 3, 4, -5]: there are 2(even) -ve numbers so take the product as it is, i.e. 120
[2, 5, 1]: there are 0(even) -ve numbers so take the product as it is: 10
[8, -3, 1]: there is 1(odd) -ve numbers, so take the two positive products, i.e. 8 and 1
[1, 3, -5, 7, -6, 2, -2, 4]: there are 3(odd) -ve numbers, so take the two biggest positive products, i.e 1 to -2 = 1260 and 7 to 4 = 672
Clearly the biggest product is 1260.
I just want to mention one thing: initialize the maximum global sum to -infinity. If there is at least one zero in the array, initialize it to 0.
The above code will not yield a uniform distribution.
As Erasmus suggested, you can use the Fisher-Yates-Knuth shuffle algorithm, which gives a uniform shuffle. Here is the code of the modern version:
.
for(int i=n-1; i>0; i++) {
swap(arr+random(i), arr+i);
}
use the suitable algorithm
- anotherguy September 08, 2013Use a trie with a twist: Rather than using english alphabets for traversal, use corresponding numbers:
1 for a, b, c
2 for d, e, f
and so on
So taking the path 12 should yield ad, ae, af, bd, be, bf.
I assume we can use a random number generator such that random(n) returns a value between 0(inclusive) and n(exclusive)
.
for(int i=0; i<n; i++) {
swap(arr+random(n), arr+random(n));
}
Also, I think we have different notions of "nearest". My understanding is that distance is the length of the shortest path between two nodes.
So if you have
1
2 3
4 5 6 7
8 9 10 11
then the distance between 2 and 8, 9, 10, 11 is 2. The distance between 2 and 6, 7 is 3.
Your approach will give the answer 6 or 7, which is wrong.
Sorry for the bad formatting.
- anotherguy September 08, 2013I don't think that would work. The nearest leaf node can be above the given node as well. Even if it's not, a leaf node just 1 level below might be very far while a leaf node 2 levels below might just be 2 nodes away.
- anotherguy September 08, 2013A node might not be an ancestor to its nearest leaf node.
1
/ \
2 3
/ \
4 5
/ \ / \
6 7 8 9
/ \ / \ / \ / \
10 11 12 13 14 15 16 17
In the above case, the nearest leaf node to 2 is 3.
We want to traverse the tree using DFS, storing the minimum height and the closest descendant leaf at each node:
1(1, 3)
/ \
2(3, 10) 3(0, 3)
/ \
... ...
Then starting from the given node, we want to go up to the root and check the path which is the shortest.
So in this case, nearest leaf to 2 is at distance
min(3, 1+1) = 2
Suppose the tree looked something like:
N(hN, cN)
/ \
NL(hNL, cNL) NR(hNR, cNR)
/ \ / \
NLL(hNLL,..) NLR(hNLR,..) NRL(hNRL,..) NRR(hNRR, cNRR)
/ \ / \ / \ / \
... ... ... .. ... ... ...
Then the leaf closest to NLRLLR would be the corresponding leaf node to
min(hNLRLLR, 1+hNLRLL, 2+hNLRL, 3+hNLR, 4+hNL, 5+hN)
O(N) time, O(N) extra space
You cannot convert a 32 bit decimal number to binary and store it as a 32 bit integer. This is because the max. capacity of a 32 bit integer is ~4e9.
So for example, 100000₁₀ = 11000011010100000₂ and 11000011010100000 exceeds the capacity of a 32 bit integer. Best you can do is print the number. Here's how:
void print_bin(unsigned int num) {
int i;
unsigned int j=1<<31;
for(i=31; i>=0; i--) {
printf("%d", (num&j)>>i);
j >>= 1;
}
printf("\n");
}
The function loops from the MSB to the LSB, printing each bit.
- anotherguy September 08, 2013Just a note - 2 byte integers have a maximum capacity of ~32000 and in this case the max. product can be ~1800000 so overflow can happen.
- anotherguy September 08, 2013The time to construct front_diag and back_diag is O(m*n)
- anotherguy September 06, 2013@sagar: In the case of (26, 1, 70, 11), A can win as follows:
1. A selects 26
2. Now B has to select either 1 or 11 from (1, 70, 11).
3. B selects either 11 or 1.
4. A selects 70.
5. B gets the other one.
So A can make a decision which forces B to not be able to choose 70. I think you probably read the question wrong.
Small mistake in the code above: replace >= by < in the 2nd and 3rd last lines
- anotherguy September 02, 2013@joe kidd: My condition for intersection is that that intersection must be a valid point. I have checked whether the intersection is a valid point or not in the last part of my answer(2 out of the 4 if conditions)
- anotherguy September 02, 2013I believe I have achieved O(n) time and O(1) extra space complexity:-
Let us maintain such an invariant at all times:
The first n numbers of the array are negative.
The next p numbers of the array are positive.
So let the array look like this:
-ve -ve -ve ... -ve; +ve +ve +ve ... +ve; -ve ....
n times p times remaining
Now let us find n1 and p1 such that
-ve -ve -ve ... -ve; +ve +ve +ve ... +ve; -ve -ve -ve ... -ve; +ve +ve +ve .... +ve; -ve ....
n times p times n1 times p1 times remaining
Now let us try to 'consume' the n1 and p1 elements in the n and p elements. We can do this by swapping the 2nd and 3rd blocks(p and n1 elements). If we can do this in O(p+n1) time, then increment n to be n+n1 and p to be p+p1 and keep doing this, we should be able to do this for the whole array in O(n) time.
So the challenge is this:
x1 x2 x3 ... xp; y1 y2 y3 ... yq
has to be rearranged to form
y1 y2 y3 ... yq; x1 x2 x3 ... xp
in O(p+q) time.
If p==q, then it's easy. Just keep on swapping x1, y1; x2, y2 and so on.
If p!=q, suppose p>q without loss of generality. Then swap the elements y1..yq and x1..xq to get
y1 y2 y3 ... yq xq+1 xq+2 ... xp x1 x2 x3 ... xq
and repeat the procedure for the subarray xq+1 xq+2 ... xp; x1 x2 x3 ... xq
This way, it is possible to swap an unequal number of elements in place in O(n) time and O(1) extra space.
Code:
#include<stdio.h>
#include<stdlib.h>
void swap(int* arr, int pos1, int pos2) {
arr[pos1] ^= arr[pos2];
arr[pos2] ^= arr[pos1];
arr[pos1] ^= arr[pos2];
}
void swap_in_place(int* arr, int ff, int fl, int sf, int sl) {
if(ff==fl+1 || sf==sl+1) {
return;
}
if(fl-ff>sl-sf) {
int lesser = sl-sf+1;
int i;
for(i=0; i<lesser; i++) {
swap(arr, ff+i, sf+i);
}
swap_in_place(arr, ff+lesser, fl, sf, sl);
}
else{
int lesser = fl-ff+1;
int i;
for(i=0; i<lesser; i++) {
swap(arr, fl-i, sl-i);
}
swap_in_place(arr, ff, fl, sf, sl-lesser);
}
}
void print_array(int* arr, int size) {
int i;
for(i=0; i<size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void swap_pos_neg(int* arr, int size) {
int neg=0;
int pos=0;
while(neg<size && arr[neg]<0) {
neg++;
}
pos=neg;
while(pos<size && arr[pos]>0) {
pos++;
}
if(pos>=size) return;
while(pos<size) {
int new_neg=pos;
while(new_neg<size && arr[new_neg]<0) {
new_neg++;
}
int new_pos = new_neg;
while(new_pos<size && arr[new_pos]>0) {
new_pos++;
}
swap_in_place(arr, neg, pos-1, pos, new_neg-1);
neg += new_neg-pos;
pos = new_pos;
}
}
void main() {
int size = 5;
int arr[] = {-1, 1, 3, -2, 2};
print_array(arr, size);
swap_pos_neg(arr, size);
print_array(arr, size);
}
This code takes .325 seconds for 10,000 elements.
- anotherguy September 02, 2013This takes O(n^2) time. You are shifting O(n) positive numbers for each of O(n) negative numbers.
- anotherguy September 02, 2013Here's one approach:
Traverse the whole matrix and store all diagonals according to size. If the array size is (n, m), then the diagonal size can range from 1 to min(n, m)
Make two arrays of vectors which will store the two kinds of diagonals.
For example, something like(some kind of pseudo-code):
class Point {
int x, y;
}
Vector<1> front_diags[min(n,m)]
Vector<1> back_diags[min(n,m)]
front_diags[4] will store all diagonals of type / and size 4 as a vector
So if you have the matrix
00100001
00010010
00001100
00001100
00010010
00100001
front_diag =
[[], [], [], [], [], [Point(7, 0)]]
back_diag =
[[], [], [], [], [], [Point(2, 0)]]
because there is only one front diagonal(size 6, starting from (7, 0)) and only one back diagonal(size 6, starting from (2, 0))
Now iterate through min(n,m)-1 to 0, trying to find pairs of the same size that intersect. The first pair you find should be the largest intersecting X in the matrix.
for size = min(n,m)-1 to 0:
for front in front_diag[size]:
for back in back_diag[size]:
if((front.x + back.x - front.y + back.y)%2==0): Intersection point's x coordinate is an integer
if((-front.x + back.x + front.y + back.y)%2==0): //Intersection point's y coordinate is an integer
if((front.x - back.x + front.y - back.y)/2 >= size): //Intersection point is not more than size away from front's start
if((front.x - front.y - back.x + back.y)/2 >= size): // Intersection point is not more than size away from back's start
return size;
kkr.ashish's approach is correct!
Here is my code:
#include<stdio.h>
void main() {
int A[] = {2, 4, 6, 8, 10, 12};
int N = sizeof(A)/sizeof(A[0]);
int O1[N], O2[N], O[N];
int i;
O1[0]=1;
O2[N-1]=1;
for(i=1; i<N; i++) {
O1[i] = O1[i-1]*A[i-1];
}
for(i=N-2; i>=0; i--) {
O2[i] = O2[i+1]*A[i+1];
}
for(i=0; i<N; i++) {
O[i] = O1[i]*O2[i];
}
printf("{");
for(i=0; i<N; i++) {
printf("%d, ", A[i]);
}
printf("\b\b}\n");
printf("{");
for(i=0; i<N; i++) {
printf("%d, ", O[i]);
}
printf("\b\b}\n");
}
O1 stores {1, A[0], A[0]A[1], ...., A[0]A[1]..A[N-2]}
O2 stores {A[1]A[2]..A[N-1], A[2]A[3]..A[N-1], ...., 1}
We can't use a DP as you are thinking. The constraint that the two halves should have the same sum is only true the first time we split the array.
Let A be the array s.t. sum(A) = n
Let A1, A2 be the halves s.t. sum(A1) = sum(A2) = n/2
Let A11, A12 be any two halves of A1. It is not necessary for any such A11, A12 that sum(A11) = sum(A12)!
A DP solution might be possible, but certainly not this way!
@m@}{: I'm not sure what you're trying to do, but I think your solution uses 9 bits to store the position of 1 piece, which can be done with just 6 bits. Moreover, your code doesn't compile!
- anotherguy August 29, 2013while(don't know how to phrase question) {
learn how to phrase question;
}
ask question;
while(don't know how to phrase question) {
learn how to phrase question;
}
ask question;
I can't seem to edit my answer. I have a much more elegant solution which uses a maximum of 10 bits, based upon pretonesio's 11 bit solution:
1. If the two pieces are on opposite vertical halves, the first 5 bits should represent the location of the piece in the first half and the next 5 bits should represent the location of the piece in the second half = 10 bits
2. If the pieces are in the same vertical half but in different quarters, use 1 bit to represent which half they are in, the next 4 bits to represent location of piece in upper quarter, next 4 for location of lower quarter piece = 9 bits
3. If they are in the same quarter but in different vertical eighths, use 2 bits to represent which quarter they are in, next 3 bits for location of piece in left eighth and next 3 bits of location of piece in right eighth = 8 bits
4. If they are in the same vertical eighth but in different sixteenth, use 3 bits for the eighth they are in, 2 bits for the piece in upper sixteenth and 2 bits for the piece in lower sixteenth = 7 bits
5. If they are in the same sixteenth but in different vertical thirtysecondths, use 4 bits for the sixteenth and 1 bit each for the location of each piece in respective thirtysecondth = 6 bits
6. If they are in the same thirtysecondth, use 5 bits to represent the location of that thirtysecondth = 5 bits
You can represent 2^n values with n bits.
However, you can represent
2^n + 2^(n-1) + 2^(n-2) + ... 1 = 2^(n+1) - 1
values with *atmost* n bits
So you can represent 2^11 - 1 = 2047 different values using just 10 bits.
Now here's the catch in the problem, as brennahan already mentioned - the order of the pieces doesn't matter.
So there are 64C2 = 2016 possible ways to arrange two pieces on an 8x8 chessboard.
Therefore, it should definitely be possible to represent 2016 ways using 10 bits.
In fact, you can represent 2016 values using all 5, 6, 7, 8, 9 and 10 bit sequences.
Here's one method:
Consider all possible relative positionings:
1. There are 7*8 = 56 possible ways of having two pieces horizontally adjacent = | P | P |
2. There are 8*7 = 56 possible ways of having two pieces vertically adjacent = | P |
-----
| P |
3. There are 7*7 = 49 possible ways of having two pieces like this = | P | |
---------
| | P |
4. There are 7*7 = 49 possible ways of having two pieces like this = | | P |
---------
| P | |
Just keep on repeating this procedure, using all sequences of 5, 6, 7, 8, 9 and 10 bits
You should be able to represent 32 + 64 + 128 + 256 + 512 + 1024 = 2016 ways to arrange the pieces.
Edit: I just wrote a program to automatically assign bit sequences to every possible configuration. There are a lot of them for 8x8 so I'll just show a solution for a 4x4 chessboard(120 configurations) using atmost 6 bits:
-----------------
| P | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
000
-----------------
| | P | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
001
-----------------
| | | P | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
010
-----------------
| | | | |
-----------------
| P | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
011
-----------------
| | | | |
-----------------
| | P | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
100
-----------------
| | | | |
-----------------
| | | P | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
101
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | P | | |
-----------------
| | | | |
-----------------
110
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | P | |
-----------------
| | | | |
-----------------
111
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | P |
-----------------
| | | | |
-----------------
0000
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | P | | |
-----------------
0001
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | P | |
-----------------
0010
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | P |
-----------------
0011
-----------------
| P | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
0100
-----------------
| | P | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
0101
-----------------
| | | | |
-----------------
| P | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
0110
-----------------
| | | | |
-----------------
| | P | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
0111
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | P | |
-----------------
| | | | |
-----------------
1000
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | P |
-----------------
| | | | |
-----------------
1001
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | P | |
-----------------
1010
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | P |
-----------------
1011
-----------------
| P | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
1100
-----------------
| | | | |
-----------------
| P | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
1101
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | P |
-----------------
| | | | |
-----------------
1110
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | P |
-----------------
1111
-----------------
| P | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
00000
-----------------
| | P | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
00001
-----------------
| | | P | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
00010
-----------------
| | | | P |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
00011
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
00100
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
00101
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
00110
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
00111
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| P | | | |
-----------------
01000
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | P | | |
-----------------
01001
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | P | |
-----------------
01010
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | P |
-----------------
01011
-----------------
| P | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
01100
-----------------
| | P | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
01101
-----------------
| | | P | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
01110
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
01111
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
10000
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
10001
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | P | | |
-----------------
10010
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | P | |
-----------------
10011
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | P |
-----------------
10100
-----------------
| | P | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
10101
-----------------
| | | P | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
10110
-----------------
| | | | P |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
10111
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
11000
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
11001
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
11010
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| P | | | |
-----------------
11011
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | P | | |
-----------------
11100
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | P | |
-----------------
11101
-----------------
| P | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
11110
-----------------
| | P | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
11111
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
000000
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
000001
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | P | |
-----------------
000010
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | P |
-----------------
000011
-----------------
| | | P | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
000100
-----------------
| | | | P |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
000101
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
000110
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
000111
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| P | | | |
-----------------
001000
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | P | | |
-----------------
001001
-----------------
| P | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
001010
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
001011
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | P |
-----------------
001100
-----------------
| | | | P |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
001101
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
001110
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| P | | | |
-----------------
001111
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
010000
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
010001
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
010010
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
010011
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
010100
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
010101
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
010110
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
010111
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
011000
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
011001
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
011010
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
011011
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
011100
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
011101
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
011110
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
011111
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
100000
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
100001
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
100010
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
100011
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
100100
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
100101
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
100110
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
100111
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
101000
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
| | | | |
-----------------
101001
-----------------
| | | | |
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
101010
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
101011
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
101100
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
101101
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
| | | | |
-----------------
101110
-----------------
| | | | |
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
101111
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
110000
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
110001
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
110010
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
110011
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
110100
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
110101
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
110110
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
110111
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
111000
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
111001
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | P | |
-----------------
111010
-----------------
| | P | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
111011
-----------------
| | | P | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
111100
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | P | | |
-----------------
111101
-----------------
| P | | | |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| | | | P |
-----------------
111110
-----------------
| | | | P |
-----------------
| | | | |
-----------------
| | | | |
-----------------
| P | | | |
-----------------
111111
My algorithm is correct.
- anotherguy October 26, 2013@Nitin R. Gupta: the sum of{0,3,0,2,5,0,3,5,2,0} is 3+2+5+3+5+2 = 20, not 15.
@jvermette: it handles multiple troughs as well