0
\$\begingroup\$

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

(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.

\$\endgroup\$
3

2 Answers 2

1
\$\begingroup\$

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())
\$\endgroup\$
1
  • \$\begingroup\$ How long does it take to run in practice? \$\endgroup\$
    – Simd
    Commented Jan 5 at 8:01
0
\$\begingroup\$

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
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.