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
