Problem 534. Find best domino orientation

Created by Doug Hull

Solve Later

Given a list of pairs, find the orientation they should be placed in a line, such that the sum of the absolute values of the differences is zero.

Zero means do not invert, One means invert in the order vector.

list = [1 2
        4 2
        2 3

order = [0 1 1]

yields: [1 2][2 4][3 2]
    or: abs(2-2) + abs(4-3)
    or:        0 + 1
    or: 1

There is a unique solution to this problem where the final score is minimized.

Solve

Solution Stats

599 Solutions
172 Solvers

Last Solution submitted on May 05, 2020

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Jean-Marie Sainthillier on 6 Aug 2012

No unique solution. For me it is the last solution of the permutation matrix.

Doug Hull on 7 Aug 2012

For which test statement is there not a unique solution? We need to fix the test suite if there are two answers of same score.

Jean-Marie Sainthillier on 7 Aug 2012

Sorry, it was a mistake.

Andrew Newell on 9 Jan 2015

The statement of the problem is incorrect: "the sum of the absolute values of the differences is zero." You want the smallest sum, but it isn't necessarily zero.

Raihan Ahmed on 6 Jan 2016

Is there any size constraint on this problem ? My solution is not getting accepted ...

Solution Comments

Solution 550812

2 Comments

2 Comments

Jon on 30 Dec 2014

Best solution without lookup table

Ramoflaple on 7 Jul 2015

Never thought for-loop can be used for a matrix.

Solution 73793

2 Comments

2 Comments

Albert Yam on 10 Apr 2012

Aww.. ran out of memory.

Albert Yam on 10 Apr 2012

%the part of the code i cut out, should work in theory ..

fliplist = fliplr(list);
idx = triu(ones(length(list)),0);
for j = 1:length(idx)
idx2 = unique(perms(idx(j,:)),'rows');
[a b] = size(idx2);
for i = 1 : a
idxi = boolean(idx2(i,:)');
list2 = list;
list2(idxi,:) = fliplist(idxi,:);
list2 = list2';
list2 = list2(:);
dlist = abs(diff(list2));
val2 = sum(dlist(2:2:end));
if val2 < val
val = val2;
orientation = idxi';
end
if val == 0
return
end
end
end

Problem Recent Solvers172

Problem Tags

contest

Problem 534. Find best domino orientation

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers172

Suggested Problems

More from this Author52

Problem Tags

Problem 534. Find best domino orientation

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers172

Suggested Problems

More from this Author52

Problem Tags

Players