Problem: Dont Stop!
Setter: ankit_907
Tester: ronkar
Difficulty:
MEDIUM
Question:
A sudden commencement of unimaginable events unveil Dr. Octavius thrashing cars on the highway like a waste can. Peter Parker being our Friendly Neighbourhood Spiderman puts the lives of people as his utmost priority, and wants to evacuate all the cars on the highway.
There are N traffic signals on the highway where each traffic signal can exhibit 2 colours: Red and Green. The i^{th} signal remains Red only for p_{i} ranges of time and Green otherwise.
There are a lot of cars and he wants all of them to keep moving for the entire T seconds. The cars would move only if all the signals are Green or Peter flags them to keep moving at some instant. For this, Peter can use his web shooter and perform any of the 2 operations some number of times :
- Destroy a certain traffic signal permanently(thereby making it non-existent),
- Distract Dr. Octavius at some specific time instant t, and flag the cars to continue moving for that very instant(irrespective of the signals’ color).
Find the minimum number of operations Peter should perform to safely evacuate all the cars.
Two arrangements are considered different if there exists at least one position where their values are not the same in both the arrangements.
Quick Explanation:
The solution to the problem requires one to map the i^{th} signal with the time instants they are RED on. The answer to the problem would be the minimum vertex cover of the formed bipartite graph .
Detailed Explanation:
The first thing which we should realize are the available options with us :
- Destroy a certain traffic signal
- Make a certain time instant inconsiderate.
The 2 things in consideration over here are related to each other since we can draw a mapping between the signals and the time instants they are RED on. The formed mapping is bipartite in nature !
The 2 set of nodes of the graph are time instants and the i^{th} signal. The edge connecting them would be weighted 1 if there exists a mapping between them. Now, according to the question : We must select some nodes from the graph such that the selected nodes contain all the edges’ at least 1 endpoint.
This is called minimum vertex cover of a graph. According to Konig’s Theorem, the min vertex cover of any bipartite graph is equal to its maximum matching. Hence , all we have to do now is to find the max matching of the graph !
The max matching can be found by finding the Max Flow of the given bipartite graph. We can take use of the fact that all the edges of the graph are of max weight 1. Hence we can use Dinic’s Algorithm to find its answer in a much efficient way.
Time Complexity
The Time Complexity for each test case would be O(E*sqrt(V)).
Here, the max value of E=N*T and the max value of V=2*max(N,T)+2.
Therefore the worst case time complexity goes as : O(N*T*sqrt(2*N)) which well passes our time constraints .
Setter's Code
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
using namespace std;
#define ll long long
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>ordered_set;
// using namespace chrono;
#include<bits/stdc++.h>
#define F first
#define S second
#define lld long double
#define vc vector<ll>
#define pb push_back
#define all(a) a.begin(),a.end()
const int MOD=(1e9 +7);
// const ll inf=(1000000000000000000);
typedef pair<ll,ll> pairs;
#define varval(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
inline ll mod(ll a){
return (a-MOD*(a/MOD));
}
ll power(ll a, ll b){ll res=1;a=mod(a);while(b>0){if(b&1){res=mod(res*a);b--;}a=mod(a*a);b>>=1;}
return res;}
struct edge {ll x, y, cap, flow;};
struct DinicFlow {
// *** change inf accordingly *****
const ll inf = (1e18);
vector <edge> e; vc cur, d;
vector<vc > adj; ll n, source, sink;
DinicFlow() {}
DinicFlow(ll v){ n=v; cur=vc (n+1);
d = vc (n+1); adj = vector<vc >(n+1);}
void addEdge(ll from, ll to, ll cap) {
edge e1 = {from, to, cap, 0};
edge e2 = {to, from, 0, 0};
adj[from].push_back(e.size()); e.pb(e1);
adj[to].pb(e.size()); e.pb(e2); }
ll bfs(){ queue <ll> q;
for(ll i = 0; i <= n; ++i) d[i] = -1;
q.push(source); d[source] = 0;
while(!q.empty() and d[sink] < 0) {
ll x = q.front(); q.pop();
for(ll i = 0; i < (ll)adj[x].size(); ++i){
ll id = adj[x][i], y = e[id].y;
if(d[y]<0 and e[id].flow < e[id].cap){
q.push(y); d[y] = d[x] + 1;
} } } return d[sink] >= 0; }
ll dfs(ll x, ll flow) { if(!flow) return 0;
if(x == sink) return flow;
for(;cur[x] < (ll)adj[x].size(); ++cur[x]){
ll id = adj[x][cur[x]], y = e[id].y;
if(d[y] != d[x] + 1) continue;
ll pushed = dfs(y,min(flow,e[id].cap-e[id].flow));
if(pushed){ e[id].flow+=pushed;
e[id^1].flow -= pushed; return pushed; }
} return 0; }
ll maxFlow(ll src, ll snk) {
this->source=src;this->sink = snk; ll flow=0;
while(bfs()){ for(ll i=0;i<=n;++i) cur[i]=0;
while(ll pushed=dfs(source,inf))flow+=pushed;
} return flow;
}
void dfs2(int m, vector<bool>& vis){
vis[m] = true;
for(auto id: adj[m]){
if (e[id].flow < e[id].cap && !vis[e[id].y]){
dfs2(e[id].y, vis);
}
}
}
void min_cut(vector<int>& s, vector<int>& t){
vector<bool> vis(n);
dfs2(source, vis);
for(int i = 0; i < n; ++i){
if (i == source || i == sink)
continue;
if (vis[i]){
s.push_back(i);
}
else
t.push_back(i);
}
}
};
int main() {
// your code goes here
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll t,n,i,j,k,f,T,X;
cin>>t;
for(int tc=1;tc<=t;tc++){
cin>>n>>T;
ll N=max(n,T);
DinicFlow U(2 * N + 3);
int src = 2 * N + 1, snk = 2* N + 2;
for(i=1;i<=N;i++){
U.addEdge(src, i, 1);
U.addEdge(i + N, snk, 1);
}
ll p;
for(int i = 1; i <= n; ++i){
cin>>p;
while(p--){
ll l,r;
cin>>l>>r;
while(r>=l){
U.addEdge(i,r + N, 1);
// U.addEdge(i,r , 1);
r--;
}
}
}
cout<<U.maxFlow(src,snk)<<"\n";
}
// cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Hope you enjoyed solving the question !
Do feel free to share your feedbacks, discussing the question in the comments.
You can also head over to our forum AskREC in case of any ambiguites
Thank You !