GCOEN - Editorial

PROBLEM LINK:

Practice
Contest
Author: Pratik
Tester: Arjun
Editorialist: Pratik

DIFFICULTY:

MEDIUM .

PREREQUISITES:

Greedy, DP etc.

PROBLEM:

There is going to be a major fair in Government College Of Engineering Nagpur – GCOEN Named as Adhyaaya . In which there are many events going to happen. There are nn numbers of events you can attend. You know its starting and ending days and the amount of money you could win in the event.But the condition is that you can attend only one event in a day. Tell the maximum amount of money you will win.

EXPLANATION:

In the given test case, There are 4 events in which you can participate

  • first event will start on day 2 and end on day 4
  • second event will start on day 3 and end on day 6
  • Third event will start on day 6 and end on day 8
  • Fourth event will start on day 5 and end on day 7

So, first event and third , first event and fourth event are the only 2 events whose days are not co-inciding. [2,4] && [6,8] and [2,4] && [5,7] respectively.
if we add prizes of 2 events , we will get prize of (4+2 = 6) in first condition and (4+3 =7) in second condition, so we will print max of them i.e 7 .

SOLUTION

Setter's Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin >> n;
map<int,int> compress;
vector a(n),b(n),p(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> p[i];
b[i]++;
compress[a[i]], compress[b[i]];
}

int coords = 0;
for (auto&v : compress) {
v.second = coords++;
}

vector<vector<pair<int,int>>> project(coords);
for (int i = 0; i < n; i++) {
project[ compress[b[i]] ].emplace_back( compress[a[i]], p[i] );
}

vector dp(coords, 0);
for (int i = 0; i < coords; i++) {
if (i > 0) {
dp[i] = dp[i-1];
}
for (auto p : project[i]) {
dp[i] = max(dp[i], dp[p.first]+p.second);
}
}
cout << dp[coords-1] << endl;
}

Tester's Solution

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define vll vector
#define ld long double
#define pll pair<ll,ll>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define oset tree<int, null_type, less, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
const int MOD=1000000007;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp
temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n;
ll a[n],b[n],p[n];
map<ll,ll> pnt;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i]>>p[i];
b[i]++;
pnt[a[i]]=0;
pnt[b[i]]=0;
}
ll cnt=0;
for(auto&it:pnt)
{
it.S=cnt;
cnt++;
}
vector<vector > v(cnt);
for(int i=0;i<n;i++)
{
v[pnt[b[i]]].PB({pnt[a[i]],p[i]});
}
vll dp(cnt,0);
for(int i=0;i<cnt;i++)
{
if(i>0)
{
dp[i]=dp[i-1];
}
for(auto it:v[i])
{
dp[i]=max(dp[i],dp[it.F]+it.S);
}
}
cout<<dp[cnt-1];
}