The problem statement is-Eve is a beginner stand-up comedian. Her first show gathered a grand total of two spectators: Alice and Bob.
Eve prepared a1+a2+a3+a4 jokes to tell, grouped by their type:
type 1: both Alice and Bob like them;
type 2: Alice likes them, but Bob doesn't;
type 3: Bob likes them, but Alice doesn't;
type 4: neither Alice nor Bob likes them.
Initially, both spectators have their mood equal to 0. When a spectator hears a joke he/she likes, his/her mood increases by 1. When a spectator hears a joke he/she doesn't like, his/her mood decreases by 1. If the mood of a spectator becomes negative (strictly below zero), he/she leaves.
When someone leaves, Eve gets sad and ends the show. If no one leaves, and Eve is out of jokes, she also ends the show.
Thus, Eve wants to arrange her jokes in such a way that the show lasts as long as possible. Help her to calculate the maximum number of jokes she can tell before the show ends.
Here is the problem link - https://codeforces.com/problemset/problem/1792/B
I have spent quite some time over this problem, but I am not able prove some observations formally in this problem. I get that it is always optimal to select the type 4 operation in the last and type 1 operation in the first it is intuitively clear, however how do I show this formally? I was thinking on using some exchange arguments but wasn't able to construct the argument. Moreover, what should be the strategy to maximize the number of jokes? Thanks