THEATRE - Editorial


Div-2 Contest

Author: Kushal Goel
Tester: Radoslav Dimitrov
Editorialist: William Lin




Brute Force, Greedy


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.


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.


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.


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.

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
		for(p[2]=0; p[2]<4; ++p[2]) {
			//make sure p[2] is distinct
			for(p[3]=0; p[3]<4; ++p[3]) {
				//make sure p[3] is distinct
				//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.

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)
			if(ok) {
				//move on to the next index

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).

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.


Setter's Solution
from itertools import permutations as per
for _ in range(int(input())):
    for __ in range(n):
        if (a,b) not in dic:
            dic[(a,b)] += 1

    best = - (10**3)
    for p in list(per(['A','B','C','D'])):
        profit = 0
        for tup in zip(p,['12','3','6','9']):
            if lc[-1]==0:
        for x in lc:

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
            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)
    s += best
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() {
	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;

	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)
		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)
		//find empty movies
		for(int i=0; i<4; ++i)
		//update ans
		ans=max(ca, ans);
	} while(next_permutation(p, p+4));

	cout << ans << "\n";

int main() {

	cin >> t;

	cout << tans;

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:


My over complicated dp solution: XP


My 500 line AC code :


Too lazy to think :sob:.I push-backed all possible 24 combinations to a 2d-vector :rofl::stuck_out_tongue:


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)


My Backtracking Solution inspired from NQueens Problem …

Recursion Based AC solution

Patience level : GOD

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.

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 -
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

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. :slight_smile:


1000 lines code😒
I think you are wasting your time in right sense.:joy:

1 Like

My All Possible combination solution

legend spotted!!:upside_down_face:


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

Tried to do the same thing but it didn’t pass the test cases ://

Please listen to me what I did in THEATRE.

Created permutations and for each permutation, checked each permutation and then for each test case for each permutation for each permutation I checked the profit and printed.

I don’t know if that makes sense to you but I was quite sleepy when I solved it and it worked because it should.

The sample output was wrong though. It was missing a 0 AFAIR.