# 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! :)