 # THEATRE - Editorial

Author: Kushal Goel
Editorialist: William Lin

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;
for(p=0; p<4; ++p) {
for(p=0; p<4; ++p) {
//make sure p is distinct
if(p==p)
continue;
for(p=0; p<4; ++p) {
//make sure p is distinct
if(p==p||p==p)
continue;
for(p=0; p<4; ++p) {
//make sure p is distinct
if(p==p||p==p||p==p)
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

s = 0
for i in range(T):

cnt = {}
for j in range(n):
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, p, f2, 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 18 Likes

My over complicated dp solution: https://www.codechef.com/viewsolution/29512943 XP

2 Likes

My 500 line AC code :

https://www.codechef.com/viewsolution/29478945

16 Likes

Too lazy to think .I push-backed all possible 24 combinations to a 2d-vector  https://www.codechef.com/viewsolution/29512047

2 Likes

can also solved using bfs

1 Like

This question clearly fits Hungarian Algorithm but after making small changes to it to find maximum sum instead of minimum. Only the code for the algorithm is not readily available. It solves in O(n^3)

3 Likes

My Backtracking Solution inspired from NQueens Problem …
https://www.codechef.com/viewsolution/29469462

Recursion Based AC solution
https://www.codechef.com/viewsolution/29777230

Patience level : GOD
Respect++

1 Like

So,I had managed to get 30 points on the problem in last week&totally forgot that I had not received 100 points.Then today morning I looked my rank&it was ~3k.I wondered how come even after solving 5.5 problems it was too low&then saw it.Time was running out since I had to go to college but I came up with 1000 line solution.
https://www.codechef.com/viewsolution/29754824

https://www.codechef.com/viewsolution/29533942

Am i missing something in this python code. Its basically iterating for 4 tables.
Table 1 for 12 PM, Table 2 for 3PM, Table 3 for 6 PM and Table 4 for 9PM.

Then just iterated over table 1 choosing 1 of 16 options,
then over table 2 choosing 1 of remaining 9 options,
then over table 3 for 1 of 4 options left,
then over table 4 for 1 option.
TOTAL iterations each time=576

But it only gave answer for 30 Points. Any help is appreciated

here’s my AC approach - https://www.codechef.com/viewsolution/29646531
it is somewhat similar to the one by @abhishekp97 [I think]

I am not able to figure out why my solution is getting wrong answer for original constraints
https://www.codechef.com/viewsolution/29414615

Time was running out since I had to go to college but I came up with 1000 line solution.

That’s interesting. Its interesting to see what you will do when you have abundant time. 5 Likes

1000 lines code😒
I think you are wasting your time in right sense. 1 Like

My All Possible combination solution https://www.codechef.com/viewsolution/29434899

legend spotted!! 2 Likes

i am unable to understand why i got only 30 points.