PROBLEM LINK
Author: Kanhaiya Mohan
Tester: Saurav Jha
Editorialist: Naman Dhingra
DIFFICULTY
EASY
PREREQUISITES
GREEDY, PREFIX SUM, ARRAY
PROBLEM
Given an integer X, m identical objects ordered from left to right (divided into n consecutive groups) and an array A having n elements, where A_{i} is the number of objects in the i^{th} group. Determine the maximum number of objects that can be selected so that no two objects are from the same group and the distance between any two selected objects is at least X.
OBSERVATION
The first planet of the first group will always be selected. Thereafter, the leftmost possible planet of a different group and following the distance constraint will be selected.
EXPLANATION
Greedy approach works in this problem.
To show this, consider the following case:
n = 2, A= [5,2], X = 6
Door 1 : [ P1, P2, P3, P4, P5 ] Door 2 : [ P6, P7]
It can be seen that if any other planet reachable from Door 1 other than P1 is selected, no planet reachable from Door 2 can be selected because of the distance constraint. Hence, selecting P1 is optimal (leftmost possible planet).
The first planet reachable by the first door will always be selected as there is no distance constraint on it and it is the leftmost possible door.
SOLUTION
One solution which is very simple is to keep increasing the planet index from
currently\_selected\_planet + X by 1 until it is part of a different group, then select that planet and continue doing so. But this solution will have a time complexity of O(m) which will not work with the given constraints.
A better approach is to check for each group, if there is a planet in that group, which follows the distance constraint from the currently selected planet.
Let pref[k] be the total number of planets in groups 1 to k.
To select a planet from the i^{th} group, if currently\_selected\_planet + X > pref[i-1]+a[i] then no planet for the i^{th} group can follow the distance constraint.
Otherwise,
If (pref[i-1]+1) - currently\_selected\_planet >= X then select pref[i-1] + 1 ie: the leftmost planet for the i^{th} group. Else, select (currently\_selected\_planet + X)^{th} planet.
TIME COMPLEXITY
O(n) per testcase
SOLUTION
Editorialist's Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;
cin>>t;
while( t-- ){
int n, x;
cin >> n >> x;
int a[n];
for( int i = 0 ; i < n ; i++ ){
cin >> a[i];
}
int currselected = 1; // currently_selected_planet
int doors = 1; // number of planets selected till now
int doorsvis = a[0]; // number of planets checked/visited
for( int i = 1 ; i < n ; i++ ){
if( doorsvis + 1 - currselected >= x ){
currselected = doorsvis + 1;
doors++;
}
else if( doorsvis + a[i] - currselected >= x ){
currselected = currselected + x;
doors++;
}
doorsvis += a[i];
}
cout << doors << endl;
}
}
Feel free to share your approach. Suggestions are welcome! :)