PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Vichitr Gandas
DIFFICULTY:
EASY
PREREQUISITES:
Binary Search, Greedy, Observations
PROBLEM:
A bird starts at a height H at x=0, and there are N obstacles i^{th} of which is of height h_i at position x_i. The only difference is that the obstacles are only from bottom to top and not in the reverse direction. For the bird to cross the i^{th} obstacle successfully, the bird’s height at x_i should be strictly greater than h_i.
Find minimum number of clicks required to cross all the obstacles given that with one click if initially at (i,j), then after the click (i+1,j+1), otherwise if we don’t click at x=i, then at (i+1, j−1). Also at any point before x=x_N, height of the bird should remain non negative otherwise it will drown.
QUICK EXPLANATION:
Notice that if we keep ascending the bird continuously for first k moves and let it descend such that it crosses all the obstacles, thats equivalent to simultaneous ascend + descend in an optimal game play. So the above problem can be solved using binary search on k.
Or we can also solve greedily. Initially decrease H from each h_i. Now just take max((h_i+x_i+2)/2) for all i. If at any point x_i <= h_i then its impossible.
EXPLANATION:
Binary Search Solution
Let’s say in the optimal play, the bird is able to pass through all obstacles with k clicks then clicking k times in the start is always optimal.
Why doing all clicks in the start is optimal?
If we click k times then height would be H+k after all the clicks and after another k steps, it would be again H, because each move H decreases by 1 if we don’t click.
In any other strategy where we don’t click once, the bird would never have more height than H after k*2 moves. Hence best optimal way is to do all clicks continuously in the start.
Now how to check if k clicks are enough to pass all the obstacles?
We can simulate the process by doing all clicks in first k moves and checking if at every obstacle i, the bird height is > h_i. Now how to calculate height at position x?
If x_i <= k, then height would be H + x_i because we have clicked x_i clicks so far.
If x_i > k then height would be H + k - (x_i - k) because we have clicked k times and moved x_i - k extra steps after all the clicks.
Pseudocode
def check(k):
for i in range(n):
if x[i] <= k:
if h[i] >= H + x[i]:
return False
else:
if h[i] >= H + k - (x[i] - k):
return False
return True
Now if we know that k clicks are enough, then more than k clicks would also lead to a win. Hence we should try for less than k clicks. This gives a perfect situation for binary search on k.
Greedy Solution
The bird is initially at (0,H). Let’s bring it to (0,0) by shifting the x-axis H units up. After this initial position of the bird would be (0,0) and all the obstacles height would decrease by H.
Now when is it impossible to win?
When h_i >= x_i for any i then its impossible to win because we can click at most x_i times and the bird can achieve at most height x_i but still it would be less or equal to the height of the obstacle hence the bird will crash.
Now how to find minimum number of clicks required?
If we know how many clicks each obstacle would take so that the bird doesn’t clash with it, we can take maximum of all to find the number of clicks to safely pass all obstacles.
Now how to find the number of clicks required for i^{th} obstacle which is at position x_i and height h_i?
- We know that the bird started at (0,0) so to reach x_i, it would need at least x_i/2 clicks. One click can make the bird move for two steps. But if we do exactly x_i/2 clicks, it would touch (x_i,0).
- Now we also want the bird to be at height at least h_i so that it doesn’t touch the obstacle.
Reaching at x_i and having the height h_i is equivalent to moving x_i+h_i distance. But we need to ensure we don’t touch this point, hence it would at least (x_i+h_i+1)/2 clicks if x_i+h_i is odd and (x_i+h_i)/2 + 1 clicks if x_i+h_i is even. Or we can write it as (x_i+h_i+2)/2 clicks in both cases.
So finally iterate over the all obstacles and take maximum of (x_i+h_i+2)/2 over all i.
TIME COMPLEXITY:
O(nlog(10^9)) for binary search solution.
O(n) for linear solution.
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 maxn = 1e5, maxtn = 5e5, maxx = 1e9, maxh = 1e9, maxt = 28752;
const string newln = "\n", space = " ";
int n, H;
int d[maxn + 10], h[maxn + 10];
set<int> p;
bool valid(int x){
for(int i = 0; i < n; i++){
if((d[i] <= x && h[i] >= H + d[i]) || (d[i] > x && h[i] >= H + x - (d[i] - x))){
return false;
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
int tn = 0;
while(t--){
cin >> n >> H; tn += n;
p.clear();
for(int i = 0; i < n; i++){
cin >> d[i];
if(i > 0)assert(d[i] > d[i - 1]);
p.insert(d[i]);
}
assert(p.size() == n);
for(int i = 0; i < n; i++){
cin >> h[i];
}
int l = 0, r = maxx, ans = -1;
while(l <= r){
int m = (l + r) >> 1;
if(valid(m)){
ans = m; r = m - 1;
}else{
l = m + 1;
}
}
cout << ans << endl;
}
assert(tn <= maxtn);
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#ifdef HOME
#include <windows.h>
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 30'000);
int sumN = 0;
forn(tc, T)
{
int N = readIntSp(1, 100'000);
int H = readIntLn(0, 1'000'000'000);
vector<pair<int,int>> x(N);
int ctr = 0;
for (auto& xi : x)
{
++ctr;
if (ctr == N)
xi.first = readIntLn(1, 1'000'000'000);
else
xi.first = readIntSp(1, 1'000'000'000);
}
ctr = 0;
for (auto& xi : x)
{
++ctr;
if (ctr == N)
xi.second = readIntLn(1, 1'000'000'000);
else
xi.second = readIntSp(1, 1'000'000'000);
xi.second -= H;
}
bool solvable = true;
int sol = 0;
for (const auto& xi : x)
{
if (xi.first <= xi.second)
solvable = false;
else
{
sol = max(sol, (xi.first + xi.second + 2) / 2);
}
}
if (!solvable)
{
printf("-1\n");
continue;
}
printf("%d\n", sol);
}
assert(sumN <= 500'000);
return 0;
}
Editorialist's Solution
/*
* @author: vichitr
* @date: 26th June 2021
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n, H, x[N], h[N];
bool check(int k) {
for (int i = 0; i < n; i++) {
if (x[i] <= k) {
if (h[i] >= H + x[i])
return false;
}
else {
if (h[i] >= H + k - (x[i] - k))
return false;
}
}
return true;
}
void binary_search() {
cin >> n >> H;
for (int i = 0; i < n; i++)
cin >> x[i];
for (int i = 0; i < n; i++)
cin >> h[i];
int s = 0, e = 1e9;
int ans = -1;
while (s <= e) {
int m = (s + e) / 2;
if (check(m)) {
ans = m;
e = m - 1;
}
else
s = m + 1;
}
cout << ans << '\n';
}
void greedy() {
cin >> n >> H;
for (int i = 0; i < n; i++)
cin >> x[i];
for (int i = 0; i < n; i++) {
cin >> h[i];
h[i] -= H;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (h[i] >= x[i]) {
ans = -1;
break;
}
ans = max(ans, (x[i] + h[i] + 2) / 2);
}
cout << ans << '\n';
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
while (t--) {
//binary_search();
greedy();
}
return 0;
}
VIDEO EDITORIAL:
If you have other approaches or solutions, let’s discuss in comments.