Qus: Cover Them All!

#1

I was solving few qus on Haker block.
and this qus quite tricky one. pls let me my error. I am trying 10 times still getting error.

My code:

#include <bits/stdc++.h>
using namespace std;
#define M 100000000007
#define ll long long

int main () {
#ifndef ONLINE_JUDGE
freopen(“input.text”, “r”, stdin);
freopen(“output.text”, “w”, stdout);
#endif
int t;
cin>>t;
while(t–)
{
ll n,cost = 0;
cin>>n;
ll arr[n];
ll b[n];
for(ll i=0; i<n; i++)
{
cin>>arr[i];
}
for(ll i=0; i<n; i++)
{
cin>>b[i];
}
sort(arr,arr+n);
sort(b,b+n);
ll v;
for(ll i=0; i<n-1; i++)
{
for(ll j=i+1;j<n;j++)
{
v = ((arr[i]%M)-(arr[j]%M))%M;
v = abs(v)%(M);
cost += v*max(b[i],b[j]);
}
}
cout<<(cost)%M<<"\n";

}

}

#2

@deepak147852 I do not know which question you are talking about, I would be better if you code resolve this doubt and raise it on the question on which you have doubt.

#3

It’s from hackerblock.
Title :- “Cover Them All”
Quesrion
There are N soldiers located on our X-AXIS . The point at which soldier is located also has some number of bombs .
The war is near and every soldier wants to communicate with every other soldier.
If the ith soldier has b number of bombs and is located at position X then the cost of communicating with any other soldier j having c number of bombs located at position Y is defined as *|X-Y|max(b,c) .
Find the sum of costs of communication if every soldier wants to communicate with every other soldier.
NOTE :- You have to consider pair(i,j) only once in sum of costs.

Input Format

First line consists of number of test cases T. Each test case consists of three lines. The first line indicates the number of soldiers (N). The second line indicates the coordinates of the N soldiers ( X[i] ). The third line contains the number of bombs at every soldiers location ( B[i] ) . The x-coordinates needn’t be in increasing order in the input.

Constraints

1 <= T <= 20 1 <= N <= 200000 1 <= X[i] <= 1000000000 1 <= B[i] <= 10000

Output Format

The total cost modulo 10^9+7.

Sample Input

1 3 1 3 6 10 20 30

Sample Output

280

Explanation

there are 3 pairs (1,2) -> cost = abs(3-1) * 20 = 40 (1,3) -> cost = abs(1-6) * 30 = 150 (2,3) -> cost = abs(3-6) * 30 = 90 sum = 40 + 150 + 90 = 280

#4

My Code

#include <bits/stdc++.h>
using namespace std;
#define M 100000000007
#define ll long long

int main () {
#ifndef ONLINE_JUDGE
freopen(“input.text”, “r”, stdin);
freopen(“output.text”, “w”, stdout);
#endif
int t;
cin>>t;
while(t–)
{
ll n,cost = 0;
cin>>n;
ll arr[n];
ll b[n];
for(ll i=0; i<n; i++)
{
cin>>arr[i];
}
for(ll i=0; i<n; i++)
{
cin>>b[i];
}
sort(arr,arr+n);
sort(b,b+n);
ll v;
for(ll i=0; i<n-1; i++)
{
for(ll j=i+1;j<n;j++)
{
v = ((arr[i]%M)-(arr[j]%M))%M;
v = abs(v)%(M);
cost += v*max(b[i],b[j]);
}
}
cout<<(cost)%M<<"\n";

}

}

#5

@deepak147852 hey you will need segment or fenwick tree.
lets say we are considering a pair (x,y) of soldiers who communicate
assume x<y, so |x-y| = (y-x)
now we have 2 cases.
Case 1: b >= c
in this case the answer will simply be (y-x)*b, so total cost for this case is
sigma (y(i) - x) b
simplifying further, we get sigma (y) b - x b (number of soldiers having less bombs than current soldier)
To answer this one, we require 2 things:

  1. number of soldiers lying ahead having less bombs
  2. sum of their positions
    this can be answered with segment tree / fenwick tree.

Case 2: b < c
total cost for this case is
sigma [(y(i) - x) * c(i)]
simplifying:
sigma [y(i) c(i)] - sigma [x c(i)]
= sigma [y(i) c(i)] - x (sigma c(i) )
the first term can be found out by precomputing all y(i)*c(i) values, and proceeding in a similar way

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#7

ok, abhinav one qus only

You are developing a smartphone app. You have a list of potential customers for your app. Each customer has a budget and will buy the app at your declared price if and only if the price is less than or equal to the customer’s budget.

You want to fix a price so that the revenue you earn from the app is maximized. Find this maximum possible revenue.

For instance, suppose you have 4 potential customers and their budgets are 30, 20, 53 and 14. In this case, the maximum revenue you can get is 60.

Input format

Line 1 : N , the total number of potential customers.

Lines 2 to N +1: Each line has the budget of a potential customer.

Output format

The output consists of a single integer, the maximum possible revenue you can earn from selling your app.

Sample Input 1

4 30 20 53 14

Sample Output 1

60

Sample Input 2

5 40 3 65 33 21

Sample Output 2

99

Test data

Each customers’ budget is between 1 and 108, inclusive.

Subtask 1 (30 marks) : 1 ≤ N ≤ 5000.

Subtask 2 (70 marks) : 1 ≤ N ≤ 5×105.

Live evaluation data

There are 15 test inputs on the server during the exam. The grouping into subtasks is as follows.

• Subtask 1: Test inputs 0,…,5

• Subtask 2: Test inputs 6,…,14

Solution

#include
using namespace std;
#include
int maximumProfit(int budget[], int n) {
sort(budget, budget + n);
int *cost = new int[n];
for(int i = 0;i < n;i++)
cost[i] = budget[i] * (n - i); // budget[i] * (n-i) why?
int max = 0;
for(int i = 0;i < n;i++)
if(cost[i] > max)
max = cost[i];
return max;
}

int main() {
int n ,*input,i,*cost;
cin>>n;
input = new int[n];
for(i = 0;i < n;i++)
cin>>input[i];

cout << maximumProfit(input, n) << endl;

}

Please see my comment and pls let me why we have multiply **budget[i] * (n-i) **