EVIL_INF - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: wuhudsm
Tester & Editorialist: iceknight1093

DIFFICULTY:

2723

PREREQUISITES:

Simple dynamic programming, basic data structure knowledge — for example sets

PROBLEM:

N people order takeout, the i-th person’s order will be ready at time X_i and he will arrive to collect it at time Y_i. X_i \lt Y_i is known.
Each person will:

  • Take his order if it’s present.
  • If his order is not present but some others are, take whichever present order has the lowest index.
  • Do nothing if no orders are present.

An evil person is one who takes an order that isn’t his.
A devil can steal exactly one person’s order. What’s the maximum possible number of evil people?

EXPLANATION:

The main observation required to solve this problem is the following: at any moment of time, at most one order (that should be present at this time) will be missing.

Proof

Suppose the devil steals person i's order that’s supposed to be ready at time X_i; and the person arrives at time Y_i.
Then,

  • At any time before X_i, everything is as it should be
  • At times in the range [X_i, Y_i-1], almost everything is as it should be: the only difference is that person i's order is missing.
  • At time Y_i:
    • If there are no orders present, nothing happens and person i leaves.
      Note that if the devil hadn’t stolen his order, then in the normal process there would be no orders remaining at the end of this time anyway; which means the process will go on as usual after Y_i and no more orders will be missing.
    • If there is an order present, person i will take it. Suppose he takes order j.
      Then, at times in the range [Y_i+1, Y_j-1], person j's order will be the only one missing (everything else is accounted for, and person i's order would normally have been taken at time Y_i anyway)
  • Continue this process to see that at any instant, at most one order is missing.

Note that in the last case in the above proof, the process during time [Y_i+1, Y_j-1] proceeds exactly the same as if the devil had stolen person j's order initially!
This observation leads us to a solution.

Let \text{take}[i] denote the index of the takeout that person i will take, if his own is missing (and \text{take}[i] = -1 if no such person exists).
Note that since at most one order is missing at any time, \text{take}[i] is uniquely defined.

Now, if the devil steals person i's takeout, it’s easy to see that the people who become angry form a chain, going as i \to \text{take}[i] \to \text{take}[\text{take}[i]] \to \ldots, as long as the next person exists (i.e doesn’t equal -1).

This tells us that we need to compute two things: the \text{take}[i] values for each i, and then the longest chain in them.

Computing take

Let’s attempt to find \text{take}[i].
If person i's takeout is missing, then at time Y_i we know that all remaining takeouts will be of persons j such that X_j \lt Y_i \lt Y_j, i.e, takeouts that were prepared before Y_i but weren’t taken yet.
We want to find the smallest j such that this condition is satisfied, and do so for every i.
If no such j exists, then \text{take}[i] = -1 of course.

Note that the problem constraints guarantee that all the X_i and Y_j are distinct between 1 and 2N, which means something (in fact, exactly one thing) happens at each time instant.
Let’s use that fact to simulate the process nicely:

  • Iterate across time, from 1 to 2N. Also maintain a set of takeouts that haven’t been taken yet, say S.
  • At time t,
    • If there’s an i such that X_i = t, insert i into S.
    • If there’s an i such that Y_i = t, delete i from S.
      Then, (if S is non-empty) \text{take}[i] will be the smallest element of S.

At each time instant, we do only a couple of operations at most.
So, if S were a data structure that allowed us to quickly insert and erase elements, as well as get the smallest element, we’d be done.

There is indeed such a data structure: a set (std::set in C++, TreeSet in Java, Python unfortunately doesn’t have one built-in).
This allows us to insert/delete elements in \mathcal{O}(\log N), and get the minimum element in \mathcal{O}(1).

So, make S a set and simulate the process as mentioned above, for \mathcal{O}(N\log N) runtime.

Finding the longest chain

Once the \text{take}[i] values are known, finding the longest chain is fairly straightforward.

Let \text{dp}[i] be the length of the longest chain if the devil steals person i's takeout.
Then,

  • If \text{take}[i] = -1, we have \text{dp}[i] = 0
  • Otherwise, \text{take}[i] = 1 + \text{dp}[\text{take}[i]]

As long as memoization is used, computing this for every i takes \mathcal{O}(N) time.
The answer is just the maximum of the \text{dp} array.

TIME COMPLEXITY

\mathcal{O}(N \log N) per test case.

CODE:

Author's code (C++) 
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int steal[N],dp[N];

struct Data
{
	int t,num,ty;
	
	Data() {}
	
	Data(int t,int num,int ty):t(t),num(num),ty(ty) {}
	
	friend bool operator<(Data x,Data y)
	{
		return x.t<y.t;	
	}
}d[N]; 

void init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		d[i]=Data(t,i,0);
	}
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		d[n+i]=Data(t,i,1);
	}
	sort(d+1,d+2*n+1);
}

void solve()
{
	int ans=0;
	set<int> S;
	for(int i=1;i<=n;i++) dp[i]=steal[i]=0;
	for(int i=1;i<=n*2;i++)
	{
		if(d[i].ty)
		{
			S.erase(d[i].num);
			if(!S.empty()) steal[d[i].num]=*S.begin();
		}
		else S.insert(d[i].num);
	}
	for(int i=n*2;i;i--)
	{
		if(d[i].ty&&steal[d[i].num])
		{
			dp[d[i].num]=dp[steal[d[i].num]]+1;
			ans=max(ans,dp[d[i].num]);
		}
	}
	printf("%d\n",ans);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init();
		solve();
	}
	
	return 0;
}
Editorialist's code (Python) 
import heapq

for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	
	event = [0]*(2*n + 1)
	take = [-1]*n
	for i in range(n):
		event[x[i]] = i+1
		event[y[i]] = -(i+1)
	
	active = []
	for i in range(1, 2*n+1):
		id = abs(event[i]) - 1
		if event[i] > 0:
			heapq.heappush(active, (id, y[id]))
		else:
			while active:
				if active[0][1] <= i: heapq.heappop(active)
				else: break
			if active: take[id] = active[0][0]
	dp = [0]*n
	for i in reversed(range(1, 2*n+1)):
		id = abs(event[i]) - 1
		if event[i] < 0:
			if take[id] != -1: dp[id] = 1 + dp[take[id]]
	print(max(dp))
2

Can anyone tell me what is wrong with this approach ?

1  2  4  7
3  5  6  8

the first order will always be stolen or taken by the intended person

check if the person can steal the order of next person if he can set it as true else false

check[i] = y[i-1]>x[i];

by this logic making a check array
(check[i] = if this order can be taken by other person)
check[0] = false(always)

now for the above given case

1  2  4  7
3  5  6  8

check[0] = false (always);
check[1] = true (3>2)
check[2] = true (5>4)
check[3] = false (6<7)

check = [f t t f]

now find longest chain of trues that will be final ans


#include <iostream>
#include <bits/stdc++.h>


using namespace std;

#define ll          long long
#define vi          vector<int>
#define vll         vector<ll>
#define pll         pair<ll, ll>
#define pii         pair<int, int>
#define ld          long double
#define ff          first
#define ss          second
#define vs          vector<string>
#define vpll        vector<pll>
#define vb          vector<bool>
#define mp          make_pair
#define pb          push_back
#define endl        '\n'
#define takeinput(arr,n)    for(int i = 0;i<n;i++)cin>>arr[i];
#define print(arr)  for(int i =0;i<arr.size();i++){cout<<arr[i]<<" ";cout<<endl;}


void solve()
{
    int n;
    cin>>n;
    vector<int>x(n);
    vector<int>y(n);
    vector<bool>check(n,false);
    takeinput(x,n);
    takeinput(y,n);
    
    for(int i = 1;i<n;i++)
    {
        if(y[i-1]>x[i])check[i] = true;
    }
    int temp = 0;
    int ans = 0;
    for(int i = 0;i<n;i++)
    {
        if(check[i] == true)temp++;
        else temp = 0;
        ans = max(ans,temp);
        
    }
    cout<<ans<<endl;
    
}
    
int main() {
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }



	
}