[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!:cookie:

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%.
:confused:


#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::cookie::cookie::cookie::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 :wink: :cookie:


#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