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:
-
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.
-
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;
}