[Community Puzzle] Bank Robbers

#21

I solved this puzzle and get green for all testcases, but when I submit it I only get a 50% score? How is this possible?

#23

I think this puzzle has validator issues. The tests are weaker than the validators, so that a wrong code will pass them all and get stuck on the validation, leaving the coder with no clue about what is wrong with their algorithm.

To offset the punishing effect of these validators, I’ll give a few clues about what is expected.

An example that might help understand the problem:

Let’s say we have just 3 robbers (Andy, Bob and Carl) and 10 vaults numbered 1 to 10
All vaults have very simple codes that take one minute to break, except vault 4 that takes 2 minutes and vault 6 that takes 29 minutes.
At first Andy, Bob and Carl work on locks 1 to 3 and take one minute each to crack them.
Then Andy gets to work on lock 4, Bob on lock 5 and Carl on lock 6. Andy will get stuck for 2 minutes, Carl for nearly half an hour. In the mean time, Bob will have time to crack two locks. Then Andy and Bob will get asigned vaults in quick succession until none remains to be cracked. Both will twiddle their thumbs until Carl finally breaks vault 6’s lock.

Each time a lock gets cracked, the thief that is done with it gets reallocated to a new vault (if any remains to be cracked). The rules for reallocation are clearly stated in the problem definition.
Each thief will spend a total time equal to the sum of the time needed to crack each vault that was assigned to him. The final time is simply the max of the times spent by each thief when the last lock is cracked.

Here is some pseudo-code that might help get an idea of the solution.
There are other ways to look at the problem, this is just the simplest to explain I could think of.

Each thief is assigned a cumulated time counter, initially zero.
Each thief begins with no vault assigned to him.

• while not all vaults are cracked
• if there are still vaults available (not cracked yet and with no thief working on them)
• look for an available thief (his cumulated time will be the shortest)
• reassign the thief to a new vault and increase his cumulated time by that of the new vault
• count one more cracked vault
• final time is the longest cumulated time.

In the example:

``````All thieves initially available
Andy -> vault 1, time 0:01, Bob & Carl available
Bob -> vault 2, time 0:01, Carl available
Carl -> vault 3, time 0:01, Andy, Bob & Carl available
Andy -> vault 4, time 0:03, Bob & Carl available
Bob -> vault 5, time 0:02, Carl available
Carl -> vault 6, time 0:30, Bob available
Bob -> vault 7, time 0:03, Andy & Bob available
Andy -> vault 8 time 0:04, Bob available
Bob -> vault 9, time 0:04, Andy & Bob available
Andy -> vault 10, time 0:05, no more vaults to crack
final time : max (0:05, 0:04, 0:30) = 30 minutes.``````

#24

feel free to suggest modifications in the IDE tests.

#25

For one thing, out of the 4 tests only the last one exercises the code in any meaningful way.

As it turns out, it’s the first robber who spends the most time and holds the final result.
There are no cases of more than one thief being available at the same time except during initial vault attribution.

All these are potential pitfalls for awkward code. At the very least you should have more than one “big heist” test, and possibly carefully thought out values to make sure vault attribution works as intended.
If anything else fails, swapping the validatoirs with the tests could do the trick.

#27

ok this is my code well the evaluation. befor that i looped through all vaults to calculate the time needed for each vailt. the values are stored in a list called vaults

so from there I do

``````          //loop through all robbers the first round to give them all a vault
for (var j = 0; j < R; ++j) {
int vaultTime = vaults.removeAt(0);
robbers[j] = robbers[j] + vaultTime;
stderr.writeln('robbers[\$j]  \${robbers[j]}');
}
robbers.sort();//sort for follow up vault
//while robber with lowest time is lower than robber with secondlowest time
while(robbers[0]<robbers[1] && vaults.isNotEmpty){
int vaultTime = vaults.removeAt(0);
//add vault time to robber
robbers[0] = robbers[0] + vaultTime;
stderr.writeln('1robbers  \${robbers} adding \$vaultTime');
//sort robbers to see who is free next
if(robbers[0]>robbers[1]){
robbers.sort();
}
}
total = robbers.reduce(max);//(takes biggest value)
``````

my output is

``````vaults [125000, 156250, 50000, 6250000, 125, 5000, 781250, 5000, 500000, 5000000, 62500, 25000, 50000, 78125, 78125, 6250000, 15625, 500000, 500, 2500]

loop through robers
//first round
robers[0] 125000
robers[1] 156250
robers[2] 50000
robers[3] 6250000
robers[4] 125
//follow up
1robers [5125, 50000, 125000, 156250, 6250000] added 5000
1robers [786375, 50000, 125000, 156250, 6250000] added 781250
1robers [55000, 125000, 156250, 786375, 6250000] added 5000
1robers [555000, 125000, 156250, 786375, 6250000] added 500000
1robers [5125000, 156250, 555000, 786375, 6250000] added 5000000
1robers [218750, 555000, 786375, 5125000, 6250000] added 62500
1robers [243750, 555000, 786375, 5125000, 6250000] added 25000
1robers [293750, 555000, 786375, 5125000, 6250000] added 50000
1robers [371875, 555000, 786375, 5125000, 6250000] added 78125
1robers [450000, 555000, 786375, 5125000, 6250000] added 78125
1robers [6700000, 555000, 786375, 5125000, 6250000] added 6250000
1robers [570625, 786375, 5125000, 6250000, 6700000] added 15625
1robers [1070625, 786375, 5125000, 6250000, 6700000] added 500000
1robers [786875, 1070625, 5125000, 6250000, 6700000] added 500
1robers [789375, 1070625, 5125000, 6250000, 6700000] added 2500
6700000
``````

any guess where i am going wrong?

#28

…? Dafuq?

My initial robber array looks like this:

`125:10000:125000:156250:6250000:`

Note the “10000” instead of your “50000”…

You’re talking about test case 04 “Big Heist” correct?

And I get different vault values in some places, too. I notice a factor 5 difference for two vaults that I have as “1000” and “100000”…
Can you double check your input routine?

#29

hmm thank you!

I fixed a bug where I worked with C as the length of letters… should have been C-N …

well at least I thought that was the problem… now im passing 100% of the tests in the browser. but once submitted i only reach 50%.

#30

I just solved it today (or yesterday since it just passed midnight), and my guess is that since you pass the test cases your algorithm is probably correct, cause the last test would probably make you fail otherwise. So, a hint is to think about avoiding timeout and optimize how you step through the “work” each robber does on the vault.

#31

found the bug
removed the whole “robbers[0]>robbers[1]” thing since i sort the first is always the lowest ^^ thanks. 100% <3

cookies for everyone:cookie: 1UP

#32

thanks and congrats! that was just my thought: maybe optimise speed. then i found a unneeded <
maybe it would have worked with a <= but without even better

#36

I got stuck at last test case. Got “6473750” instead “6515625”
Does any one have any idea?
My code

const R = parseInt(readline());
const V = parseInt(readline());
let combinations = []
for (let i = 0; i < V; i++) {
var inputs = readline().split(’ ');
const C = parseInt(inputs[0]);
const N = parseInt(inputs[1]);
let combine = calcCombination(C, N)
combinations.push(combine)
}

function calcCombination(c, n) {
let d = c - n
return Math.pow(10, n) * Math.pow(5, d)
}

// Write an action using console.log()
// To debug: console.error(‘Debug messages…’);

combinations = combinations.sort((a, b) => a - b)

let time = 0

for (let i = 0; i < combinations.length; i++) {
let combine = combinations[i]
time += combine
for (let j = 0; j < R; j++) {
if (combinations[i+j]) {
combinations[i+j] -= combine
}
}
}

console.log(time);

#37

Thank you, ends up I was being a helluva lot more efficient’n what the prompt was asking for, so my robbers were much faster’n the validator’s dumb robbers LuL

#38

It’s simple. One robber must try all 500,000 combinations to his repository and spend 500,000 seconds on this. The second robber hacks the vault for 1000 combinations and spends 1000 seconds on it. And he should proceed to the next repository, and not wait until the first robber tries all 500,000 combinations. In short, the number of vaults per robber not the same. One can hack one vault for 500,000 seconds, and the second during this time can hack 500 vaults for 1000 seconds each

#39

I pass all of the cases, but when it validates, for some reason it won’t accept my last two cases (#3 and #4). I’m using C#. I’ve edited out all of my Console.Error.WriteLine comments, in case that messes it up. Any ideas? I really don’t want to determine an entirely different way to solve the same problem.

Thanks!

#40

I have the same issue. I wrote mine in C# (which I’m getting to know slowly) and I pass all the test cases, but when I submit it’s only passing the first two and not the last two.

#41

Your comment have just opened my mind in 3 seconds
thank you