DRGNBOOL - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

LECANDY

3 Likes

#include

using namespace std;

int main()
{
int t,n,m,a[101],b[101];
int i,x,y,ans;
cin>>t;
while(t–)
{
cin>>n;
cin>>m;
for(i=0; i<100; i++)
{
a[i]=b[i]=0;
}
for(i=0; i<n; i++)
{
cin>>x;
cin>>y;
a[y]+=x;
}
for(i=0; i<m; i++)
{
cin>>x;
cin>>y;
b[y]+=x;
}
ans=0;
for(i=0; i<100; i++)
{
if(a[i]<b[i])
ans+=(b[i]-a[i]);
}
cout<<ans<<endl;
}
return 0;
}

Both Author’s and Tester’s Solutions fail. Their Solutions have changed the meaning of the question.
Consider this simple test-case :

1

2 2

9 1

5 1

6 1

7 1

Here the output should be 1 . As if warrior with power 9 battles with warrior with power 7 then soints warrior now has power 2(i.e. 9-7). Then warrior with power 5 will battle with warrior with power 6, so the wizard must increase the power of 5 by 1 else soints will loose.

But according to authors & testers solution, They are considering as if more than 1 warrior can battle with 1 warrior which is wrong according to question statement. The answer according to their solution comes to be 0 .(i.e. 9+5>=6+7).

Hi everyone,following text has been copied from the question : “Also note that the battle can proceed by different scenarios and the SoChef need to distribute additional chakra among the Soints in such a way that they will win for any possible battle scenario.”

Doesn’t that mean we should find the the number of chakras for the worst case which can happen.
But according to this editorial they are considering the best case possible.

consider this test case:
2 1
3 1
9 1
7 1

worst case: (F 7 1) fights with (I 3 1) chakras required:4
Best case: (F 7 1) fights with(I 9 1) chakras required:0

According to me: Any possible battle scenario means WE SHOULD CONSIDER THE WORST CASE RATHER THAN THE BEST CASE.please correct me if I am wrong.

Can someone please point out what is wrong in this code?

#include
#include <math.h>
#include

using namespace std;

#define lli long long int
#define loop(i,a,b) for(lli i=a;i<b;i++)

int main() {
int t;
cin>>t;
while(t–)
{
int n,m, a[100]={0},temp1=0,temp2=0,ans=0;
cin>>n>>m;

	loop(i,0,n)
	{
		cin>>temp1>>temp2;
		a[temp2] += temp1;
	}

	loop(i,0,m)
	{
		cin>>temp1>>temp2;
		a[temp2] -= temp1;
	}

	loop(i,0,100)
	{
		if(a[i] < 0)
			ans += a[i];
	}

	cout<<-1*ans<<"\n";
}
return 0;

}