Hey @Niako, awesome puzzle. I get the first 5 tests to pass but tests 6-10 all fail and I can’t for the life of me figure out where the bug is in my algorithm. What is being introduced in test number 6 that isn’t there in tests 1-5?
1 Like
Nothing in particular (tests 1-4 are small images with few columns to remove, the others are “big” images with an increasing number of columns to remove).
Here are the total energy / path indices / corresponding energies (from top to bottom) of the successively removed paths of test 6:
365
[69, 69, 69, 69, 69, 69, 68, 67, 66, 65, 64, 63, 63, 64, 65, 66, 67, 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69]
[0, 23, 10, 23, 7, 15, 6, 2, 7, 2, 10, 4, 3, 1, 1, 4, 2, 2, 0, 1, 1, 0, 1, 1, 19, 50, 32, 24, 19, 5, 1, 27, 24, 19, 7, 12, 0]
539
[68, 68, 68, 68, 68, 68, 68, 67, 68, 67, 68, 68, 67, 66, 65, 65, 66, 67, 68, 67, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 67, 68, 68]
[0, 37, 28, 62, 79, 45, 6, 4, 3, 0, 8, 9, 2, 6, 1, 2, 3, 1, 1, 1, 1, 1, 1, 11, 20, 25, 27, 20, 10, 3, 44, 26, 14, 20, 1, 17, 0]
661
[64, 64, 63, 64, 65, 65, 65, 64, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 43, 43, 42, 41, 41, 40, 39]
[19, 12, 61, 50, 87, 47, 6, 5, 12, 10, 3, 7, 9, 4, 4, 1, 4, 6, 6, 1, 4, 5, 14, 32, 15, 23, 67, 39, 37, 13, 9, 13, 12, 2, 11, 8, 3]
721
[3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 2, 2, 3, 9, 5, 2, 3, 2, 3, 1, 4, 3, 4, 2, 1, 3, 1, 5, 4, 7, 9, 16, 41, 115, 146, 11, 9, 91, 132, 7, 27, 6, 22, 19, 4, 0]
679
[0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 2, 2, 1, 0, 0, 1, 2, 3, 3, 2]
[0, 2, 3, 2, 6, 5, 7, 7, 1, 3, 2, 5, 6, 0, 2, 4, 3, 1, 5, 4, 34, 44, 94, 121, 13, 5, 4, 2, 7, 130, 72, 25, 27, 4, 17, 12, 0]
738
[29, 30, 31, 32, 33, 34, 34, 35, 36, 37, 38, 39, 38, 39, 40, 41, 41, 42, 42, 43, 42, 41, 42, 41, 40, 40, 39, 39, 38, 37, 36, 37, 36, 37, 38, 38, 37]
[23, 51, 36, 40, 34, 24, 27, 169, 25, 43, 14, 5, 5, 2, 3, 3, 2, 0, 0, 0, 4, 3, 24, 36, 24, 9, 4, 38, 6, 25, 4, 6, 13, 13, 17, 6, 0]
739
[11, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 30, 31, 32, 32, 32, 31, 30]
[2, 10, 59, 12, 7, 9, 2, 1, 2, 3, 2, 5, 8, 6, 9, 3, 4, 8, 8, 7, 21, 57, 12, 45, 101, 46, 34, 26, 16, 81, 55, 18, 16, 6, 20, 14, 4]
760
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 2, 3, 3, 2, 2, 1, 0, 0, 0, 0, 1, 2, 3, 2]
[0, 1, 3, 3, 3, 2, 7, 10, 6, 2, 3, 5, 4, 6, 5, 2, 2, 1, 2, 65, 195, 102, 31, 20, 10, 5, 11, 16, 28, 42, 70, 60, 10, 2, 8, 18, 0]
807
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 7, 7, 6, 7, 8, 8, 9, 10]
[0, 0, 2, 2, 3, 3, 6, 12, 3, 2, 1, 5, 4, 1, 1, 1, 4, 2, 5, 58, 272, 10, 45, 11, 20, 6, 11, 24, 6, 5, 20, 3, 82, 25, 34, 117, 1]
829
[43, 43, 43, 44, 45, 45, 44, 44, 43, 43, 42, 42, 43, 42, 41, 40, 39, 38, 37, 36, 36, 36, 36, 37, 38, 37, 36, 35, 34, 35, 35, 35, 35, 35, 36, 37, 37]
[14, 5, 35, 45, 37, 30, 44, 55, 69, 41, 122, 51, 16, 3, 11, 4, 4, 1, 1, 5, 0, 2, 13, 47, 27, 14, 4, 36, 1, 30, 5, 13, 14, 14, 7, 7, 2]
784
[45, 44, 43, 42, 42, 41, 40, 41, 42, 42, 41, 42, 42, 42, 42, 41, 40, 39, 38, 37, 36, 35, 36, 36, 37, 36, 35, 34, 34, 34, 33, 33, 33, 33, 32, 31, 31]
[2, 26, 16, 54, 50, 22, 80, 33, 26, 87, 50, 66, 15, 4, 6, 6, 5, 3, 0, 1, 4, 4, 11, 43, 28, 14, 17, 32, 6, 15, 7, 7, 8, 13, 9, 14, 0]
785
[44, 43, 42, 42, 42, 41, 40, 41, 42, 41, 41, 42, 41, 40, 39, 38, 37, 36, 37, 37, 36, 37, 38, 38, 37, 36, 36, 35, 34, 35, 34, 34, 35, 34, 35, 35, 34]
[6, 31, 9, 33, 32, 47, 34, 34, 49, 84, 50, 67, 37, 8, 4, 5, 3, 1, 1, 0, 5, 5, 15, 39, 18, 25, 3, 41, 11, 22, 9, 9, 16, 19, 7, 4, 2]
841
[2, 2, 2, 3, 4, 5, 6, 7, 6, 7, 8, 9, 9, 10, 11, 12, 13, 12, 13, 12, 12, 12, 11, 11, 11, 11, 11, 10, 9, 8, 7, 6, 6, 7, 7, 8, 9]
[0, 3, 4, 5, 2, 2, 10, 13, 5, 2, 2, 2, 1, 4, 11, 1, 28, 150, 61, 25, 49, 40, 37, 32, 10, 7, 7, 13, 11, 10, 8, 24, 41, 34, 63, 121, 3]
835
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 4, 4, 4, 4, 5, 6, 7, 7, 6, 6, 6, 5, 5]
[0, 1, 2, 2, 2, 3, 12, 12, 1, 0, 2, 4, 6, 0, 1, 0, 4, 1, 5, 88, 205, 47, 44, 42, 28, 10, 1, 22, 11, 7, 19, 19, 21, 12, 139, 58, 4]
846
[42, 41, 40, 39, 40, 41, 42, 43, 44, 44, 45, 45, 45, 44, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 35, 34, 33, 32, 31, 32, 31, 31, 30, 29, 30, 29, 29]
[5, 17, 30, 37, 28, 43, 89, 85, 45, 54, 96, 8, 4, 3, 3, 2, 8, 6, 3, 3, 1, 6, 15, 29, 15, 29, 25, 42, 22, 24, 5, 17, 15, 19, 9, 3, 1]
Make sure to compute the lexicographically-min path from top to bottom.
1 Like
hello,@Niako,it’s a greate puzzle.when I tests I-3,I can’t pass ;there is frist path:0:24 1:24 2:24 3:23 4:23 5:22 6:22 7:21;i can’t get 148 when the thrid times;where i am wrong in the calculation…
by the way,the path is bottom to top
@yinteman Hi, I’m sorry I really don’t get your message. Are you talking about test 4? What is the path you’re talking about (length should be 19, the height of the image)?
Very good puzzle, I learned something cool in the process 
1 Like
Almost the same problem is featured in the week 2 assignment of the free “Algorithms part II by Princeton” course on Coursera (link), although slightly different input/output requirements. Additional insight and tips can be found on that assignment’s specification and faq pages.
I solved CG version first, after that the other one was piece of cake.
2 Likes
Thanks a lot for this puzzle @Niako ! I am Junior Software Engineer in Image Processing and I never heard about this algorithm, always nice to discover new things !
Also there is a kind of typo error in the pre-generated code in Python: in the second for loop i = int(j) while i is also the row iteration value, it can be a bit misleading 
2 Likes
Just solved it, nice puzzle, I like the effect.
At each step I recalculate my whole energy matrix E and my whole lowest_energy matrix L (I use a DP method).
It feels a bit dumb to do so, and your last paragraph hints that there’s a way to go faster than this, so I gave it some thoughts, but there’s something that bothers me.
I get that you can just update energy along the seam, but if you want to delete a cell in each row of E it’ll be O(W) per row with a basic array of arrays so O(W*H) at each step, so indeed it might be a bit faster than just recalculating the whole E but it’s the same complexity.
So the only huge improprement I can imagine is using an array of linked lists instead, for more efficient cell removals.
So let’s say you refactor it like this.
Now comes the real problem: the L matrix.
Cause even with linked lists and trying to update as few values as possible, removing a single cell in the last row will propagate with a kind of triangularish shape in rows above and the area you’d be forced to update will be O(W*H) anyway.
So it feels like even with those optimisations (which would be a bit painful to implement for languages without buidin linked lists), I don’t see how you can beat an O(W*H) complexity each turn.
Am I missing something ?
2 Likes
@pardouin Using these optimizations (some kind of “backpropagation” to update the DP, doubly-linked cells data structure, …) the worst case complexity will indeed be the same (O(W*H), i.e. linear in the size of the image), but it should be more efficient in practice.
2 Likes
I just passed all test cases however I still can’t pass validators number 5,8 and 10.
Can you give me some clarification on this please!
I answered in PM to avoid spoiling here.
1 Like
I just came across this puzzle and wanted to thank you for it! It was really nice discovering that cool algorithm and I think you ‘shaped’ the rules perfectly so that it’s quite fast to implement without loosing any interesting part.
Hope you ll submit another image processing puzzle 
2 Likes
I know that it would be quite the task, but @Niako , would you consider making another level 2 of this that would require more optimization (such as caching, as you allude to in the problem statement)? I could perhaps make it if you don’t want to because it would be too much effort?
I think that it would be natural to be concerned about that being too small of a change for an entirely new puzzle, so perhaps a 3-channel version of this problem could be possible with much larger images to force some caching?
Any feedback (not just from the creator) would be appreciated!
1 Like
Thanks for your feedback. The purpose of this puzzle was to provide a simple enough introduction to the algorithm (and not the technical aspects) behind seam carving. From there, anybody is free to go further and implement the technique in both directions on RGB images, experiment with energy functions…
Going further with a sequel on CG though would not necessarily be very interesting as it would still be the same algorithm at the heart of the puzzle. Furthermore it would require much larger images, while inputs are limited to 10000 chars. To circumvent that limitation, we usually provide a RNG formula in the statement, a seed as input and ask the player to generate the data. But using seam carving on random images would be very artificial.
Hello @Niako,
Thank you for your interesting puzzle, I could be interested by your answer to @katiia’s message. I face the same difficulty as I pass all test cases but not the validators number 5, 8 and 10.
Would you please have a suggestion or a description of these validators?
I replied in PM.
I implemented a dfs with memo instead of dp. It failed at test case 7, 10 and validator 7 because of time out. Would you give some advices for reducing the time cost?
My C code of dfs:
void dfs(int x,int y,int energy){
if(energy>f[x][y]||energy>min_e)return;
f[x][y]=energy;
if(x==n){ // if on last row of image
if(f[x][y]<min_e){
// update the known lowest energy solution
min_e=f[x][y];
for(int i=1;i<=n;++i){
min_e_y_route[i]=y_route[i];
}
}
return;
}
for(int j=y-1;j<=y+1;++j)if(j>=1&&j<=m){
y_route[x+1]=j; // record the route of dfs
dfs(x+1,j,energy+E(x+1,j));
}
}
terrible puzzle.