PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Rahim Mammadli
Tester: Jatin Yadav
Editorialist: Istvan Nagy
DIFFICULTY:
Medium-Hard
PREREQUISITES:
minimum cost flow, merge sort tree, Johnson’s algorithm
PROBLEM:
There is a game played on a one-dimensional axis. N stones will appear on this axis. Each of these stones is described by three numbers x_i, t_i, c_i, meaning the stone will appear at a point x_i, at time t_i, and has a value c_i.
There are p players initially (at time 0) all at the point 0. If a player is at a point x at time t, then at time t+1, he/she can be either at x or at x+1. A player is able to pick up a stone with value c_i if he/she is at the point x_i at the time t_i. Picking up a stone does not take any time. Each stone can be picked up at most once.
The score of a player is defined as the sum of values of stones he/she has picked up. The score of a number of players is simply the sum of their individual scores. Devise a strategy for the players to gain the maximum total score.
You should find the maximum possible total score for each number of players p between 1 and K inclusive.
EXPLANATION
Subtask 1 (T\leq 15, N \leq 15): can be solved with O(3^N + 2^N*K) complexity per test case, where dp[bitmask] stores minimum number of players needed to cover stones to the corresponding to the bitmask.
Subtask 2 (K = 1): also can be solved with dynamic programming:
Sorting stones by their (x_i, t_i) value. We can pick up the j-th stone after i-th stone iff
-
x_j>x_i
-
t_j-x_j \geq t_i-x_i
We can maintain an increasing map with the (t-x) keys. When we add the i-th stone:
- find the largest key which is not greater than (t_i-x_i) in the map:
- prev = map[key]
- we can assign map[t_i-x_i] = max(map[t_i-x_i], prev + c_i)
- we can correct/remove the (key, value) pairs from the map to preserve the increasing property of the map
The map last entry value is the answer.
Subtask 3 (\sum_t N \leq 200 , \sum_t N*K \leq 4000 ): Build the following flow graph :
Create two nodes for every stone one in node and one out node and add a directed edge from the in node to the out node with capacity=1 and $cost=-c$. Add e-th edge from the i-th stone out node to the j-th stone in node if the j-th stone can be taken after the i-th stone. Assign capacity 1, and cost = 0 to this edge. Run K iterations of max flow min cost, with Bellman-Ford.
This subtask solution time complexity : O(K * N * N ^ 2) = O(K * N ^ 3).
Subtask 4 (original constraints): We will build a better flow graph and also will use merge sort tree.
- Create two nodes for every stone the same way as in the previous subtask.
- Connects all in node with its corresponding out node as in the previous subtask.
- Sorting stones according to their (x_i, t_i) value
- We can pick up the j-th stone after i-th stone iff
- x_j>x_i
- t_j-x_j \geq t_i-x_i
- Just store (t-x) for every stone, and build a merge sort tree by divide and conquer.
- At each recursion step (layer) there will be a left and right side.
- At every layer create two new node one for the left and one for the right side.
- On the left side add a directed edge from every stone out node to the newly created node.
- On the right side add a directed edge from the newly created right node to the right side stones in nodes.
- Also for the newly created entries on the left side connect the j entry with j+1 with \infty capacity, in the order they are sorted.
- Do the same for the right side also
- Every entry on the left side connect it to the first entry on the right side with a greater or equal (t-x) value.
The graph will have N*log(N) edges. Run K iterations of max flow min cost, with Bellman-Ford we would get : O(N ^ 2 * log^2(N)*K), we can use here the Johnson’s algorithm as a speed up to O(N * log^2(N)*K) .
TIME COMPLEXITY:
O(N * log^2(N)*K) per test case
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define mt make_tuple
#define MAX (int)(5*pow(10,4) + 5)
ll inf = 1e14;
ll INF = pow(10,9);
ll modulo = 998244353;
double eps = 1e-10;
#define MM (int)(3*pow(10,6) + 10)
#define MN (int)(pow(10,6) + 10)
template<class T>
bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
// following mcmf is taken from USACO
int flow[MM*2], cap[MM*2], hd[MN], nx[MM*2], to[MM*2], cost[MM*2];
ll pi[MN], d[MN];
int p[MN];
int vis[MN];
struct MCF//MN = nodes, MM = edges [assume edges one-directional]
{
public:
int N, M, S, T;
void inithd(){
memset(hd, -1, sizeof hd);
M = 0;
}
void adde1(int a, int b, int ca, int co)
{
nx[M]=hd[a], hd[a]=M;
to[M]=b, cost[M]=co, cap[M]=ca, flow[M] = 0;
M++;
}
void adde(int a, int b, int ca, int co){
adde1(a, b, ca, co);
adde1(b, a, 0, -co);
}
void init(int n, int s, int t){
N = n, S = s, T = t;
}
void setpi(){
fori(N){
pi[i] = 1;
}
ll n = N;
vector<ll> in(n, 0);
fori(M){
if(cap[i]){
in[to[i]]++;
}
}
vector<ll> bfs;
fori(n){
if(!in[i]){
bfs.pb(i);
pi[i] = 0;
}
}
fori((int)bfs.size()){
ll a= bfs[i];
for(ll j = hd[a]; ~j; j = nx[j]){
if(!cap[j]){
continue;
}
int b = to[j];
--in[b];
pi[b] = min(pi[b], pi[a] + cost[j]);
if(!in[b]){
bfs.pb(b);
}
}
}
/*
cout<<"after topo "<<endl;
fori(N){
cout<<pi[i]<<' ';
}
cout<<endl;
*/
}
struct state
{
public:
int n;
ll d;
bool operator > (state o) const {return d > o.d;}
};
void dijk()
{
std::priority_queue<state, std::vector<state>, std::greater<state> > q;
memset(p, -1, N * sizeof p[0]);
memset(vis, 0, N * sizeof vis[0]);
fori(N){
d[i] = inf;
}
d[S] = 0;
q.push({S, 0});
for(int n;!q.empty();)
{
n = q.top().n; q.pop();
if(vis[n]) continue;
vis[n]=1;
for(int id=hd[n];~id;id=nx[id])
{
if(cap[id] - flow[id] <= 0) continue;
int x = to[id];
ll w = cost[id] + pi[n] - pi[x];
if(ckmin(d[x], w+d[n]))
p[x]=id, q.push({x, d[x]});
}
}
}
ll mincost(ll F)
{
ll C=0;
while(F>0)
{
dijk();
if(d[T] == inf)
return 0;
ll c = d[T] + pi[T] - pi[S], f = F;
for(int x=T;x!=S;x=to[p[x]^1])
ckmin(f, (ll)cap[p[x]]-flow[p[x]]);
C += c*f;
for(int x=T;x!=S;x=to[p[x]^1])
{
flow[p[x] ] += f;
flow[p[x]^1] -= f;
}
F -= f;
for(int i=0;i<N;++i){
pi[i] += d[i];
}
}
return C;
}
void clearAll(){
M = 0;
fori(N){
hd[i] = -1;
}
}
};
int nodenum[MAX];
int lef[MAX];
int rig[MAX];
int node;
void divConq(ll l, ll r, vector<pair<ll,ll> >& a, vector<pair<ll,ll> >& b, MCF& mcmf){
if(l >= r){
return;
}
ll mid = (l+r)/2;
divConq(l, mid, a, b, mcmf);
divConq(mid+1, r, a, b, mcmf);
for(ll i = l; i<=mid; i++){
nodenum[i] = node;
ll hd = a[i].ss;
mcmf.adde(rig[hd], node, 1, 0);
++node;
}
for(ll i = mid+1; i<=r; i++){
nodenum[i] = node;
ll hd = a[i].ss;
mcmf.adde(node, lef[hd], 1, 0);
++node;
}
for(ll i = mid+1; i<=r-1; i++){
mcmf.adde(nodenum[i], nodenum[i+1], INF, 0);
}
ll pt = mid+1;
for(ll i = l; i<=mid; i++){
while(pt <= r && a[pt].ff < a[i].ff){
++pt;
}
if(pt <= r){
// cout<<"we added edge from original "<<a[i].ss+1<<" to "<<a[pt].ss+1<<endl;
mcmf.adde(nodenum[i], nodenum[pt], 1, 0);
}
}
ll pt1 = l, pt2 = mid+1;
pt = l;
while(pt<=r){
if(pt1 > mid){
b[pt] = a[pt2];
++pt2;
}
else if(pt2 > r){
b[pt] = a[pt1];
++pt1;
}
else if(a[pt1].ff <= a[pt2].ff){
b[pt] = a[pt1];
++pt1;
}
else{
b[pt] = a[pt2];
++pt2;
}
++pt;
}
for(ll i = l; i<=r; i++){
a[i] = b[i];
}
}
ifstream in;
ofstream out;
// #define cin in
// #define cout out
void deal(){
MCF mcmf;
mcmf.inithd();
ll tests;
cin>>tests;
while(tests--){
node = 1;
ll n, k;
cin>>n>>k;
vector<vector<ll> > all;
fori(n){
ll xi, ti, ci;
cin>>xi>>ti>>ci;
if(ti - xi >= 0){
all.pb(vector<ll>({xi, ti, ci}));
}
}
n = all.size();
sort(all.begin(), all.end());
vector<pair<ll, ll> > arr(n);
fori(n){
arr[i] = mp(all[i][1] - all[i][0], i);
}
ll s1 = node;
++node;
ll s2 = node;
++node;
ll t = node;
++node;
fori(n){
lef[i] = node;
++node;
rig[i] = node;
++node;
mcmf.adde(s2, lef[i], 1, 0);
mcmf.adde(rig[i], t, 1, 0);
mcmf.adde(lef[i], rig[i], 1, -all[i][2]);
}
vector<pair<ll,ll> > b(n);
divConq(0, n-1, arr, b, mcmf);
mcmf.adde(s1, s2, k, 0);
mcmf.init(node, s1, t);
mcmf.setpi();
ll ans = 0;
fori(k){
ans-=mcmf.mincost(1);
cout<<ans<<'\n';
}
mcmf.clearAll();
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
deal();
}
Tester's Solution
If you have other approaches or solutions, let’s discuss in comments.