THEATRE - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

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

18 Likes

My over complicated dp solution: CodeChef: Practical coding for everyone XP

2 Likes

My 500 line AC code :

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

16 Likes

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

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

2 Likes

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

1 Like

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 - CodeChef: Practical coding for everyone
it is somewhat similar to the one by @anon57725588 [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. :slight_smile:

5 Likes

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

1 Like

My All Possible combination solution CodeChef: Practical coding for everyone

legend spotted!!:upside_down_face:

2 Likes

i am unable to understand why i got only 30 points.
please help.
https://www.codechef.com/viewsolution/29711992

Tried to do the same thing but it didn’t pass the test cases ://
@anon57725588
https://www.codechef.com/viewsolution/29513490

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.