Header Ad

HackerEarth Game Of Strengths problem solution

In this HackerEarth Game of Strengths problem solution, Andrew is very fond of Maths.He has N boxes with him,in each box there is some value which represents the Strength of the Box.The ith box has strength A[i]. He wants to calculate the Overall Power of the all N Boxes.

Overall Power here means Sum of Absolute Difference of the strengths of the boxes(between each pair of boxes) multiplied by the Maximum strength among N boxes. Since the Overall Power could be a very large number,output the number modulus 10^9+7(1000000007).


HackerEarth Game Of Strengths problem solution


HackerEarth Game Of Strengths problem solution.

#include<iostream>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<functional>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#define MOD 1000000007
using namespace std;
long long arr[1000010];
int main()
{
int i,n,t;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n,greater<long long>());
long long ans=0,temp;
for(i=0;i<n-1;i++)
{
ans=(ans+(n-i-1)*arr[i])%MOD;
}
temp=MOD*(long long)100000;
for(i=n-1;i>0;i--)
{
ans=(temp+ans-(i)*arr[i])%MOD;
}
ans=(ans*arr[0])%MOD;
cout<<ans<<endl;
}
return(0);
}

Second solution

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cassert>
#include<set>
#include<queue>
#include<map>

using namespace std;

#define vi vector < int >
#define pb push_back
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define all(x) x.begin(),x.end()

ll a[100005];

int main()
{
int t,n,i;
scanf("%d",&t);
assert(1<=t && t<=10);
while(t--)
{
scanf("%d",&n);
assert(2<=n && n<=100000);
ll mx = -INF;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
assert(0<=a[i] && a[i]<=1000000000);
mx = max(mx,a[i]);
}
mx %= MOD;
ll ans = 0;
sort(a+1,a+n+1);
ll sum = 0;
for(i=1;i<=n;i++)
{
ans = (ans+((i-1)*a[i] - sum+MOD)%MOD)%MOD;
sum = (sum+a[i])%MOD;
}
ans = (ans*mx)%MOD;
printf("%lld\n",ans);
}
//system("pause");
return 0;
}


Post a Comment

0 Comments