HOOPS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY

Cakewalk

PREREQUISITES

Observation

PROBLEM

Given N hoops (where N is odd) in a row. You jump into hoop 1, and your friend jumps into hoop N. Then you jump into hoop 2, and after that, your friend jumps into hoop N−1, and so on. The process ends when someone cannot make the next jump because the hoop is occupied by the other person. Find the last hoop that will be jumped into.

QUICK EXPLANATION

The process ends when someone jumps into the middle hoop. Therefore, the middle hoop will be the last hoop that will be jumped into.

EXPLANATION

Now, given a number N (where N is odd) we need to find its middle.

  • Brute force approach will iterate through N and find the middle. That can be done by taking two pointers L and R, L starting at 1 and R starting from N. That can be done using the below code.
L=1
R=N
while L < R:
    L+=1
    R -=1
print(L)

The time complexity of the above approach is O(N) per test case, which will exceed the given time constraints. Therefore we need to find an optimized approach.

  • Optimize approach is that we can find the middle of a number N (where N is odd) by \frac{N+1}{2}. The time complexity of this approach is O(1) per test case.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
 
using namespace std;
 
const int maxt = 1e5 - 1, maxn = 1e5;
 
int main()
{   
    int t; cin >> t;
    int n;
    while(t--){
        cin >> n;
        cout << (n / 2 + 1) << endl;
    }
} 
Tester's Solution
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) {
        int n;
        cin >> n;
        cout << (n + 1) / 2 << '\n';
    }
}
Editorialist's Solution

3 Likes

@cherry0697 Just a query like if suppose N could be anything like odd or even in that case we would have to check like N % 2 == 0
like if it is equal to zero then answer would be N / 2 else answer would be (N / 2) + 1 right?? Is that the correct logic.Asking just out of curiosity

4 Likes

Hi , try running for some numbers through them, you would observe that irrespective of odd or even N, the value will always be (N+1)/ 2

2 Likes

Editorialist’s Solution
:joy: :joy: :joy:

1 Like

Hey thanks man!!