Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Holi and Cultural Festival problem solution

YASH PAL, 31 July 2024
In this HackerEarth Holi and Cultural Festival problem solution A cultural festival is going to be organized in Hacker Society on the day of Holi .The head of the society needs some Poets ,Dancers and some Musicians to perform in this event. He decides to interview N number of people who live in the society. Each one has ratings in all the three fields. He wants to choose right guys for the right job so that the festival can be celebrated in the best possible way.Thus he selects P Poets,D Dancers and M Musicians. Help him in organizing the event.
The strength of Cultural Festival is the sum of ratings of the people in the corresponding field. You have to maximize the sum of their ratings.
HackerEarth Holi and Cultural Festival problem solution

HackerEarth Holi and Cultural Festival problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct edge
{
ll to,rev,cost,fl,cap;
};
vector<edge>v[3010];
ll n,prog[3010],webd[3010],dist[3010],curflow[3010],fans,cans,w,p,m,market[3010];
bool mark[3010];
pair<ll,ll>par[3010];
void add_edge(ll fr,ll to,ll cap,ll cost)
{
v[fr].push_back({to,(int)v[to].size(),cost,0,cap});
v[to].push_back({fr,(int)v[fr].size()-1,-cost,0,0});
}
ll spfa(ll src,ll dest)
{
ll i,j,k;
queue<ll>q;
for(i=1;i<=3007;i++)
{
mark[i]=curflow[i]=0;
dist[i]=1e10;
}
curflow[src]=1e10;
dist[src]=0;
mark[src]=1;
q.push(src);
while(!q.empty())
{
j=q.front();
q.pop();
mark[j]=0;
for(i=0;i<v[j].size();i++)
{
ll to=v[j][i].to;
ll idx=v[j][i].rev;
ll cst=v[j][i].cost;
ll cap=v[j][i].cap;
if(cap<=0||dist[to]<=cst+dist[j])
continue;
curflow[to]=min(curflow[j],cap);
dist[to]=cst+dist[j];
par[to]={j,i};
if(!mark[to])
{
q.push(to);
mark[to]=1;
}
}
}
return curflow[dest];
}
ll augment(ll src,ll dest,ll flow)
{
for(ll i=dest;i!=src;i=par[i].first)
{
edge &temp=v[par[i].first][par[i].second];
edge &rev=v[i][temp.rev];
temp.cap-=flow;
temp.fl+=flow;
rev.cap+=flow;
rev.fl-=flow;
}
return 1LL*dist[dest]*flow;
}
void min_cost_max_flow(ll src,ll dest)
{
ll temp;
while(temp=spfa(src,dest))
{
cans+=augment(src,dest,temp);
fans+=temp;
}
}
int main()
{
freopen("in00.txt","r",stdin);
freopen("out00.txt","w",stdout);
ll i,j,k,src,sink,wb,pg,mr;
cin>>n>>w>>p>>m;
src=n+1;
sink=n+2;
wb=n+3;
pg=n+4;
mr=n+5;
for(i=1;i<=n;i++)
{
cin>>webd[i];
add_edge(i,wb,1,-webd[i]);
}
for(i=1;i<=n;i++)
{
cin>>prog[i];
add_edge(i,pg,1,-prog[i]);
}
for(i=1;i<=n;i++)
{
cin>>market[i];
add_edge(i,mr,1,-market[i]);
}
for(i=1;i<=n;i++)
{
add_edge(src,i,1,0);
}
add_edge(wb,sink,w,0);
add_edge(pg,sink,p,0);
add_edge(mr,sink,m,0);
min_cost_max_flow(src,sink);
cout<<abs(cans)<<"n";
return 0;
}

Second solution

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

#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }

const long long INF = 99999999;

// min cost max flow code source -> spaghetti source
struct graph {
typedef int flow_type;
typedef int cost_type;
struct edge {
int src, dst;
flow_type capacity, flow;
cost_type cost;
size_t rev;
};
vector<edge> edges;
void add_edge(int src, int dst, flow_type cap, cost_type cost) {
adj[src].push_back({src, dst, cap, 0, cost, adj[dst].size()});
adj[dst].push_back({dst, src, 0, 0, -cost, adj[src].size()-1});
}
int n;
vector<vector<edge>> adj;
graph(int n) : n(n), adj(n) { }

pair<flow_type, cost_type> min_cost_max_flow(int s, int t) {
flow_type flow = 0;
cost_type cost = 0;

for (int u = 0; u < n; ++u) // initialize
for (auto &e: adj[u]) e.flow = 0;

vector<cost_type> p(n, 0);

auto rcost = [&](edge e) { return e.cost + p[e.src] - p[e.dst]; };
for (int iter = 0; ; ++iter) {
vector<int> prev(n, -1); prev[s] = 0;
vector<cost_type> dist(n, INF); dist[s] = 0;
if (iter == 0) { // use Bellman-Ford to remove negative cost edges
vector<int> count(n); count[s] = 1;
queue<int> que;
for (que.push(s); !que.empty(); ) {
int u = que.front(); que.pop();
count[u] = -count[u];
for (auto &e: adj[u]) {
if (e.capacity > e.flow && dist[e.dst] > dist[e.src] + rcost(e)) {
dist[e.dst] = dist[e.src] + rcost(e);
prev[e.dst] = e.rev;
if (count[e.dst] <= 0) {
count[e.dst] = -count[e.dst] + 1;
que.push(e.dst);
}
}
}
}
} else { // use Dijkstra
typedef pair<cost_type, int> node;
priority_queue<node, vector<node>, greater<node>> que;
que.push({0, s});
while (!que.empty()) {
node a = que.top(); que.pop();
if (a.snd == t) break;
if (dist[a.snd] > a.fst) continue;
for (auto e: adj[a.snd]) {
if (e.capacity > e.flow && dist[e.dst] > a.fst + rcost(e)) {
dist[e.dst] = dist[e.src] + rcost(e);
prev[e.dst] = e.rev;
que.push({dist[e.dst], e.dst});
}
}
}
}
if (prev[t] == -1) break;

for (int u = 0; u < n; ++u)
if (dist[u] < dist[t]) p[u] += dist[u] - dist[t];

function<flow_type(int,flow_type)> augment = [&](int u, flow_type cur) {
if (u == s) return cur;
edge &r = adj[u][prev[u]], &e = adj[r.dst][r.rev];
flow_type f = augment(e.src, min(e.capacity - e.flow, cur));
e.flow += f; r.flow -= f;
return f;
};
flow_type f = augment(t, INF);
flow += f;
cost += f * (p[t] - p[s]);
}
return {flow, cost};
}
};

const int N = 2005;
int a[N], b[N], c[N], d[N];
int main(){
int n, p, m, d;
cin >> n >> p >> d >> m;
int ans = N * (p + m + d);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) cin >> c[i];

graph g(n + 10);
int src = 0, dst = n + 9;
g.add_edge(src, 1, p, 0);
g.add_edge(src, 2, d, 0);
g.add_edge(src, 3, m, 0);

for(int i = 1; i <= n; i++){
g.add_edge(1, i + 3, 1, N - a[i]);
g.add_edge(i + 3, dst, 1, 0);
}

for(int i = 1; i <= n; i++){
g.add_edge(2, i + 3, 1, N - b[i]);
}

for(int i = 1; i <= n; i++){
g.add_edge(3, i + 3, 1, N - c[i]);
}
pair<int, int> P = g.min_cost_max_flow(src, dst);
assert(P.fst == p + m + d);
printf("%dn", ans - P.snd);
}
coding problems solutions

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes