# MINORPATH - Editorial

Author: harasees_singh
Testers: mexomerf, rivalq
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Basic bit manipulation

# PROBLEM:

You are given an array A, and you’d like to move from position 1 to position N.
From position i, you can move to any position j such that i \leq j \leq \min(N, i + A_i).

The cost of a path is the bitwise OR of all values you visit along the way.
Find the minimum cost, or say that no valid path exists.

# EXPLANATION:

Since 2^0 + 2^1 + \ldots + 2^i \lt 2^{i+1} for every i \geq 0, it’s better for us to not use higher bits as much as possible; even at the cost of using more lower ones.

Let’s build our answer bit-by-bit, going from the higher bits to the lower ones (i.e, from 20 down to 0).
Suppose we’re currently dealing with bit b. Then,

• We need to (somehow) check if a path exists where we don’t need to use bit b.
• If such a path doesn’t exist, add 2^b to our answer; otherwise do nothing. Then, move to bit b-1 and continue.

Now let’s focus on checking whether a path that doesn’t include bit b exists.

• First, since we’re iterating in descending order, we know already for every bit \gt b whether it will be in the answer or not. If some bit doesn’t need to be in the answer, let’s call it forbidden.
• Bit b itself we don’t want to include, so let’s treat it as forbidden too.
• Any bit \lt b is ‘free’, so let’s just assume they’re all allowed, i.e, none of them are forbidden.

Now that we have a set of forbidden bits, we cannot land on any value that contains a forbidden bit.
Among the remaining positions, we need to check whether a path from 1 to N exists.

This can be done greedily:

• First, neither A_1 nor A_N can contain a forbidden bit, since we’ll definitely take those values. Check that first.
• Let’s keep a variable \text{reach}, denoting the furthest index we can reach. Initially, \text{reach} = 1 + A_1.
• Then, for each i from 2 to N:
• If i \gt \text{reach}, then it’s impossible to reach position i (or any position larger than i), so no path exists.
• If A_i contains a forbidden bit, ignore this index.
• Otherwise, set \text{reach} to \max(\text{reach}, i + A_i).

If we are able to reach position N using this process, a path exists; otherwise it does not.

This allows us to check a fixed bit in \mathcal{O}(N), thus making the whole algorithm run in \mathcal{O}(20\cdot N).

# TIME COMPLEXITY:

\mathcal{O}(20\cdot N) per testcase.

# CODE:

Setter's code (C++)
// ਹਰਅਸੀਸ ਸਿੰਘ

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
#define ff                              first
#define ss                              second
#define infinity                        8999999999999999999
#define sz(v)                           ((int)(v).size())
#define all(v)                          (v).begin(),(v).end()
#define MOD_DEFINE                      const int MOD = 1e9 + 7;
#define endl                            '\n'
#define int                             long long
#define pii                             pair<int, int>
#define vi                              vector<int>
#define pb(n)                           push_back((n))
#define mii                             map<int, int>
#define umii                            unordered_map<int, int>
#define l(var, initial, final)          for(int var=initial; var < final; var++)
#define cout                            std::cout
#define cin                             std::cin
#define pqb                             priority_queue<int>
#define pqs                             priority_queue<int, vi, greater<int>>
#define fps(x, y)                       fixed<<setprecision(y)<<x
typedef long long ll;
typedef vector<pii> vpii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void prn() { }
template<typename T1, typename T2> istream &operator >> (istream& in, pair<T1, T2> &a){in >> a.ff >> a.ss; return in;}
template<typename T1, typename T2> ostream &operator << (ostream& out, pair<T1, T2> a){out << a.ff << ' ' << a.ss; return out;}
template<typename T, typename T1> T amax(T &a, T1 b){if(b > a) a = b; return a;}
template<typename T, typename T1> T amin(T &a, T1 b){if(b < a) a = b; return a;}
template<typename T> istream& operator>>(istream &in, vector<T> &v) { for (auto &x : v) in >> x; return in;}
template<typename T> ostream& operator<<(ostream &out, vector<T> &v) {out << "{ "; for (auto &x : v) out << x << " "; out << "}\n"; return out;}
template<typename T, typename... Args> void prn(T x, Args... args) {cout << x << " "; prn(args...);}
template<typename Iterable> void prnIter(const Iterable& ITER, ostream&out = cout){ auto x = ITER.begin(); out << "{ "; for (; x != ITER.end(); ++x) out << *x << ' '; out << "}" << endl;}

MOD_DEFINE

bool traverse(int bit, const vector<bool> &safe, const vector<int> &in){
int n = in.size();

if(((in[0] >> bit) & 1) or ((in.back() >> bit) & 1)){
return false;
}

int R = in[0];

int mx = 0;
for(int cur = 0; R < n - 1; cur = R + 1, R = mx){

for(int i = cur; i <= R; i++){
if(((in[i] >> bit) & 1) or !safe[i]) continue;

amax(mx, i + in[i]);
}
if(mx <= R){
return false;
}
}
return true;
}
void slv(){
int n; cin >> n;
vector<int> in(n); cin >> in;

vector<bool> safe(n, true);
vector<bool> f(32, true);

if(!traverse(31, safe, in)){
cout << -1 << endl; return;
}
for(int bit = 31; bit >= 0; bit--){
// try to keep bit off
if(traverse(bit, safe, in)){
f[bit] = 0;

for(int i = 0; i < n; i++){
if((in[i] >> bit) & 1) safe[i] = false;
}
}
}
int ans = 0;
for(int i = 0; i < 32; i++){
if(f[i])
ans += (1 << i);
}
cout << ans << endl;
}

int32_t main(){

ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int T = 1;

cin >> T;
for(int t = 1; t <= T; t++){
// cout << "Case #" << T << ": ";
slv();
}
return 0;
}
/*
*think brute force first.
*try proving the algorithm on pen n paper first.
*floating point precision errors ?
*implementation too lengthy ? logic might be incorrect.
*/

Tester's code (C++)
// Jai Shree Ram

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
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 readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

int solve(){
static int sum_n = 0;
sum_n += n;
assert(sum_n <= 5e5);

if(n == 1){
cout << a[0] << endl;
return 0;
}

vector<int> suff(n + 1,0);
if((a[0] | a[n - 1]) & mask) return false;
suff[n - 1] = 1;
for(int i = n - 2; i >= 0; i--){
int dp = 0;
if((a[i] & mask) == 0) {
int l = i + 1, r = min(n - 1, i + a[i]);
if(suff[l] > suff[r + 1]) dp = 1;
}
suff[i] = suff[i + 1] + dp;
}
return suff[0] > suff[1];
};
int comp = 0, ans = 0;
bool possible = false;
for(int i = 21; i >= 0; i--){
int temp = comp + (1 << i);
if(check(temp)){
possible = true;
comp = temp;
}else{
ans += (1 << i);
}
}
if(!possible) ans = -1;
cout << ans << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
while(t--){
solve();
}
return 0;
}

Editorialist's code (Python)
def check(a, mask):
if (a[0] & mask) != a[0]: return False
if (a[-1] & mask) != a[-1]: return False
reach = a[0]
for i in range(1, n):
if i > reach: return False
if (a[i] & mask) == a[i]: reach = max(reach, i + a[i])
return True

for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for bit in reversed(range(21)):
if check(a, ans + (1 << bit) - 1): continue
else: ans += 1 << bit
if check(a, ans): print(ans)
else: print(-1)

1 Like

Editorialist code is wrong (python one which is provided)

Oh you’re right, I changed it a bit while testing and pasted the wrong code in.
Should be fine now.

thank u

Couldn’t get your idea . Can you pleaase elaborate on the idea.
We have to take the bitwise or of every index value how so ever isnt it?

Thanks for this great editorial.

Thanks for the editorial. For anyone who didn’t understand the c++ editorial code, refer to the python code it’s much easy to follow after reading the approach. After reading the editorial, I was trying to implement the soln without looking at the code, and I had many failed attempts trying to do that.

Trying to understand why ans|((1<<bit)-1) would work was kinda counter-intuitive, so putting it in my own words here for others like me.

KEY TAKEAWAY after many failed attempts

int mask = INT_MAX ^ (1 << bit); // XORing with INT_MAX will set the current bit as 0 and others as 1

the above mask did not work because the bits before bit are also set to 1, when in reality any bit
higher than the current one is assumed to be forbidden and therefore should be 0,
unless we cannot reach the end without it being set to 1.
whether we can reach the end or not is given by works function. SO,

int mask = ans | ( (1<<bit) - 1 );

above mask will set any necessary forbidden bits to 1 and all the bits lower than bit to 1