ANCT - Editorial

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.

2 Likes

Thanks