Problem Link:
Problem Link: Defective Item
Contest Link: Chef Dynasty
Author & Editorialist: Ashish Sonam
Tester: Prakhar Kochar
Difficulty:
Cakewalk
Prerequisites:
Implementation, Prefix and Suffix Sum
Problem:
Chef has a container that opens from both ends and contains N items numbered from 1 to N. He realizes that one item whose value is x is defective and wants to remove it from the container. To remove an item Chef has to start from one end and take out each item till the defective piece is no more there. Work done will be the sum of values of items taken out in the process (including the defective item). Chef has Q queries denoting the defective item. He has to find the minimum work done for each query.
Explanation:
- Basically for each query, we have to find the minimum of prefix and suffix sum for certain index.
- Store the indices of each element.
- Traverse through the given array and store the prefix and suffix sums.
- For each query, we can get the position of defective item and get the minimum of prefix and suffix sums for the corresponding index in constant time.
Time Complexity:
O((Q * log(N)) + N)
Solutions:
Setter's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n, q;
cin >> n >> q;
vector<int> a(n), pref(n + 1), suff(n + 1);
map<int, int> mp;
for (int i = 0; i < n; i++)
{
cin >> a[i];
// storing the indices
mp[a[i]] = i;
}
// computing prefix sum
for (int i = 0; i < n; i++)
pref[i + 1] = pref[i] + a[i];
// computing suffix sum
for (int i = n - 1; i >= 0; i--)
suff[i] = suff[i + 1] + a[i];
while (q--)
{
int x;
cin >> x;
// get the index at which element x is present
int id = mp[x];
// minimum of prefix and suffix sum for index id
cout << min(pref[id + 1], suff[id]) << "\n";
}
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Tester's Solution (Python)
t = int(input())
for _ in range(0,t):
dic = {}
n,q = map(int,input().split())
lis = list(map(int,input().split()))
for i in range(0,n):
# storing the indices
dic[lis[i]] = i
pre = [0]*(n+1)
suf = [0]*(n+1)
# computing prefix sum
for i in range(0,n):
pre[i+1]=pre[i]+lis[i]
# computing suffix sum
for i in range(n-1,-1,-1):
suf[i]=suf[i+1]+lis[i]
for __ in range(0,q):
x = int(input())
# get the index at which element x is present
id = dic[x]
# minimum of prefix and suffix sum for index id
print(min(pre[id+1],suf[id]))