BOOLGAME - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Authors: Tushar Gautam , Shubham Jain
Editorialist: Shubham Jain
Tester: Aryan Choudhary

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Brute force, Dynamic Programming

PROBLEM:

You are given N binary variables x_1, x_2, ... x_N. Setting the variable x_i to 1 gives you some reward g_i, and setting all the variables in some special contiguous ranges (u_i, v_i) to 1 gives you reward d_i. Both g_i and d_i can be possibly negative. Find the K largest rewards that you can obtain out of all possible assignments.

QUICK EXPLANATION:

Store the K largest rewards for the pairs (position, position where the last zero was observed). Thus, you store K possible rewards at N^2 pairs. Take the max K values of the pairs (N,i), 0 \leq i \leq N.

EXPLANATION:

As the quick explanation hints, we store the max K largest rewards for the pairs (position, last zero). Let us have vectors dp[i][j], which store the K largest values when we are at the position i, and the last zero we observed was at position j. For convenience, we add a position 0 at the start, and keep our dp 1-indexed. Thus, we first initialize dp[0][0] with a single value of 0.

There are two cases:

  1. x_i is set to 1, and the last position at which we observed a zero, j, is such that j < i. In this case, we can directly update dp[i][j] by looking at the K largest values of dp[i-1][j]. However, we need to also add some additional values that come with making this decision: we need to add g[i] (because we decided to make this position’s value 1), and rewards of all the intervals (k,i) such that k > j. We can do this by maintaining a pointer and updating it as we iterate over j.

  2. x_i is set to 0, and thus the last position at which we observed a zero, j, is such that j = i. In this case, we can take the max K values over all dp[i-1][j], 0 \leq j \leq i-1.

The setter’s code explains this with helpful comments. Time complexity is O(N*(N+M)*K).

For the subtasks, when N \leq 18 you could iterate over all the 2^{18} assignments, and when K = 1 you could write the above dp calculating only the best assignment (and thus, dp would be an int instead of a vector).

SOLUTIONS:

Setter's Solution
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

int main(){
	fastio;

	int tests;
	cin>>tests;

	while(tests--){

		int n, m, k;
		cin >> n >> m >> k;
		long long int g[n+1];
		vector<pair<int, long long int>> reward[n+1];

		// 1-indexed for easy handling of edge cases

		for(int i = 1; i <= n; i++){
			cin >> g[i];
		}
		for(int i = 1; i <= m; i++){
			int u, v;
			long long int d;
			cin >> u >> v >> d;
			// add reward information at right end
			reward[v].push_back(make_pair(u, d));
		}

		for(int i = 1; i <= n; i++){
			sort(reward[i].begin(), reward[i].end());
		}

		vector<long long int> dp[n+1][n+1];
		dp[0][0].push_back(0);

		for(int i = 1; i <= n; i++){
			
			// first, handle the case where current value is 1
			// we need just to take the max K values from dp[i-1][j]
			// and update those values with extra reward added

			long long int rew_added = g[i];
			for(auto & r: reward[i]){
				rew_added += r.second;
			}
			int ptr = 0;

			for(int j = 0; j < i; j++){
				while(ptr < reward[i].size() && reward[i][ptr].first <= j){
					rew_added -= reward[i][ptr].second;
					ptr++;
				}
				for(auto & r : dp[i-1][j]){
					dp[i][j].push_back(rew_added + r);
				}
			}

			// the case where current value is 0
			// take max K values across dp[i-1][j], 0 <= j <= i-1

			for(int j = 0; j <= i-1; j++){
				for(auto & r : dp[i-1][j]){
					dp[i][i].push_back(r);
				}
			}
			sort(dp[i][i].begin(), dp[i][i].end(), greater<long long int>());
			while(dp[i][i].size() > k){
				dp[i][i].pop_back();
			}
		}

		vector<long long int> final_vals;
		for(int i = 0; i <= n; i++){
			for(auto & r : dp[n][i]){
				final_vals.push_back(r);
			}
		}

		sort(final_vals.begin(), final_vals.end(), greater<long long int>());

		for(int i = 0; i < k; i++){
			cout << final_vals[i] << " ";
		}

		cout << endl;
	}

	return 0;
}
Tester's Solution
/* in the name of Anton */
 
/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
 
#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif
 
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
 
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
 
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
 
long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}
 
vi readVectorInt(lli l,lli r,int n){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}
 
const lli INF = 0xFFFFFFFFFFFFFFFL;
 
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
 
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}
 
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}
 
bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
 
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
 
    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    vector<vi> e;
 
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
const lli ten9=1e9;
lli sumn=60;
T=readIntLn(1,10);
while(T--)
{
 
    n=readIntSp(1,sumn);
    sumn-=n;
    m=readIntSp(1,min(1000LL,n*(n-1)/2));
    k=readIntLn(1,min(200LL,1LL<<n));
    a=readVectorInt(-ten9,ten9,n);
    e.clear();e.resize(n,vi(n+1,0));
    while(m--)
    {
        lli u=readIntSp(1,n)-1,v=readIntSp(u+2,n)-1,w=readIntLn(-ten9,ten9);
        // assert(e[u][v]!=-1);
        e[v][u+1]=w;
        dbg(u,v,w);
    }
 
    for(int i=0;i<n;++i)
    for(int j=i;j>=0;--j)
        e[i][j]+=e[i][j+1];
    vector<vi> best;
    best.pb({0});
    for(int cur=0;cur<n;cur++){
        dbg(e[cur]);
        vector<vi> cbest(cur+2);
        for(lli last=0;last<=cur;++last)
        for(auto x:best[last])
        {
            cbest[cur+1].pb(x);
            dbg(last,cur,e[cur][last+1]);
            cbest[last].pb(x+e[cur][last+1]+a[cur]);
        }
 
        cbest.swap(best);
        for(auto &cbest:best)
        {
            sort(all(cbest));
            reverse(all(cbest));
            if(sz(cbest)>=k)
                cbest.resize(k);
        }
        dbg(cur,best);
    }
 
    vi ans;
    for(auto v:best)
    for(auto x:v)
        ans.pb(x);
 
    sort(all(ans));
    reverse(all(ans));
    ans.resize(k);
    for(auto x:ans)
        cout<<x<<" ";
    cout<<endl;
 
}   aryanc403();
    readEOF();
    return 0;
}
4 Likes

It’s kinda over complicating but this problem can also be solved using Yen’s Algorithm after modelling it into a graph and shifting edge weights. Here’s my submission.

PS - Contest problem links are broken.

2 Likes

isn’t that not supposed to be possible with graphs with negative edges? i did consider this idea

You can shift the edges by 1e9 because you know that total number of edges in each valid path(n).
You can add/subtract it later.

I also thought of this but I thought it won’t work somehow… ok thanks I will look into your submission

Thanks, fixed the links.