Under the Umbrella#13062

Under the Umbrella (Çözgüdiň düşündirişi)

Author of the problem:	Andrii Kholod (Connect)
Prepared by:	Andrii Kholod (Connect)
Editorial:	Andrii Kholod (Connect)

Solution

Suppose that we want to save squirrel $i$ .

If the left endpoint of the umbrella is at position $p$ , then squirrel $i$ is protected if

$p \leq x_{i} \leq p + w .$ p \le x_i \le p+w.

Therefore,

$x_{i} - w \leq p \leq x_{i} .$ x_i-w \le p \le x_i.

At the same time, the umbrella must always stay completely between the first and the last squirrel, so

$x_{1} \leq p \leq x_{n} - w .$ x_1 \le p \le x_n-w.

Hence, whenever squirrel $i$ must be protected, the left endpoint of the umbrella must belong to the interval

$I_{i} = [max (x_{1}, x_{i} - w), min (x_{n} - w, x_{i})] .$ I_i= [\max(x_1,x_i-w),\min(x_n-w,x_i)].

Now consider two squirrels $i$ and $j$ which must be protected at times $t_{i}$ t_i and $t_{j}$ t_j.

The minimum distance between their allowed intervals is

$dist (I_{i}, I_{j}) = max (0, ∣ x_{i} - x_{j} ∣ - w) .$ \operatorname{dist}(I_i,I_j) = \max(0,|x_i-x_j|-w).

Since the umbrella can move by at most one coordinate unit per unit of time, these two requirements are compatible if and only if

$max (0, ∣ x_{i} - x_{j} ∣ - w) \leq ∣ t_{i} - t_{j} ∣.$ \max(0,|x_i-x_j|-w)\le |t_i-t_j|.

Equivalently, they are incompatible if

$∣ x_{i} - x_{j} ∣ > w + ∣ t_{i} - t_{j} ∣.$ |x_i-x_j|>w+|t_i-t_j|.

An important fact is that checking every pair of requirements is sufficient.

Suppose that every pair of requirements is compatible. For every requirement $k$ , let its allowed interval be $[L_{k}, R_{k}]$ [L_k,R_k] and its time be $t_{k}$ t_k.

Consider the function

$f (t) = max_{k} (L_{k} - ∣ t - t_{k} ∣) .$ f(t)=\max_k(L_k-|t-t_k|).

Every function inside the maximum changes with speed at most $1$ , so $f$ also changes with speed at most $1$ .

For every requirement $j$ , obviously

$f (t_{j}) \geq L_{j} .$ f(t_j)\ge L_j.

From pairwise compatibility, for every $k$ we also have

$L_{k} - R_{j} \leq ∣ t_{k} - t_{j} ∣.$ L_k-R_j\le |t_k-t_j|.

Therefore,

$L_{k} - ∣ t_{j} - t_{k} ∣ \leq R_{j},$ L_k-|t_j-t_k|\le R_j,

and hence

$f (t_{j}) \leq R_{j} .$ f(t_j)\le R_j.

Thus,

$f (t_{j}) \in [L_{j}, R_{j}]$ f(t_j)\in[L_j,R_j]

for every requirement.

If necessary, we can additionally clamp $f (t)$ to the interval $[x_{1}, x_{n} - w]$ [x_1,x_n-w]. This does not increase its speed and does not change its value at any requirement outside the allowed range.

Therefore, all pairwise compatible requirements can be satisfied simultaneously.

So we can build a graph on the squirrels.

Two squirrels are connected by an edge if there exist two nut falls, one affecting the first squirrel and one affecting the second squirrel, such that these two requirements are incompatible.

Then a set of squirrels can be saved simultaneously if and only if it is an independent set in this graph.

Thus, the problem is reduced to finding a maximum independent set in a graph with at most $44$ vertices.

Now let us construct this graph efficiently.

First, sort all falls by time and merge all falls having the same time into one bitmask.

While processing times from left to right, let $l a s t_{i}$ last_i be the latest time at which squirrel $i$ was affected by a fall.

Suppose the current time is $t$ , and squirrel $j$ is affected now.

For another squirrel $i$ , among all previous falls affecting $i$ , it is enough to consider only the latest one.

Indeed, the latest fall has the smallest time difference with $t$ , so it gives the strongest restriction. If it is compatible with the current fall, then all earlier falls are also compatible.

Let the latest fall affecting squirrel $i$ happen at time $l a s t_{i}$ last_i.

Then squirrels $i$ and $j$ are incompatible if

$∣ x_{i} - x_{j} ∣ > w + (t - l a s t_{i}) .$ |x_i-x_j|>w+(t-last_i).

For fixed $i$ , all currently affected squirrels which conflict with it are outside the interval

$[x_{i} - (w + t - l a s t_{i}), x_{i} + (w + t - l a s t_{i})] .$ [x_i-(w+t-last_i),x_i+(w+t-last_i)].

Since the coordinates $x_{i}$ x_i are sorted, we can find the borders of this interval using binary search and add all conflicting squirrels using bitmasks.

After processing all times, we obtain the incompatibility graph.

Now we need to find a maximum independent set in a graph with $n \leq 44$ n\le44.

We use meet-in-the-middle.

Split the vertices into two parts of sizes at most $22$ .

For every subset $ma s k$ of the second half, let $b es t [ma s k]$ best[mask] be the maximum size of an independent set contained inside this subset.

Take any vertex $v$ from $ma s k$ .

There are two possibilities.

We do not take $v$ :

$b es t [ma s k] = b es t [ma s k ∖ {v}] .$ best[mask]=best[mask\setminus\{v\}].

Or we take $v$ . Then all its neighbors must be removed:

$b es t [ma s k] = 1 + b es t [(ma s k ∖ {v}) ∖ N (v)] .$ best[mask] = 1+ best[(mask\setminus\{v\})\setminus N(v)].

We take the maximum of these two values.

Now enumerate every subset of the first half.

For each subset, we check whether it is independent.

If it is independent, we find all vertices of the second half which are adjacent to at least one chosen vertex. These vertices cannot be used.

Then we add the best independent set among all remaining vertices of the second half.

Taking the maximum over all subsets of the first half gives the answer.

The time complexity of constructing the graph is $O (q lo g q + q n lo g n)$ O(q\log q+qn\log n).

The meet-in-the-middle part works in $O (2^{n /2})$ O(2^{n/2}).

The total time complexity is

$O (q lo g q + q n lo g n + 2^{n /2}) .$ O(q\log q+qn\log n+2^{n/2}).

The memory complexity is $O (q + 2^{n /2})$ O(q+2^{n/2}).

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;
const int MASK = (1<<22);

struct fall_event {
    ll t;
    ull mask;
};

ll x[50] , lastt[50];

ull gr[50];

int g2[25];
int banMask[MASK];
int bestMask[MASK];
int goodMask[MASK];

signed main() {
    speed;

    ll n , q , w;

    cin>>n>>q>>w;

    for (int i = 1 ; i<=n ; i++) cin>>x[i];

    vector<fall_event> ev;

    ev.reserve(q);

    for (int z = 0 ; z<q ; z++) {
        ll t , l , r;

        cin>>t>>l>>r;

        ll L = lower_bound(x+1 , x+n+1 , l)-x;
        ll R = upper_bound(x+1 , x+n+1 , r)-x-1;

        ull mask = 0;

        if (L <= R) {
            ll len = R-L+1;

            mask = ((1ULL<<len)-1)<<(L-1);
        }

        ev.pb({t , mask});
    }

    sort(ev.begin() , ev.end() , [](fall_event A , fall_event B) {
        return A.t < B.t;
    });

    for (int i = 1 ; i<=n ; i++) {
        lastt[i] = -1;
    }

    ull all = (1ULL<<n)-1;

    for (int z = 0 ; z<q ; ) {
        int j = z;

        ll t = ev[z].t;

        ull cur = 0;

        while(j < q && ev[j].t == t) {
            cur |= ev[j].mask;
            j++;
        }

        if (cur) {

            for (int i = 1 ; i<=n ; i++) {
                if (cur&(1ULL<<(i-1))) {
                    lastt[i] = t;
                }
            }

            for (int i = 1 ; i<=n ; i++) {
                if (lastt[i] == -1) continue;

                ll dist = w+t-lastt[i];

                ll L = lower_bound(
                    x+1 , x+n+1 , x[i]-dist
                )-x;

                ll R = upper_bound(
                    x+1 , x+n+1 , x[i]+dist
                )-x;

                ull bad = 0;

                if (L > 1) {
                    bad |= (1ULL<<(L-1))-1;
                }

                if (R <= n) {
                    bad |= all^((1ULL<<(R-1))-1);
                }

                gr[i] |= cur&bad;
            }
        }

        z = j;
    }

    for (int i = 1 ; i<=n ; i++) {
        for (int j = 1 ; j<=n ; j++) {
            if (gr[i]&(1ULL<<(j-1))) {
                gr[j] |= (1ULL<<(i-1));
            }
        }
    }

    int n1 = n/2;
    int n2 = n-n1;

    int all2 = (1<<n2)-1;

    for (int v = 0 ; v<n2 ; v++) {
        g2[v] = (gr[n1+v+1]>>n1)&all2;
    }

    int sz2 = (1<<n2);

    bestMask[0] = 0;

    for (int mask = 1 ; mask<sz2 ; mask++) {
        int v = __builtin_ctz(mask);

        int rest = mask^(1<<v);

        int take =
            rest&(~g2[v])&all2;

        bestMask[mask] = max(
            bestMask[rest],
            1+bestMask[take]
        );
    }

    ll ans = bestMask[all2];

    goodMask[0] = 1;
    banMask[0] = 0;

    int sz1 = (1<<n1);

    for (int mask = 1 ; mask<sz1 ; mask++) {
        int v = __builtin_ctz(mask);

        int prev = mask^(1<<v);

        goodMask[mask] =
            goodMask[prev] &&
            ((gr[v+1]&(ull)prev) == 0);

        banMask[mask] =
            banMask[prev] |
            ((gr[v+1]>>n1)&all2);

        if (!goodMask[mask]) continue;

        int can =
            all2&(~banMask[mask]);

        ans = max(
            ans,
            (ll)__builtin_popcount(mask)
            +(ll)bestMask[can]
        );
    }

    cout<<ans<<endl;

    return 0;
}

C++