PROBLEM LINK:
Author: Kushal Goel
Tester: Radoslav Dimitrov
Editorialist: William Lin
DIFFICULTY:
Simple
PREREQUISITES:
Brute Force, Greedy
PROBLEM:
There are 4 movies. We should assign each one of the 4 showtimes to a different movie. We should also assign each one of the 4 prices to a different movie. There are N requests, each one with a movie and a showtime, meaning that a person will watch the movie if it has that showtime. For each movie, if nobody watches that movie, $100 will be lost. Find the maximum profit.
QUICK EXPLANATION:
Check each possible assignment for the showtimes of the movies. We can find the maximum answer for a movie-showtime assignment by finding the number of views of each movie and greedily assigning lower prices to the movies with fewer views.
EXPLANATION:
First, we will map the movie types into integers from 0 to 3 and we will do the same thing for showtimes.
In the input, we are given N requests, but it is somewhat useless to store them as a list. Instead, let’s calculate a frequency matrix f_{i, j}, which means the number of requests with movie i and showtime j. We can find this matrix by iterating over the requests and incrementing the corresponding element in the matrix.
Then, we somehow need to be able to process each possible assignment for a showtime to a movie. Define an array p, such that we will pair movie i with showtime p_i. We are given that each showtime can only correspond to one movie, which means that all elements of p are distinct, so p is a permutation.
Using some method described in the implementation section below, we will iterate through all permutations p, which will give us all possible assignments.
How do we check a particular assignment? We still need to assign the prices. We could do the same thing for the prices, iterating through another permutation, but instead, we can assign the prices greedily.
Notice that given p, we can determine the number of views for each movie, and let that be f2_i. Since movie i has showtime p_i, f2_i=f_{i, p_i}.
To get the best possible profit, we should sort the movies by f2, and assign the least viewed movie with price 25, the second least viewed movie with price 50, and so on. This is known as the Rearrangement Inequality.
Lastly, remember to subtract 100 for each movie such that f2_i=0.
Once we find the answer for each p, we just choose the maximum.
IMPLEMENTATION
One of the relatively harder parts of this solution to implement is iterating over all permutations.
To start with, we can use 4 nested for loops, each one iterating over the range from 0 to 3, and adding if statements to make sure that the elements in the permutation are distinct.
Code
int p[4];
for(p[0]=0; p[0]<4; ++p[0]) {
for(p[1]=0; p[1]<4; ++p[1]) {
//make sure p[1] is distinct
if(p[1]==p[0])
continue;
for(p[2]=0; p[2]<4; ++p[2]) {
//make sure p[2] is distinct
if(p[2]==p[0]||p[2]==p[1])
continue;
for(p[3]=0; p[3]<4; ++p[3]) {
//make sure p[3] is distinct
if(p[3]==p[0]||p[3]==p[1]||p[3]==p[2])
continue;
//process the permutation p
}
}
}
}
This works, but is a bit hard to write. What if we wanted to loop over permutations of length 10? Do we use 10 nested for loops? What if the length of the permutation n is given in the input?
We can replace the nested for loops with recursion instead. They pretty much do the same thing, except that it’s more concise.
Code
int n=4, p[n];
void dfs(int i=0) {
if(i>=n) {
//we have filled in all p[i]
//process the permutation p
} else {
for(p[i]=0; p[i]<n; ++p[i]) {
//make sure p[i] is distinct
bool ok=1;
for(int j=0; j<i&&ok; ++j)
ok=p[j]!=p[i];
if(ok) {
//move on to the next index
dfs(i+1);
}
}
}
}
dfs();
Now comes the power of standard libraries. In C++, there is a function called next_permutation(), which, given a permutation, basically returns the lexiciographically smallest permutation greater than the given one.
Using this function, we can write an easier implementation (and this is what I used).
Code
int n=4, p[n];
//initialize the permutation
iota(p, p+n, 0);
//iterate through all permutations
do {
//process the permutation p
} while(next_permutation(p, p+n));
There also easy ways to implement iterating over all permutations in Python. Check the setter’s code or the tester’s code for more details.
SOLUTIONS:
Setter's Solution
netsum=0
from itertools import permutations as per
for _ in range(int(input())):
n=int(input())
dic={}
for __ in range(n):
a,b=input().split()
if (a,b) not in dic:
dic[(a,b)]=1
else:
dic[(a,b)] += 1
best = - (10**3)
for p in list(per(['A','B','C','D'])):
profit = 0
lc=[]
for tup in zip(p,['12','3','6','9']):
lc.append(dic.get(tup,0))
if lc[-1]==0:
profit-=100
lc=sorted(lc)
pr=25
for x in lc:
profit+=pr*x
pr+=25
best=max(best,profit)
print(best)
netsum+=best
print(netsum)
Tester's Solution
import sys
import itertools
def read_line():
return sys.stdin.readline().split()
s = 0
T = int(read_line()[0])
for i in range(T):
n = int(read_line()[0])
cnt = {}
for j in range(n):
a, b = read_line()
if cnt.get((a, b)) == None:
cnt[(a, b)] = 1
else:
cnt[(a, b)] += 1
best = -(10 ** 18)
for p in list(itertools.permutations(['A', 'B', 'C', 'D'])):
cand = 0
li = []
for t, f in zip(['12', '3', '6', '9'], p):
li.append(cnt.get((f, t), 0))
if li[-1] == 0:
cand -= 100
li = sorted(li)
pr = 25
for x in li:
cand += pr * x
pr += 25
best = max(best, cand)
print(best)
s += best
print(s)
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t, n, f[4][4], p[4], f2[4], tans;
//returns ID from 0 to 3
int getMovieID(char c) {
return c-'A';
}
int getShowtimeID(int x) {
return x/3-1;
}
void solve() {
//input
cin >> n;
//clear frequency matrix
memset(f, 0, sizeof(f));
//find the frequencies
for(int i=0; i<n; ++i) {
char c;
int x;
cin >> c >> x;
++f[getMovieID(c)][getShowtimeID(x)];
}
int ans=-1e9;
//initialize the permutation
iota(p, p+4, 0);
//iterate through all permutations
do {
//assign movie i to showtime p[i]
//new frequency array for the movies
for(int i=0; i<4; ++i)
f2[i]=f[i][p[i]];
int ca=0;
//by the rearrangement inequality, sort the frequency array and assign higher prices to movies which have more views
sort(f2, f2+4);
for(int i=0; i<4; ++i)
ca+=(i+1)*25*f2[i];
//find empty movies
for(int i=0; i<4; ++i)
if(!f2[i])
ca-=100;
//update ans
ans=max(ca, ans);
} while(next_permutation(p, p+4));
//output
cout << ans << "\n";
tans+=ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--)
solve();
//output
cout << tans;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 
.I push-backed all possible 24 combinations to a 2d-vector 
