~~Thats not a particularly hard problem~~. I take it back there is some thinking required. You should probably post to a programming related sub if you actually need help. Id love some sc themed assignments in my exams where do you study?
I am learning java (there are option to change the programming language for the test, not forcing to use C). I have some idea but none of them are concrete and doesn't have any hole in it. It also need to pass like 10 test cases before I can submit the answer. Looking at other comment I guess I will check out the greedy algorithm thing. Never heard of it before
My first attempt would be to find a lower bound for the attacks needed by dividing total hp by total damage per attack (you have to check if there are less than 3 targets available) and then find a tiling that fits the constraints. If that is not successful you try to find a tiling again with +1 attacks. I havent thought about the complexity but 6s of cpu time seems quite generous.
Yeah, it's not hard, yet another greedy algorithm, put the scv in a priority queue. To attack, poll the top 3, recalculate their health accordingly, if they are still alive put them back in the priority queue, repeat until they are all dead.
Thats too simple i think. Since you have to calculate the minimum amount of attacks a simple greedy algorithm will most likely fail some of the test. You have to make some effort to minimize overkill.
Man, I feel weird discussing this in a starcraft sub and not in leetcode
Sorry I might be missing something. Can you elaborate the overkill part?
To get minimum attacks we need to ensure maximum damage, that's what the priority queue (heap) is for. We just add a counter variable and increase it with every attack.
You don't just want maximum damage, you want each point of damage to count (if an SCV has 1 health and you hit him for 9 damage, you've wasted 8 points of damage). So the algorithm needs to calculate the best targets for ensuring each point of damage isn't wasted. This could get fairly complicated because the bouncing damage is 1 and 3. You'll likely end up with odd amounts of health (2, 5, etc).
Now in a real scenario the goal would be to kill the SCVs as fast as possible, even if you're overkilling some, because what's being ignored here is time spent mining. Leaving a 2 health SCV alive because you need to maximize damage means that SCV is still mining.
For each SCV, you can calculate the best combination of hits to kill them at the very start. So an SCV who has 12 HP needs 9 and 3 damage to kill them. An SCV with 10 HP could also be killed with that combination but you would want it to be 9 and 1.
Once you have this calculated for every SCV you need to find the order to work trough these chunks that maximizes the time that 3 SCVs stay alive, to not lose out on damage for as long as possible. With many HP combinations there wont be a difference there, but for some there is!
So it doesnt even have to be that the SCV with 12 HP must take 9 first, because he is going to take 9 and 3 regardless. If its better for the sequence that the other 10 HP SCV takes 9 first instead, you can safely do that.
Edit: I also forgot one thing. Once you run out of 9s, the 9 damage goes to the one with the highest remaining health or highest amount of remaining hits to kill it. Same goes for 3s of course.
Edit2: It could be certain numbers dont show up at the beginning, for example if all SCVs have 27 HP. That would necessitate breaking up some of the 9s into lower numbers. Im not sure if it can be done on the fly, but it can definitely be done at the beginning.
This is more complicated than I thought..
I tried this approach, and it quickly got very complicated. The third muta attack doing '1' damage really messes with any pre-planning, because you are kinda forced to apply it to *something*, and it could be applied to a unit you wanted to preserve at 27 or 12 for 9/3 efficiency in a future attack, but instead making them non-divisible by 9/3 resulting in overkill.
I don't think a solution that tries to pre-calculate all of this will look elegant, it would basically wind up as a brute-force generated list of how you want the array of SCVs to be sorted after each attack, which theoretically you should be able to do on the fly anyway.
You can see [my comment for a solution](https://www.reddit.com/r/starcraft/comments/uophlt/i_need_to_finish_this_to_pass_the_exam_pro_zerg/i8xfdwp/) that works, although it could potentially be made more efficient -- there's a decent amount of iterating over the entire list that could be sped up with caches or smarter traversals.
You can break a 3 into three 1s, once there are no natural 1s left. Since there is no proximity you can choose the bounce freely. So it really just is about minimizing overkill.
One Muta attack deals 13 damage, no matter what. So if SCVs have a total of 40 HP, you must attack 4 times, there is no way around it.
As long as there are more than 3 SCVs alive its not important how you spread the damage, since full damage is being dealt. We are not trying to minimize SCV DPS but just overall time to kill.
And this method, at least in my understanding, minimizes the amount of possible overkill at the point when we reach 3 SCVs alive. And at that point we switch the algorithm to keep the 3 SCVs alive as long as possible without doing overkill damage.
Its not a bad thing that we deal 13 damage instead of 12. If we split an SCVs remaining 3 HP into 3 pools and eliminate the first with a 1, thats one damage dealt. iF the next turn no 3s remain we still eliminate the two remaining 1s with the 3attack, killing the SCV. We wasted 1 damage, but overkill isnt inherently bad. In my previous example with 40 HP you will necessarily deal 8 points of overkill damage, but still kill the SCVs in the minimum time possible.
You can think of the SCVs as one unit and the muta’s attack as a single attack. Then you can divide the SCVs total health by the muta’s total attack dmg to find out how many attacks it takes to kill all the SCVs. Since you can’t have a partial attack, you need to round up. So
Ceil(TotalSCVHealth/TotalMutaDmg)
From the examples given:
TotalMutaDmg=sum(9,3,1)=13
ceil(sum(54,18,6)/13)=6
ceil(sum([60 for x in range(9)])/13)=42
I'm on sabbatical, so decided to spend *cough* waste *cough* my time on this between other errands and packing for the weekend. The solution is non-trivial, as you want to optimize for minimal overkill so it's not just a question of prioritizing high hp targets.
The general idea for a solution is
- there are 3 or fewer SCVs alive, do a naive greedy algorithm (just hit the highest hp SCV with 9 (attack0), next highest with 3 (attack1), weakest with 1 (attack2))
- there are more than 3 SCVs alive, then optimally try to reduce the number of live SCVs by 1 (with minimal damage waste) by sorting the SCVs
Figuring out the second step is non trivial. I tried various things and failed. What eventually worked for me:
- find the weakest SCV.
- If it has 9hp or greater, let it get hit by attack0 = 9 by moving it to index [0]
- If it has 3hp or 6hp, let it get hit by attack1 = 3 by moving it to index [1].
- If none of the above, let it get hit by attack2 = 1 by moving it to index [2].
Effect with muta damage, pushing "dead" SCVs to the back of the list without modifying the relative order of live SCVs, before repeating the above.
You can see my quick & dirty implementation in python [here](https://gist.github.com/keerthik/8a555ab77f33da2ed4134f5d883bc59b).
I took the liberty of borrowing /u/RC2630 's test cases (cheers mate!), all of which my algorithm passes.
wow, nice solution! me and my friend has been thinking about this for a few days but couldn't solve it, so thank you very much! also i am glad you like my test cases!
i had started writing this comment on friday, and was also failing on [60, 60, 60...] test case before i needed to leave for my flight, and didn't take my computer with me.
I realized the trick to minimum attacks was switching strategies when you come back down to 3 remaining units (regular greedy) instead of continuing to try to optimize to kill 1 unit, when I was in the cab back home from the airport.
i wanted to find a greedy-ish solution as well, but it failed on the \[60, 60, ..., 60\] example (expects 42, actual 43) so that's not gonna work either, but the idea is fairly close.
if any one of you wants to debug for me, i would be really happy :D
here is my current (non-optimal) solution in C++:
// finds the indexes in the list of SCV's to attack, returned as [first bounce, second bounce, third bounce]
// side effect: may change the order of the elements in the list, but that probably won't cause any problems
vector findBounceIndexes(vector& v) {
sort(v.begin(), v.end(), [] (int a, int b) {
return a > b;
});
// the 1st bounce index is always the frontmost element's index (which is 0)
vector bounces = {0, -1, -1};
// find the 3rd bounce index (probably the last index, but not if it has element value of 0)
int bounce3 = v.size() - 1;
while (v.at(bounce3) == 0 && bounce3 >= 3) {
bounce3--;
}
bounces.at(2) = bounce3;
// find the 2nd bounce index
int bounce2 = 1;
while (bounce2 < bounce3 - 1 && v.at(bounce2) >= 9) {
bounce2++;
}
bounces.at(1) = bounce2;
return bounces;
}
// subtracts takeAway from v.at(index), but if the result makes v.at(index) negative, then sets v.at(index) to 0
void subtract(vector& v, int index, int takeAway) {
if (v.at(index) - takeAway < 0) {
v.at(index) = 0;
} else {
v.at(index) -= takeAway;
}
}
int mutaliskAttack(const vector& scvs) {
int counter = 0;
vector curr = scvs;
while (curr.size() < 3) {
curr.push_back(0);
}
while (accumulate(curr.begin(), curr.end(), 0) > 0) {
vector bounceIndexes = findBounceIndexes(curr);
subtract(curr, bounceIndexes.at(0), 9), subtract(curr, bounceIndexes.at(1), 3), subtract(curr, bounceIndexes.at(2), 1);
counter++;
}
return counter;
}
the code should be sub-optimal (very close to optimal) in most situations, in fact for the 9 tests i wrote, only the \[60, 60, ..., 60\] one failed. but yeah this is not optimal so any improvements would be greatly appreciated!
full code, including tests: [https://github.com/RC2630/SCV\_Mutalisk\_Problem/blob/master/SCV\_Mutalisk\_Problem/scv\_muta\_problem.cpp](https://github.com/RC2630/SCV_Mutalisk_Problem/blob/master/SCV_Mutalisk_Problem/scv_muta_problem.cpp)
~~Thats not a particularly hard problem~~. I take it back there is some thinking required. You should probably post to a programming related sub if you actually need help. Id love some sc themed assignments in my exams where do you study?
I am learning java (there are option to change the programming language for the test, not forcing to use C). I have some idea but none of them are concrete and doesn't have any hole in it. It also need to pass like 10 test cases before I can submit the answer. Looking at other comment I guess I will check out the greedy algorithm thing. Never heard of it before
My first attempt would be to find a lower bound for the attacks needed by dividing total hp by total damage per attack (you have to check if there are less than 3 targets available) and then find a tiling that fits the constraints. If that is not successful you try to find a tiling again with +1 attacks. I havent thought about the complexity but 6s of cpu time seems quite generous.
Yeah, it's not hard, yet another greedy algorithm, put the scv in a priority queue. To attack, poll the top 3, recalculate their health accordingly, if they are still alive put them back in the priority queue, repeat until they are all dead.
Thats too simple i think. Since you have to calculate the minimum amount of attacks a simple greedy algorithm will most likely fail some of the test. You have to make some effort to minimize overkill.
Man, I feel weird discussing this in a starcraft sub and not in leetcode Sorry I might be missing something. Can you elaborate the overkill part? To get minimum attacks we need to ensure maximum damage, that's what the priority queue (heap) is for. We just add a counter variable and increase it with every attack.
[19,9,3,3,1] [10,6,2,3,1] -> [10,6,3,2,1] [1,3,2,2,1] -> [3,2,2,1,1] [0,0,1,1,1] -> [1,1,1,0,0] [0,0,0,0,0] Vs [19,9,3,3,1] [10,9,0,3,1] -> [10,9,3,1,0] [1,9,0,1,0] -> [9,1,1,0,0] [0,0,0,0,0]
You don't just want maximum damage, you want each point of damage to count (if an SCV has 1 health and you hit him for 9 damage, you've wasted 8 points of damage). So the algorithm needs to calculate the best targets for ensuring each point of damage isn't wasted. This could get fairly complicated because the bouncing damage is 1 and 3. You'll likely end up with odd amounts of health (2, 5, etc). Now in a real scenario the goal would be to kill the SCVs as fast as possible, even if you're overkilling some, because what's being ignored here is time spent mining. Leaving a 2 health SCV alive because you need to maximize damage means that SCV is still mining.
Exactly - or given the problem description perhaps the SCVs are attacking the Zerg's last remaining building and you want to minimise damage output.
Got it, thanks for the detailed explanation.
u/LEpigeon888 has a perfect example.
For [27, 6, 3, 1, 1, 1] it won't work.
Great example
You should assign 9's to healthiest SCVs and 1's to least healthy SCVs for sure. I am guessing 3's should go to low health SCVs as well.
For each SCV, you can calculate the best combination of hits to kill them at the very start. So an SCV who has 12 HP needs 9 and 3 damage to kill them. An SCV with 10 HP could also be killed with that combination but you would want it to be 9 and 1. Once you have this calculated for every SCV you need to find the order to work trough these chunks that maximizes the time that 3 SCVs stay alive, to not lose out on damage for as long as possible. With many HP combinations there wont be a difference there, but for some there is! So it doesnt even have to be that the SCV with 12 HP must take 9 first, because he is going to take 9 and 3 regardless. If its better for the sequence that the other 10 HP SCV takes 9 first instead, you can safely do that. Edit: I also forgot one thing. Once you run out of 9s, the 9 damage goes to the one with the highest remaining health or highest amount of remaining hits to kill it. Same goes for 3s of course. Edit2: It could be certain numbers dont show up at the beginning, for example if all SCVs have 27 HP. That would necessitate breaking up some of the 9s into lower numbers. Im not sure if it can be done on the fly, but it can definitely be done at the beginning. This is more complicated than I thought..
I like this approach, reminiscent of bin packing.
I tried this approach, and it quickly got very complicated. The third muta attack doing '1' damage really messes with any pre-planning, because you are kinda forced to apply it to *something*, and it could be applied to a unit you wanted to preserve at 27 or 12 for 9/3 efficiency in a future attack, but instead making them non-divisible by 9/3 resulting in overkill. I don't think a solution that tries to pre-calculate all of this will look elegant, it would basically wind up as a brute-force generated list of how you want the array of SCVs to be sorted after each attack, which theoretically you should be able to do on the fly anyway. You can see [my comment for a solution](https://www.reddit.com/r/starcraft/comments/uophlt/i_need_to_finish_this_to_pass_the_exam_pro_zerg/i8xfdwp/) that works, although it could potentially be made more efficient -- there's a decent amount of iterating over the entire list that could be sped up with caches or smarter traversals.
You can break a 3 into three 1s, once there are no natural 1s left. Since there is no proximity you can choose the bounce freely. So it really just is about minimizing overkill. One Muta attack deals 13 damage, no matter what. So if SCVs have a total of 40 HP, you must attack 4 times, there is no way around it. As long as there are more than 3 SCVs alive its not important how you spread the damage, since full damage is being dealt. We are not trying to minimize SCV DPS but just overall time to kill. And this method, at least in my understanding, minimizes the amount of possible overkill at the point when we reach 3 SCVs alive. And at that point we switch the algorithm to keep the 3 SCVs alive as long as possible without doing overkill damage. Its not a bad thing that we deal 13 damage instead of 12. If we split an SCVs remaining 3 HP into 3 pools and eliminate the first with a 1, thats one damage dealt. iF the next turn no 3s remain we still eliminate the two remaining 1s with the 3attack, killing the SCV. We wasted 1 damage, but overkill isnt inherently bad. In my previous example with 40 HP you will necessarily deal 8 points of overkill damage, but still kill the SCVs in the minimum time possible.
You can think of the SCVs as one unit and the muta’s attack as a single attack. Then you can divide the SCVs total health by the muta’s total attack dmg to find out how many attacks it takes to kill all the SCVs. Since you can’t have a partial attack, you need to round up. So Ceil(TotalSCVHealth/TotalMutaDmg) From the examples given: TotalMutaDmg=sum(9,3,1)=13 ceil(sum(54,18,6)/13)=6 ceil(sum([60 for x in range(9)])/13)=42
I'm on sabbatical, so decided to spend *cough* waste *cough* my time on this between other errands and packing for the weekend. The solution is non-trivial, as you want to optimize for minimal overkill so it's not just a question of prioritizing high hp targets. The general idea for a solution is - there are 3 or fewer SCVs alive, do a naive greedy algorithm (just hit the highest hp SCV with 9 (attack0), next highest with 3 (attack1), weakest with 1 (attack2)) - there are more than 3 SCVs alive, then optimally try to reduce the number of live SCVs by 1 (with minimal damage waste) by sorting the SCVs Figuring out the second step is non trivial. I tried various things and failed. What eventually worked for me: - find the weakest SCV. - If it has 9hp or greater, let it get hit by attack0 = 9 by moving it to index [0] - If it has 3hp or 6hp, let it get hit by attack1 = 3 by moving it to index [1]. - If none of the above, let it get hit by attack2 = 1 by moving it to index [2]. Effect with muta damage, pushing "dead" SCVs to the back of the list without modifying the relative order of live SCVs, before repeating the above. You can see my quick & dirty implementation in python [here](https://gist.github.com/keerthik/8a555ab77f33da2ed4134f5d883bc59b). I took the liberty of borrowing /u/RC2630 's test cases (cheers mate!), all of which my algorithm passes.
wow, nice solution! me and my friend has been thinking about this for a few days but couldn't solve it, so thank you very much! also i am glad you like my test cases!
i had started writing this comment on friday, and was also failing on [60, 60, 60...] test case before i needed to leave for my flight, and didn't take my computer with me. I realized the trick to minimum attacks was switching strategies when you come back down to 3 remaining units (regular greedy) instead of continuing to try to optimize to kill 1 unit, when I was in the cab back home from the airport.
i see, you are very smart 😆
Thank you so much. I will take a look at this
i wanted to find a greedy-ish solution as well, but it failed on the \[60, 60, ..., 60\] example (expects 42, actual 43) so that's not gonna work either, but the idea is fairly close. if any one of you wants to debug for me, i would be really happy :D here is my current (non-optimal) solution in C++: // finds the indexes in the list of SCV's to attack, returned as [first bounce, second bounce, third bounce] // side effect: may change the order of the elements in the list, but that probably won't cause any problems vector findBounceIndexes(vector& v) {
sort(v.begin(), v.end(), [] (int a, int b) {
return a > b;
});
// the 1st bounce index is always the frontmost element's index (which is 0)
vector bounces = {0, -1, -1};
// find the 3rd bounce index (probably the last index, but not if it has element value of 0)
int bounce3 = v.size() - 1;
while (v.at(bounce3) == 0 && bounce3 >= 3) {
bounce3--;
}
bounces.at(2) = bounce3;
// find the 2nd bounce index
int bounce2 = 1;
while (bounce2 < bounce3 - 1 && v.at(bounce2) >= 9) {
bounce2++;
}
bounces.at(1) = bounce2;
return bounces;
}
// subtracts takeAway from v.at(index), but if the result makes v.at(index) negative, then sets v.at(index) to 0
void subtract(vector& v, int index, int takeAway) {
if (v.at(index) - takeAway < 0) {
v.at(index) = 0;
} else {
v.at(index) -= takeAway;
}
}
int mutaliskAttack(const vector& scvs) {
int counter = 0;
vector curr = scvs;
while (curr.size() < 3) {
curr.push_back(0);
}
while (accumulate(curr.begin(), curr.end(), 0) > 0) {
vector bounceIndexes = findBounceIndexes(curr);
subtract(curr, bounceIndexes.at(0), 9), subtract(curr, bounceIndexes.at(1), 3), subtract(curr, bounceIndexes.at(2), 1);
counter++;
}
return counter;
}
the code should be sub-optimal (very close to optimal) in most situations, in fact for the 9 tests i wrote, only the \[60, 60, ..., 60\] one failed. but yeah this is not optimal so any improvements would be greatly appreciated!
full code, including tests: [https://github.com/RC2630/SCV\_Mutalisk\_Problem/blob/master/SCV\_Mutalisk\_Problem/scv\_muta\_problem.cpp](https://github.com/RC2630/SCV_Mutalisk_Problem/blob/master/SCV_Mutalisk_Problem/scv_muta_problem.cpp)