# Challenge

This challenge is based on the domino effect:

Initially, each domino is located on one straight line and is in a vertical state. It can be dropped either to the left along the same straight line, or to the right. Then this domino will knock down the next one, and that one, perhaps, the other.

The dominoes are each of different heights, and they are located at different distances.

Your task is to find the minimum number of dominoes that need to be knocked down manually.

# Input

• The first line of the input data contains one integer n (1≤n≤1000) — the number of dominoes.

• The second line of the input contains n integers x (1≤x≤10**9) — the coordinates of dominoes. It is sorted!

• The third line of the input data contains n integers h (1≤h<10**9) — the heights of the dominoes.

# Output

• Output one number - the minimum number of dominoes that need to be knocked down manually.

# Tests

Input:
10
10 20 30 40 50 60 70 80 90 100
19 19 8 19 19 19 1 10 20 30

Output: 3

Input:
6
10 20 30 40 50 60
17 9 13 21 7 3

Output: 2

Input:
10
10 20 30 40 50 60 70 80 90 100
15 16 11 17 18 19 1 9 18 30

Output: 2


(Geogebra visualisation. "P" means pass, -> or <- : demolition directions)

# Scoring

This is , so the fastest algorithm scores the most. Here are the points based on your algorithm's complexity:

5 points for O(n!),

25 for O(x^n),

50 for O(n^x) where x≥3,

75 for O(n^x) where 2≤x<3,

80 for O(n*log(n)),

90 for O(n),

100 for O(n^x) where x<1, or O(log^x(n))


The first solution gets a 1.1 coefficient (already expired); a solution with an explanation may get extra points.

# Python 3 + Google OR-Tools, unknown complexity (probably exponential)

Uses a slightly modified set cover formulation.


from ortools.sat.python import cp_model

def min_push(positions, heights):
model = cp_model.CpModel()
push = [{} for _ in positions]
for i, (p, h) in enumerate(zip(positions, heights)):
for d in (-1, 1):
j = i + d
while 0 <= j < len(positions):
if abs(positions[j] - p) > h:
break
push[i][j] = model.NewIntVar(0, 1, f'push_{(i,j)}')
j += d
push_t = [{} for _ in positions]
for i, d in enumerate(push):
for j, v in d.items():
push_t[j][i] = v
for d in push_t:
model.Add(sum(d.values()) <= 1)
for i, d_i in enumerate(push):
for j, v_ij in d_i.items():
for k, v_jk in push[j].items():
if ((j - i) > 0) != ((k - j) > 0):
model.Add(v_ij + v_jk <= 1)
model.Maximize(sum(v for d in push for v in d.values()))
solver = cp_model.CpSolver()
solver.Solve(model)
return int(len(positions) - solver.ObjectiveValue())

• How long does it take to run in practice?
– Simd
Jan 5 at 8:01

# MATLAB

I was trying to rewrite @user1502040's Python 3 + Google OR-Tools Answer in MATLAB.

$$\ \color{red}{\text{But there are some mistakes in my MATLAB code. Any help would be appreciated.}} \$$

clear all;close all;clc;

positions = [10 20 30 40 50 60 70 80 90 100];
heights = [19 19 8 19 19 19 1 10 20 30];
minPushes = min_push(positions, heights);
disp(minPushes);

positions = [10 20 30 40 50 60];
heights = [17 9 13 21 7 3];
minPushes = min_push(positions, heights);
disp(minPushes);

positions = [10 20 30 40 50 60 70 80 90 100];
heights = [15 16 11 17 18 19 1 9 18 30];
minPushes = min_push(positions, heights);
disp(minPushes);

function minPushes = min_push(positions, heights)
% Number of dominoes
numDominoes = length(positions);

% Decision variables: push(i,j) is 1 if domino i pushes domino j, otherwise 0
push = optimvar('push', numDominoes, numDominoes, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);

% Create an optimization problem
problem = optimproblem('ObjectiveSense', 'maximize');

% Constraints for reachable pushes
for i = 1:numDominoes
for j = 1:numDominoes
if i ~= j
% Domino i can push domino j only if it's within reach
distance = abs(positions(j) - positions(i));
if distance <= heights(i)
% Constraint is satisfied implicitly by the definition of push variable
else
% Domino i cannot push domino j because it's out of reach
problem.Constraints.(['outOfReach_' num2str(i) '_' num2str(j)]) = push(i, j) == 0;
end
end
end
end

% Each domino is pushed at most once
for j = 1:numDominoes
problem.Constraints.(['pushOnce_' num2str(j)]) = sum(push(:, j)) <= 1;
end

% Prevent cycles in pushes
for i = 1:numDominoes
for j = 1:numDominoes
if i ~= j
for k = 1:numDominoes
if j ~= k && i ~= k
if ((j - i) > 0) ~= ((k - j) > 0)
problem.Constraints.(['noCycle_' num2str(i) '_' num2str(j) '_' num2str(k)]) = push(i, j) + push(j, k) <= 1;
end
end
end
end
end
end

% Objective: maximize the number of pushes
problem.Objective = sum(sum(push));

% Solve the problem using an integer linear programming solver
options = optimoptions('intlinprog','Display','off');
[sol, fval, exitflag, output] = solve(problem,'Options',options);

% Calculate the minimum number of dominoes that need to be pushed manually
minPushes = numDominoes - fval;
end