PROBLEM LINK:
Author: Kaushik Iska
Tester: Anton Lunyov
Editorialist: Anton Lunyov
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
It is the best described in the problem statement.
QUICK EXPLANATION:
For each level L let’s calculate the total power of Soints of this level and the same for Sofloats. Let it be SointsPower[L] and SofloatsPower[L] respectively. Then if SointsPower[L] strictly less than SointsPower[L] we add the difference SofloatsPower[L] − SointsPower[L] to the answer. Doing this for all L we get the final answer.
EXPLANATION:
Though the previous explanation seems to be obvious it still requires some justification. If you understand it clearly you can skip this paragraph. Let’s consider the difference SofloatsPower[L] − SointsPower[L] introduced above. Clearly, it remains the same after each fight at this level. Also it is clear that if both numbers SofloatsPower[L] and SointsPower[L] are positive then the fight at the level L is possible and these two numbers decreases after the fight. So the battle ends once for each level one of these numbers equal to zero, while other will be equal to the absolute difference of the initial values of these two numbers. Clearly if SofloatsPower[L] > SointsPower[L] then in the end there will be no Soints of level L but at least one Sofloat of level L will remain. On the other hand, if SofloatsPower[L] ≤ SointsPower[L] then there will be no Sofloats of level L in the end of the battle. Hence SoChef should give at least SofloatsPower[L] − SointsPower[L] additional chakra to Soints of level L if this difference is positive and it also will be sufficient. Hence the answer coincides with that described above.
Now let’s discuss an implementation of this solution. Since levels are positive integers up to 100 we can create an arrays SointsPower[] and SofloatsPower[] with meaning described above initially filled by zeros:
for L from 1 to 100
SointsPower[L] = 0
SofloatsPower[L] = 0
We can fill them just during the reading the information about warriors. That is, if numbers C and L was read for the current Soint we should simply increase SointsPower[L] by C:
read C, L SointsPower[L] = SointsPower[L] + C
The same should be made for Sofloats. After that in one loop over all possible levels we calculate the answer:
ans = 0
for L from 1 to 100
dif = SofloatsPower[L] − SointsPower[L]
if dif > 0 then
ans = ans + dif
print ans
So we get the solution with time complexity O(N + M + L) and memory O(L). You can see an implementation of this approach in author’s solution.
ALTERNATIVE SOLUTION:
Let’s save all information about warriors in, say, 4 arrays of numbers. Then iterate over all levels from 1 to 100 and for each level L create a variable dif initially set to 0 and iterate over all Soints and over all Sofloats. If Soint of level L is met decrease dif by power of this Soint. If Sofloat of level L is met increase dif by power of this Sofloat. If in the end dif > 0 then increase answer by dif. Clearly in this way we find the answer. This solution has time complexity O(L * (N + M)) and requires O(N + M) memory. So it is slower then the previous one but easily passes the time limit.
We can improve this solution. For this let’s sort all warriors by level and then iterate over all warriors by groups of the same level and do the same as above with dif. In this way we get a solution with complexity O((N + M) * log (N + M)) and the same memory if we use some fast sorting algorithm like Quicksort or Merge sort. You can see an implementation of this approach in tester’s solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.