# BOOLGAME - Editorial

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

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]){
}
int ptr = 0;

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

// 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
#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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi readVectorInt(lli l,lli r,int n){
vi a(n);
for(int i=0;i<n-1;++i)
return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
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;
while(T--)
{

sumn-=n;
e.clear();e.resize(n,vi(n+1,0));
while(m--)
{
// 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();
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.