PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: harasees_singh
Testers: mexomerf, rivalq
Editorialist: iceknight1093
DIFFICULTY:
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.
*read the question again.
*/
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 readStringLn(int l, int r) { return readString(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[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int solve(){
int n = readIntLn(1,5e5);
static int sum_n = 0;
sum_n += n;
assert(sum_n <= 5e5);
vector<int> a = readVectorInt(n,0,5e5);
if(n == 1){
cout << a[0] << endl;
return 0;
}
auto check = [&](int mask){
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
int t = readIntLn(1,1000);
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)