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.
No unique solution. For me it is the last solution of the permutation matrix.
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.
Sorry, it was a mistake.
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.
Is there any size constraint on this problem ? My solution is not getting accepted ...
Best solution without lookup table
Never thought for-loop can be used for a matrix.
Aww.. ran out of memory.
%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
Increment a number, given its digits
506 Solvers
Project Euler: Problem 2, Sum of even Fibonacci
462 Solvers
Back to basics - mean of corner elements of a matrix
236 Solvers
204 Solvers
546 Solvers