Weak Avengers
Difficulty
Medium-Hard
Prerequisites
Segment tree
Problem Statement
We are given n avengers with two parameters strength value and strength type.
We have to kill some avengers such that more than half the avengers have same
strength type. When we kill an avenger the amount of power required is equal
to the strength value of avenger. We have to find the minimum value of power
required to achieve the task.
Solution
So the basic solution is we will find the count of avengers with same strength
type, so if the count of avengers is k. So let us consider that these type of avenger
is the majority type. So to make these type of avengers majority we have to
delete (n − (2 ∗ k − 1)) elements. So to find the minimum value of power we
have to choose (n − (2 ∗ k − 1)) minimum elements having other strength type.
Strength type : 1, 1, 1, 2, 2, 3, 3
Strength value: 2, 3, 4, 5, 6, 7, 8
So to make type 1 avenger majority: We have to delete 7 − (2 ∗ 3 − 1) = 2
elements. So we will choose avengers with strength type 5 and 6. So that sums
upto 11.
We will perform these for every distinct type.
Worst case Complexity tends to: O(N3
).
Efficient Solution
So we will keep the basic structure of the solution same. We will use segment
tree to find the minimum value excluding the range containing the choosen type
of avengers.
Strength type: 1, 1, 1, 2, 2, 3, 3
1
Strength value: 2, 3, 4, 5, 6, 7, 8
Ranges:
type 1: l=0 r=2
type 2: l=3 r=4
type 3: l=5 r=6
Segment tree to find the minimum value excluding the
range: Please read my article on geeksforgeeks to find the solution:
https://www.geeksforgeeks.org/queries-for-the-minimum-elementin-an-array-excluding-the-given-index-range/
To get the second minimum element we will update the minimum value with
INT_MAX and again query for the range this will give the second minimum
element. This way we can find (n − (2 ∗ k − 1)) minimum elements required.
After the task we will replace the values in segment tree which were changed to
INT_MAX with their original values.
But still our complexity does’nt reduce and it will still show TLE because
complexity still remains O(N ∗ N ∗ log(n))
We have to change the way we approach our problem.
Instead of choosing the (n − (2 ∗ k − 1)) minimum elements, we can just save
k − 1 avengers with maximum strength values and kill the rest.
So we will use the same segment tree concept to find the maximum elements
excluding a range and kill the rest and then find the minimum value among all
strength types.
Time Complexity
O(N ∗ log(n)) as for every type of frequency k we are querying k − 1 times, so
summation of (k −1) ∗ log(n) = (k1+k2+…+kq −q) ∗ log(n) tends to n∗ log(n).
Code
Basic solution without segment tree
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
2
vector<pair<int,int> > v,v1;
vector v2;
int mp[1000002] = {0}, co = 0;
memset(mp, 0, sizeof(mp));
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back(make_pair(x, 0));
v1.push_back(make_pair(0, x));
if (mp[x] == 0)
{
co++;
v2.push_back(x);
}
mp[x]++;
}
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v[i].second = x;
v1[i].first = x;
}
sort(v1.begin(), v1.end());
long long int sum1 = INT_MAX;
for (int i = 0; i < co; i++)
{
long long int c = n - (2 * mp[v2[i]] - 1) < 0
? 0 : n - (2 * mp[v2[i]] - 1), p = 0;
long long int sum = 0;
for (int j = 0; j < c && p < n; j++, p++)
{
while (v1[p].second == v2[i])
p++;
3
sum += v1[p].first;
if (i > 0 && sum > sum1)
break;
}
if(i == 0 || sum < sum1)
sum1 = sum;
}
cout << sum1 << endl;
return 0;
}
Efficient solution using segment tree
#include <bits/stdc++.h>
using namespace std;
const long long int N = 200008;
long long int* tree = new long long int[4 * N + 1];
long long int* inde = new long long int[4 * N + 1];
long long int n;
//function to build the segment tree
void buildTree(long long int* a, long long int index,
long long int s, long long int e)
{
//base case
if (s > e)
return;
//reached leaf node
if (s == e)
{
tree[index] = a[s];
inde[index] = s;
return;
}
//now build the segment tree in bottom up manner
long long int m = (s + e) / 2;
buildTree(a, 2 * index, s, m);
4
buildTree(a, 2 * index + 1, m + 1, e);
inde[index] = (tree[2 * index] < tree[2 * index + 1]
? inde[2 * index + 1] : inde[2 * index]);
tree[index] = max(tree[2 * index], tree[2 * index + 1]);
return;
}
//function to query the segment tree for RMQ
pair<long long int, long long int> query(long long int index, long long int s,
long long int e, long long int qs, long long int qe)
{
//base case: if query range is outside the node range
if (qs > e || s > qe)
return make_pair(LONG_MIN, -1);
//complete overlap
if (s >= qs && e <= qe)
return make_pair(tree[index], inde[index]);
//now partial overlap case is executed
long long int m = (s + e) / 2;
pair<long long int, long long int> left_ans = query(2 * index, s, m, qs, qe);
pair<long long int, long long int> right_ans = query(2 * index + 1, m + 1, e, qs, qe);
pair<long long int, long long int> po = (left_ans.first > right_ans.first
? left_ans : right_ans);
return po;
}
//function to update a value at position to “pos”
void updateNode(long long int index, long long int s,
long long int e, long long int pos, long long int val)
{
if (pos < s || pos > e)
return;
if (s == e)
{
tree[index] = val;
inde[index] = pos;
return;
}
5
long long int m = (s + e) / 2;
updateNode(2 * index, s, m, pos, val);
updateNode(2 * index + 1, m + 1, e, pos, val);
inde[index] = (tree[2 * index] < tree[2 * index + 1]
? inde[2 * index + 1] : inde[2 * index]);
tree[index] = max(tree[2 * index], tree[2 * index + 1]);
return;
}
int main()
{
cin >> n;
vector<pair<long long int, long long int> > arr;
long long int a[n];
long long int a1[n];
long long int x, ts = 0;
for (long long int i = 0; i < n; i++)
{
cin >> x;
arr.push_back(make_pair(x, 0));
}
for (long long int i = 0; i < n; i++)
{
cin >> x;
ts += x;
arr[i].second = x;
}
sort(arr.begin(), arr.end());
map<long long int, pair<long long int, long long int> > mp;
map<long long int, long long int> ms;
for (long long int i = 0; i < n; i++)
{
long long int e = i, sum = 0;
while (e < n && arr[e].first == arr[i].first)
{
sum += arr[e].second;
e++;
6
}
ms[arr[i].first] = sum;
mp[arr[i].first] = make_pair(i, e - 1);
i = e - 1;
}
for (int i = 0; i < n; i++)
{
a[i] = arr[i].second;
}
memset(tree, 0, sizeof(tree));
memset(inde, 0, sizeof(inde));
buildTree(a, 1, 0, n - 1);
long long int sum1 = LONG_MAX;
for (map<long long int, pair<long long int, long long int> >::iterator i = mp.begin();
i != mp.end(); i++)
{
long long int sum = 0;
long long int k = i->second.second - i->second.first + 1;
vector<pair<long long int, long long int> > st;
if (n - 2 * k + 1 <= 0)
{
sum1 = 0;
break;
}
k -= 1;
long pre = -10;
for (long long int i4 = 0; i4 < k; i4++)
{
long long int i1, i2, in, id, id1;
i1 = query(1, 0, n - 1, 0, i->second.first - 1).second;
i2 = query(1, 0, n - 1, i->second.second + 1, n - 1).second;
if (i1 == -1)
in = i2;
else if (i2 == -1)
in = i1;
else
{
in = (arr[i1].second > arr[i2].second ? i1 : i2);
}
sum += arr[in].second;
7
st.push_back(make_pair(in, arr[in].second));
updateNode(1, 0, n - 1, in, LONG_MIN);
arr[in].second = LONG_MIN;
}
sum1 = min(sum1, ts - (sum + ms[i->first]));
for (k = 0; k < st.size(); k++)
updateNode(1, 0, n - 1, st[k].first, st[k].second),
arr[st[k].first].second = st[k].second;
}
cout << sum1 << “\n”;
return 0;
}