fork download 
  1. import math
  2. # build sparse table, O(n*log(n))
  3. def build_table(A):
  4.     n = len(A)
  5.     mi = [[0 for j in range(int(math.log(n,2)) + 1)] for i in range(n)]
  6.     mx = [[0 for j in range(int(math.log(n,2)) + 1)] for i in range(n)]
  7.     for i in range(n):
  8.         mi[i][0] = i
  9.         mx[i][0] = i
  10.     j = 1
  11.     while 2 ** j <= n:
  12.         i = 0
  13.         while i + 2 ** j - 1 < n:
  14.             if A[mi[i][j - 1]] < A[mi[i + 2 ** (j - 1)][j - 1]]:
  15.                 mi[i][j] = mi[i][j-1]
  16.             else:
  17.                 mi[i][j] = mi[i + 2 ** (j - 1)][j - 1]
  18.             if A[mx[i][j - 1]] > A[mx[i + 2 ** (j - 1)][j - 1]]:
  19.                 mx[i][j] = mx[i][j-1]
  20.             else:
  21.                 mx[i][j] = mx[i + 2 ** (j - 1)][j - 1]
  22.             i += 1
  23.         j += 1
  24.     return (mi, mx)
  25.  
  26. # min, max query in range[i, j]. O(1)
  27. def RMQ(A, i, j, mi, mx):
  28.     k = int(math.floor(math.log(j - i + 1, 2)))
  29.     miq = min(A[mi[i][k]], A[mi[j - 2 ** k + 1][k]])
  30.     mxq = max(A[mx[i][k]], A[mx[j - 2 ** k + 1][k]])
  31.     return miq, mxq
  32.  
  33. # sliding window algorithm. O(n)
  34. def remove_min(A):
  35.     if len(A) <= 1: return 0
  36.     mi, mx = build_table(A)
  37.     i = 0
  38.     j = 0
  39.     max_length = 0
  40.     while j < len(A):
  41.         miq, mxq = RMQ(A, i, j, mi, mx)
  42.         if miq * 2 > mxq:
  43.             max_length = max(max_length, j - i + 1)
  44.             j += 1
  45.         else:
  46.             i += 1
  47.     return len(A) - max_length
  48.  
  49. if __name__ == '__main__':
  50.     print remove_min([4, 5, 100, 9, 10, 11, 12, 15, 200])
  51.     print remove_min([4, 7, 5, 6])
  52.     print remove_min([20, 7, 5, 6])
  53.     print remove_min([20, 4, 1, 3])
  54.     print remove_min([4, 5, 100, 9, 10, 11, 12, 15, 101,102,103,104,105,106,107,108,109,110,111,112])
Success #stdin #stdout 0.01s 7896KB
comments (?)
stdin 
Standard input is empty
stdout 
4
0
1
3
8
https://ideone.com/NaZX87
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!