PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: gheal
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Square-root decomposition
PROBLEM:
N cities lie on a line.
You know binary string a of length N-1, where a_i = 1 if and only if there exists a road between cities i and i+1.
Answer Q queries of the following form:
- Given u, v, K, you’re allowed to build roads of length K, i.e, joining x and x+K for 1 \leq x \leq N-K. Such a road allows for travel between any two cities in this range.
Find the minimum number of such roads that allow you to travel from city u to v.
EXPLANATION:
Let’s try to solve a single query (u, v, K) first.
W.l.o.g let u \leq v, so we’re moving rightwards.
The natural greedy strategy is to move right using existing roads as much as possible, and build a new road if it’s no longer possible then continue on.
It’s fairly easy to see that this greedy strategy is also optimal.
This gives us a solution in \mathcal{O}(N) per query.
Note that it can be improved slightly to \mathcal{O}(\frac{N}{K}) by moving along existing roads quicker: for each i, precompute \text{jump}[i] to be the farthest vertex to the right of i that can be reached using only existing roads - then starting from u you can alternately move to \text{jump}[u] and u+K.
Every two moves increases the distance moved by K+1, so we’ll find the answer in \leq \mathcal{O}(\frac{N}{K}) steps.
If K is large enough (say, K\gt \sqrt{N}), doing this for each query would be fast enough.
For small K however, it’s still too slow, and we need a different strategy.
Let’s use the fact that all queries are known in advance, and solve the problem offline.
Fix a value of K, and we’ll try to answer all queries with this K reasonably quickly.
First, observe that for any query (u, v), we could just as well answer the query (\text{jump}[u], \text{jump}[v]) since it’ll have the same answer.
This simply skips the first and last steps of moving along public roads, which don’t affect the answer anyway.
Now, consider a graph on N vertices, with edges as follows:
- For each i such that \text{jump}[i] = i, add the edge i \to \text{jump}[i+K].
That is, we create a graph on the jump points alone denoting all “forced” movements.
Then, for any \text{jump}[u], if we want to get to \text{jump}[v] the optimal solution (as noted right at the start) is to follow this graph till we reach a vertex that’s \geq \text{jump}[v].
The answer is the number of edges we follow.
Here’s the nice part: this graph is a tree, with vertex N being its root!
Also, for any vertex u of the tree, the N\to u path contains vertices in descending order.
So, for a query (\text{jump}[u], \text{jump}[v]) what we want is really just the lowest ancestor of \text{jump}[u] that’s \geq \text{jump}[v].
This is quite easy to compute quickly: for example, you can use binary lifting, or perform a DFS on the tree and maintain the path to each vertex and then binary search on this path.
Building the tree is linear time, and each query gets processed exactly once (with a log factor).
Finally, simply combine both solutions!
If K \gt \sqrt{N} (or some similarly large constant), do the “brute force” jumping solution, which terminates quickly.
Then, for K = 1, 2, 3, \ldots, \sqrt{N}, answer all queries with such K in \mathcal{O}(N) time total.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\sqrt {N} + Q\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll NMAX=5e5+5;
ll warp[NMAX],p[NMAX],psqrt[NMAX],ans[NMAX];
bool added[NMAX];
vector<ll> edg[NMAX],addedlist;
struct query{
ll u,v,k,id;
}queries[NMAX];
bool operator < (const query& a, const query& b){
if(a.k<b.k) return true;
if(a.k>b.k) return false;
return a.id<b.id;
}
vector<ll> dfsstack;
ll chunk;
void dfs(ll u){
if(dfsstack.size()>=chunk) psqrt[u]=dfsstack[dfsstack.size()-chunk];
else psqrt[u]=NMAX;
dfsstack.push_back(u);
for(auto it : edg[u])
dfs(it);
dfsstack.pop_back();
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ll n,q;
string a;
cin>>n>>q>>a;
a="$"+a;
warp[n]=n;
for(int i=n-1;i>=1;--i){
if(a[i]=='1') warp[i]=warp[i+1];
else warp[i]=i;
}
for(ll i=0;i<q;i++){
cin>>queries[i].u>>queries[i].v>>queries[i].k;
if(queries[i].u>queries[i].v) swap(queries[i].u,queries[i].v);
queries[i].u=warp[queries[i].u];
queries[i].id=i;
}
sort(queries,queries+q);
ll l=0,r=0;
for(ll k=1;k<=n;k++){
l=r;
while(r<q && queries[r].k==k)
r++;
if(k<=150){
for(ll i=l;i<r;i++){
ll u=queries[i].u;
while(!added[u]){
addedlist.push_back(u);
added[u]=1;
if(u+k>n) break;
p[u]=warp[u+k];
edg[warp[u+k]].push_back(u);
u=warp[u+k];
}
}
chunk=sqrt(n/k);
for(const auto& it : addedlist)
if(p[it]==0){
p[it]=n;
dfs(it);
}
for(ll i=l;i<r;i++){
ll u=queries[i].u,d=0;
while(psqrt[u]<queries[i].v) u=psqrt[u],d+=chunk;
while(p[u]<queries[i].v) u=p[u],d++;
ans[queries[i].id]=d+(u<queries[i].v);
}
for(const auto& it : addedlist) added[it]=p[it]=psqrt[it]=0,edg[it].clear();
addedlist.clear();
}
else{
for(int i=l;i<r;i++){
int u=queries[i].u,d=0;
while(u<queries[i].v){
if(u+k<=n) u=warp[u+k];
else u=n;
++d;
}
ans[queries[i].id]=d+(u<queries[i].v);
}
}
}
for(ll i=0;i<q;i++)
cout<<ans[i]<<'\n';
return 0;
}
Tester's code (C++)
// library link: https://github.com/manan-grover/My-CP-Library/blob/main/library.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
#define K 150
#define bl 300
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;
}
I cal(I u,I v,I k,I nx[],I n){
u=nx[u];
I ans=n;
asc(i,0,n){
if(u>=v){
ans=i;
break;
}
u+=k;
if(u>n){
u=n;
}
u=nx[u];
}
return ans;
}
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I n,q;
cin>>n>>q;
S s;
cin>>s;
V(P(P(I,I),I)) qr[n];
I nx[n+1];
nx[n]=n;
dsc(i,1,n){
if(s[i-1]=='1'){
nx[i]=nx[i+1];
}else{
nx[i]=i;
}
}
asc(i,0,q){
I u,v,k;
cin>>u>>v>>k;
qr[k].pb({{min(u,v),max(u,v)},i});
}
I ans[q]={};
asc(i,K,n){
asc(j,0,sz(qr[i])){
ans[qr[i][j].se]=cal(qr[i][j].fi.fi,qr[i][j].fi.se,i,nx,n);
}
}
asc(k,0,K){
if(k>=n || sz(qr[k])==0){
continue;
}
I req[n+1];
I fin[n+1];
I fn=n/bl;
dsc(i,1,n+1){
I b=i/bl;
if(b!=fn){
if(nx[i]/bl!=b){
req[i]=0;
fin[i]=nx[i];
}else{
I v=nx[i]+k;
if(v>n){
v=n;
}
v=nx[v];
if(v/bl!=b){
req[i]=1;
fin[i]=v;
}else{
req[i]=req[v]+1;
fin[i]=fin[v];
}
}
}else{
req[i]=n;
fin[i]=n+1;
}
}
asc(i,0,sz(qr[k])){
I u=qr[k][i].fi.fi;
I v=qr[k][i].fi.se;
I id=qr[k][i].se;
I cnt=0;
while(fin[u]<=v){
cnt+=req[u];
u=fin[u];
}
ans[id]=cnt+cal(u,v,k,nx,n);
}
}
asc(i,0,q){
cout<<ans[i]<<"\n";
}
return 0;
}
Editorialist's code (C++)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n, q; cin >> n >> q;
string s; cin >> s;
vector<int> jump(n+1);
jump[n] = n;
for (int i = n-1; i >= 1; --i) {
if (s[i-1] == '1') jump[i] = jump[i+1];
else jump[i] = i;
}
const int B = 200;
vector<int> ans(q);
vector<vector<array<int, 3>>> queries(B);
for (int i = 0; i < q; ++i) {
int L, R, k; cin >> L >> R >> k;
if (L > R) swap(L, R);
L = jump[L], R = jump[R];
if (L == R) continue;
if (k < B) queries[k].push_back({L, R, i});
else {
while (L < R) {
L = jump[min(L+k, n)];
++ans[i];
}
}
}
vector<vector<array<int, 2>>> q_at(n+1);
vector<basic_string<int>> children(n+1);
vector<int> path;
for (int k = 1; k < B; ++k) {
for (auto [L, R, i] : queries[k]) q_at[L].push_back({R, i});
for (int i = n-1; i >= 1; --i) {
if (jump[i] != i) continue;
int j = jump[min(i+k, n)];
children[j].push_back(i);
}
auto dfs = [&] (const auto &self, int u) -> void {
while (q_at[u].size()) {
auto [v, i] = q_at[u].back();
q_at[u].pop_back();
int lo = 0, hi = path.size()-1;
while (lo < hi) {
int mid = (lo + hi + 1)/2;
if (path[mid] < v) hi = mid-1;
else lo = mid;
}
ans[i] = path.size() - lo;
}
path.push_back(u);
for (int v : children[u]) self(self, v);
path.pop_back();
};
dfs(dfs, n);
for (int i = 1; i <= n; ++i) children[i].clear();
}
for (int x : ans) cout << x << '\n';
}