Question: https://codility.com/programmers/challenges/oxygenium2014
Question Name: oxygenium2014 or CountBoundedSlices
For this question, I was unable to solve it with a golden answer. Instead, I tried to get two silver solutions. Both of them cheated the grading system to have the detected time complexity O(n), while they do not. I will list them here for later review and possible improvements.
The first one is derived from the brute force method. And it got 90 points. The key of this solution is to return when reach the end of input.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def solution(K, A): min_pos = max_pos = 0 begin = 0 end = 1 count = 0 while begin < len (A): while A[max_pos] - A[min_pos] <= K: while end < len(A) and A[end] <= A[max_pos] and A[end] >= A[min_pos]: end += 1 if end == len(A): count += (end-begin)*(end-begin+1) return min(2000000000, count)/2 if A[end] > A[max_pos]: max_pos = end if A[end] < A[min_pos]: min_pos = end truncated = min(max_pos, min_pos) count += (truncated-begin+1)*(end-begin+end-truncated) if count > 2000000000: return 1000000000 begin = min(max_pos, min_pos) + 1 end = begin + 1 max_pos = min_pos = begin return min(2000000000, count)/2 |
The second one is similar with the official silver solution, get 80 points. It uses the Cartesian tree. Actually, according the article, if we carry further works to implement the range minimum query in a <O(N), O(1)> algorithm, this solution should be able to pass all the test, and be a golden one. But such a <O(N), O(1)> algorithm is too complicated for such a small question. And I am still learning it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | import operator class Cartesian_Tree(): ''' The class the construct the Cartesian Tree ''' class node(object): __slots__ = ('key', 'value', 'right', 'left', 'parent', 'height') def __init__(self, key, value): self.key = key self.value = value # Node's value self.right = None # Right Child self.left = None # Left Child self.parent = None # Parent Node return def __init__(self, compare, content): self.nodes=[self.node(i, content[i]) for i in xrange(len(content))] self.root = self.nodes[0] for index in xrange(1, len(content)): prior = self.nodes[index-1] current = self.nodes[index] while compare(prior.value, current.value): if prior.parent == None: current.left = prior prior.parent = current self.root = current break prior = prior.parent else: current.left = prior.right current.parent = prior if current.left != None: current.left.parent = current prior.right = current return def FindPeak(self, begin, end): if begin >= end: raise LookupError() current = self.root while current.key >= end or current.key < begin: if current.key >= end: current = current.left else: current = current.right return current.key def solution(K, A): def __solutionRec__(start, end, minPos, maxPos): if minPos != -1 and maxPos == -1: truncatedPos = minPos maxPos = max_tree.FindPeak(start, end) elif minPos == -1 and maxPos != -1: truncatedPos = maxPos minPos = min_tree.FindPeak(start, end) else: truncatedPos = len(A) if A[maxPos] - A[minPos] <= K: if end == len(A): return (end-start) * (end-start+1) / 2 else: return (truncatedPos-start+1) * (end-start+end-truncatedPos) / 2 elif minPos < maxPos: if maxPos > truncatedPos and end != len(A): stack.extend([-1, minPos, maxPos, start]) return 0 else: stack.extend([-1, minPos, maxPos, start]) stack.extend([maxPos, -1, end, minPos+1]) return 0 else: if minPos > truncatedPos and end != len(A): stack.extend([maxPos, -1, minPos, start]) return 0 else: stack.extend([maxPos, -1, minPos, start]) stack.extend([-1, minPos, end, maxPos+1]) return 0 min_tree = Cartesian_Tree(operator.ge, A); max_tree = Cartesian_Tree(operator.le, A); count = 0 stack = [max_tree.FindPeak(0, len(A)), min_tree.FindPeak(0, len(A)), len(A), 0] while(len(stack) != 0): count += __solutionRec__(stack.pop(), stack.pop(), stack.pop(), stack.pop()) if count > 1000000000: return 1000000000 return count |
Finally, the official golden solution is here. I tried to improve it as following, but sadly failed. It works a little more quickly for two tests, but worse for another one.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | def solution(K, A): N = len(A) maxINT = 2000000000 maxQ = [0] * (N + 1) posmaxQ = [0] * (N + 1) minQ = [0] * (N + 1) posminQ = [0] * (N + 1) firstMax, lastMax = 0, -1 firstMin, lastMin = 0, -1 i, j, result = 0, 0, 0 while i < N: while j < N: # added new maximum element while (lastMax >= firstMax and maxQ[lastMax] <= A[j]): lastMax -= 1 lastMax += 1 maxQ[lastMax] = A[j] posmaxQ[lastMax] = j # added new minimum element while (lastMin >= firstMin and minQ[lastMin] >= A[j]): lastMin -= 1 lastMin += 1 minQ[lastMin] = A[j] posminQ[lastMin] = j if (maxQ[firstMax] - minQ[firstMin] <= K): j += 1 else: break if posminQ[firstMin] < posmaxQ[firstMax]: result += (j - i + j - posminQ[firstMin]) * (posminQ[firstMin] - i + 1) i = posminQ[firstMin] + 1 firstMin += 1 else: result += (j - i + j - posmaxQ[firstMax]) * (posmaxQ[firstMax] - i + 1) i = posmaxQ[firstMax] + 1 firstMax += 1 if result >= maxINT: return maxINT/2 return result/2 |
Hey Sheng,
About the golden solution – I don’t get when do you increment j?
I can see that you increment it only “if (maxQ[firstMax] – minQ[firstMin] <= K)"
I think there should be an increment also when you increment i.
Otherwise j can stay behind i, for example when the condition is never satisfied…
It is not possible. Consider the time that i catched up with j (i == j), A[i] == A[i]. Therefore, maxQ[firstMax] – minQ[firstMin] = 0 <= K. Then j must be moving ahead. As a result, j can never stay behind.