https://www.codingame.com/training/easy/robbery-optimisation
Send your feedback or ask for help here!
Created by @Potemkine,validated by @JBM,@Niako and @Alain-Delpuch.
If you have any issues, feel free to ping them.
1 Like
Hello amigos.
I fail the 50, 75 and 100 tests in this one. Any tips about the flaws in my alogorythm?
You’re probably using an exponential-class algorithm. That’d pass 20 and smaller.
2 Likes
I don’t think so, since I don’t even know what that is.
What I do is making two arrays. One with the house value as value and the house number as key.
I then create a second array that has true as value and the house number as a key.
Then, I find the biggest house value and :
- add it to the thief total
- turn the value to 0
- turn the house in the second array to false
- turn the house to the right to false in the second array (if it exists)
- turn the house to the left to false in the second array (if it exists)
For the 8 houses cases, I had to check if the last biggest house value wasn’t bigger than the sum of the values of the house to the left and right.
I believe the 50,75 and 100 may have a trick that looks like that. Any clue?
1 Like
I even fail at 20 houses and above it…
What I do is put index key for every houses then sorting it by first element (for values content).
sorted by first element
[ [ 12, 13 ], [ 11, 12 ], [ 10, 2 ], [ 10, 17 ], [ 9, 19 ], [ 9, 15 ], [ 8, 5 ], [ 7, 18 ], [ 7, 10 ], [ 7, 9 ], [ 6, 11 ], [ 6, 8 ], [ 6, 16 ], [ 5, 1 ], [ 5, 14 ], [ 5, 6 ], [ 4, 4 ], [ 2, 7 ], [ 2, 3 ], [ 2, 0 ] ]
filter by second element which not a side by side
[ [ 12, 13 ], [ 10, 2 ], [ 10, 17 ], [ 9, 19 ], [ 9, 15 ], [ 8, 5 ], [ 7, 10 ], [ 6, 8 ], [ 2, 0 ] ]
what i found is 73 but should expected 75.
Well then, it seems like you’re using a slightly evolved greedy algorithm. But are you sure it should work?
Let’s consider the simple greedy (just take the best available).
It works for this: 1 0 1 — take the outside houses and you get the best solution 2.
It fails for this: 2 3 2 — take the best (middle) house of 3 and fail to get the best solution of 4.
IIUC your trick is [some variation of] avoiding the situation above by considering blocks of three.
But that’s still complicated by cases such as this: 3 4 3 4 3 — which blocks should be considered? Can it generalize?
So, in a nutshell… I think your algorithm may be incorrect.
2 Likes
If it helps convince you one exists (or debug your algorithm), here’s one selection on the 20-house test case that yields a total value of 75:
- (0,2)
- (2,10)
- (5,8)
- (7,2)
- (9,7)
- (11,6)
- (13,12)
- (15,9)
- (17,10)
- (19,9)
Hi there. This is not an easy puzzle, please at least move it to medium. New players coming into this will be disgusted, it requires some skills to figure it out.
8 Likes
The puzzle is in “medium” now.
4 Likes
Actually right now it seems to be back to easy!?
I’ve also noticed that the difficulty of some problems seems arbitrarily modified after validation (e.g. this one or this one which were both validated as hard and are now medium). Is there a rational explanation or are some people arbitrarily doing that without ever notifying it in the comments/forums?
I wish we’d get back to a simple “it’s as easy as how many people solved it”
I am confused by test case 06 (Don´t just alternate houses).
The houses are listed as
a 5
b 1
c 15
d 10
e 13
f 16
The solution given is 31, which is 5 + 10 + 16 (houses a, d & f).
But if the robber robs houses a, c & f he gets 5 + 15 + 16 = 36.
Am I missing something?
Thanks,
5 is not a house, just the nomber of house so it’s :
a 1
b 15
c 10
d 13
e 16
And in fact b + e = 31
1 Like
It’s quite possible that people just move it around.
Or maybe… Maybe when someone else has had the puzzle open to edit something else and meanwhile someone (e.g. eulersche) moved the puzzle to medium and the first one saved his changes, they overwrote the difficulty change.
And there is the failure, right between the keyboard and the chair. Thanks!
@Fluttershy AFAIK the server refuses to update the statement if your modifications are not based on the latest revision number. So that should not be incidental.
Hi there.
I started this puzzle while it was still on easy.
It seems it does not take into account my modification and that the puzzle is still in the “easy suggestions” for me.
@PatrickHectorPatrick As I said above, right now the puzzle is back to easy, most probably because somebody moved it back there without notifying anyone about it.
What? Is that possible? Can we crush his soul?
Who cares what category it’s in?
The only sensible linear indication of difficulty is the number of people who solved it. Period.