fork download
copy 
  1.  
  2. def get_intersection(rect1, rect2):
  3.     y1, x1, y2, x2 = rect1
  4.     y3, x3, y4, x4 = rect2
  5.     return (
  6.         max(0, 1 + min(x4, x2) - max(x1, x3)) *
  7.         max(0, 1 + min(y4, y2) - max(y1, y3))
  8.     )
  9.  
  10. def solve_stupid(N, M, R, C, parks):
  11.     min_trees = None
  12.     best_pos = None
  13.     for r in xrange(1, N - R + 2):
  14.         for c in xrange(1, M - C + 2):
  15.             trees = 0
  16.             for park in parks:
  17.                 trees += get_intersection((r, c, r + R - 1, c + C - 1), park)
  18.             if min_trees is None or min_trees > trees:
  19.                 min_trees = trees
  20.                 best_pos = (r, c)
  21.     return min_trees, best_pos
  22.  
  23.  
  24.  
  25. def get_interesting(a1, a2, l, total):
  26.     # growing starts at pos such that pos + l == a1
  27.     grow_start = max(1, a1 - l)
  28.     # growing stops at pos = a1
  29.     grow_stop = a1
  30.  
  31.     # falling starts at pos such that pos + l - 1 = a2
  32.     fall_start = max(1, a2 - l + 1)
  33.     # falling stops at pos right after a2: pos = a2 + 1
  34.     fall_stop = a2 + 1
  35.  
  36.     # squeeze coordinates that don't fit
  37.     grow_start = min(grow_start, total)
  38.     grow_stop = min(grow_stop, total)
  39.     fall_start = min(fall_start, total)
  40.     fall_stop = min(fall_stop, total)
  41.  
  42.     return grow_start, grow_stop, fall_start, fall_stop
  43.  
  44. def solve_smart(N, M, R, C, parks):
  45.     interesting_rows = set([1])
  46.     interesting_cols = set([1])
  47.  
  48.     for park in parks:
  49.         r1, c1, r2, c2 = park
  50.         interesting_rows.update(get_interesting(r1, r2, R, N - R + 1))
  51.         interesting_cols.update(get_interesting(c1, c2, C, M - C + 1))
  52.  
  53.     rows = sorted(interesting_rows)
  54.     cols = sorted(interesting_cols)
  55.  
  56.     col_to_index = {col: i for i, col in enumerate(cols)}
  57.  
  58.     min_trees = None
  59.     best_pos = None
  60.     for r in rows:
  61.         deriv_changes = [0] * len(cols)
  62.         for park in parks:
  63.             r1, c1, r2, c2 = park
  64.             gstart, gstop, fstart, fstop = get_interesting(c1, c2, C, M - C + 1)
  65.             park_height = get_intersection(
  66.                 (r, c1, r + R - 1, c1),
  67.                 park
  68.             )
  69.             deriv_changes[col_to_index[gstart]] += park_height
  70.             deriv_changes[col_to_index[gstop]] -= park_height
  71.             deriv_changes[col_to_index[fstart]] -= park_height
  72.             deriv_changes[col_to_index[fstop]] += park_height
  73.  
  74.         # now we know how derivative changes and we need
  75.         # initial value to start with
  76.         trees = 0
  77.         first_col = cols[0]
  78.         for park in parks:
  79.             trees += get_intersection(
  80.                 park,
  81.                 (r, first_col, r + R - 1, first_col + C - 1)
  82.             )
  83.  
  84.         if min_trees is None or min_trees > trees:
  85.             min_trees = trees
  86.             best_pos = (r, first_col)
  87.  
  88.         derivative = 0
  89.         for i, col in enumerate(cols[:-1]):
  90.             derivative += deriv_changes[i]
  91.             next_col = cols[i + 1]
  92.             trees += (next_col - col) * derivative
  93.             if trees < min_trees:
  94.                 min_trees = trees
  95.                 best_pos = (r, next_col)
  96.  
  97.     return min_trees,  best_pos
  98.  
  99.  
  100. solve = solve_smart
  101.  
  102. print solve_smart(5, 3, 2, 2, [
  103.     (2, 2, 2, 2),
  104.     (4, 2, 4, 2),
  105. ])
  106.  
  107. print solve_smart(5, 5, 3, 2, [
  108.     (1, 1, 1, 5),
  109.     (2, 1, 5, 1),
  110.     (5, 2, 5, 5),
  111.     (2, 5, 4, 5),
  112.     (3, 3, 3, 4),
  113. ])
  114.  
  115.  
  116. N = 100
  117. M = 100
  118. K = 50
  119.  
  120. import random
  121.  
  122. for R in xrange(1, N + 1):
  123.     C = R
  124.     parks = []
  125.     for i in xrange(K):
  126.         while True:
  127.             r1 = random.randrange(1, N + 1)
  128.             c1 = random.randrange(1, M + 1)
  129.             r2 = random.randrange(r1, N + 1)
  130.             c2 = random.randrange(c1, M + 1)
  131.             new_park = (r1, c1, r2, c2)
  132.             for park in parks:
  133.                 if get_intersection(new_park, park):
  134.                     break
  135.             else:
  136.                 parks.append(new_park)
  137.                 break
  138.  
  139.     smart = solve_smart(N, M, R, C, parks)
  140.     stupid = solve_stupid(N, M, R, C, parks)
  141.     if smart != stupid:
  142.         print "FAIL"
  143.         print smart
  144.         print stupid
  145.         print parks
  146.         print N, M, R, C
  147.         raise SystemExit
Time limit exceeded #stdin #stdout 5s 11496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b17P6I
language:
Python (cpython 2.7.16)
created:
8 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!