I don't know about 2-CNF. I solved the subtask by this:

For any two shooters in a row that do not have a wall between them, fix their position as VERTICAL. For any two shooters in a column that do not have a wall between them, fix their position as HORIZONTAL. If their is a conflict, answer is not possible. Now their might be some shooters whose position hasn't been fixed till now. We fix them by simply checking if their is any unmarked cell in that row that doesn't have a beam crossing it from any of the fixed shooters. If there is, then we fix the position as HORIZONTAL, else VERTICAL.

At last, we just need to check if all '.' are covered or not.

yes , both subtasks are solvable by 2sat

I didn't pay attention to R <= 5 and I implemented a -fucking massive don't how it's correct code- .

There's nothing messy in this approach. Did you know you can do reflections using ^= 1 and ^= 3 on the direction value?

I wrote the 2-SAT part, but only without mirrors; too bad I didn't have the ~10 minutes necessary to write the mirror part. I agree with Al.Cash, it's simple already.

My solution was indeed an overkill. Let K be the number of beams. Instead of writing linear SCC, we can use O(K³) Floyd-Warshall to get POSSIBLE/IMPOSSIBLE. We can even repeat this O(K) times and determine the boolean values one by one (and avoid topological sort). Only Floyd-Warshall, extremely simple.

Let's iterate over all prefixes of the seats. The number of rides is sufficient iff i * rides >= pref_sum[i] for all i, so we can easily find it. We also need to take into account that the number of rides is not less than the maximum number of tickets per customer. After that, we just need to find the sum of max(seats_count[i] - rides, 0) for all i (we greedily keep all the customers we can and move the rest).

Note: the pref_sum is the prefix sums of seats_count, which is the number of tickets for the i-the seat.

couldn't find a counter example for 30 minutes so just submitted it lol

ignore

When there's a ticket with the i-th people and the j-th seat, connect the i-th left vertex and the j-th right vertex, and construct a bipartite graph. We need to prove the following: when the degree of each (both left and right) vertex is at most K, we can partition the edges into at most K matchings. To do this, repeat the following steps: at each step, find a matching that covers all vertices with maximum degree.

Such matchings always exist: https://math.stackexchange.com/questions/638598/any-bipartite-graph-has-a-matching-that-covers-each-vertex-of-maximum-degree

You may add a fake tickets and now exactly Ans tickets will be sold for each place and nobody will have more than Ans tickets. Make a bipartite graph. Then you may use Hall's theorem and make a perfect (over places) matching starting from all persons with Ans tickets being matched (actually Hall's conditions are enough for default matching algo to never fail a DFS).

Upd. Even simpler you can add fake persons for tickets so every ticket will match Ans persons and then fake seats so every person will have Ans tickets. Now this is a well-known case for decomposition into Ans perfect matchings

I think you can use min cost matching to help. Ordering the matching can be done with bfs (i.e. find any soldier that can reach their turret safely, and repeat).

Wish I had thought of this during contest :(. Probably slightly different from the editorial solution:

Firstly, let us get an upper bound on how many turrets we can shoot. Suppose all turrets do not fire. Then finding how many turrets can be shot is just a matching problem. It turns out that this number is also correct for the original question. We will proceed to construct it.

From the maximum matching, (wlog every soldier is used) we can match each soldier to a turret. For each soldier, fix a path to the intended turret. Along the way, the soldier also enters the line of sight of other turrets, in some order. If a soldier sees 2 turrets simultaneously, break ties arbitrarily. In other words, each soldier has a sequence of turrets T1, T2, ..., Tn such that he may shoot at turret Ti if everything before has been dealt with.

Now, we let all soldiers fire at their respective T1s. This will cause some turrets to be fired at twice. While this is the case, choose a soldier for whom this turret is not the last turret, and assign him his next turret in the sequence instead.

This procedure has to terminate because there are at most 100 turrets per soldier and at most 100 soldiers. It is correct because whenever two soldiers fire at the same turret, one of them has a next turret to fire at.

Implementation wise, since the important thing about the sequence of turrets T1, ... is that you may fire at Ti if everything before has been cleared, we can actually do a BFS from each soldier and add the turrets in order they are seen. Lastly, to ensure the final order of destroying turrets is correct, simply make sure that for each soldier firing at Tk, all turrets Ti for i<k have been destroyed prior. This is --EDIT: not-- doable using toposort (although there are probably faster methods the bounds are small enough for this to not matter).

Edit: Panic! Solution was 'wrong' -- You can't toposort a cycle. For more security, go read the official solution. I'm sorry and will go hide in a cave for now. =(

More detailed explanation + attempted fix (possibly with more sinister logic bugs): Basically, after constructing the sequences of turrets for each soldier, it reduces to the following problem:

Given some sequences of numbers, such that each sequence ends with a different number, rearrange the sequences such that if, from the first sequence onwards, we pick the first number we have yet to pick, we are able to pick 1 number from each sequence (before the sequence ends).

Example: 1, 2, 3 2, 1 1, 2

If we use this order, then we pick 1 from the first sequence, and 2 from the second sequence. We can't pick anything from the third sequence, so this fails. However, if we rearrange the sequences by placing the first sequence at the back, we get 2, 1, 3, and this works.

In a more useful line of thought, we can think of the question as follows: after rearranging the sequences, pick a prefix for each sequence such that the last elements are unique and every non-last term in each sequence is contained in an earlier sequence. This formulation suggests that in a sense, shorter sequences are easier to work with. So we try to reduce the length of sequences while maintaining the property that all sequences end with unique numbers.

Firstly, wlog, let the sequences end with 1 to n. Then if a number greater than n appears in some sequence, then we can truncate the sequence to end with it, while preserving uniqueness of last numbers in the sequences. Thus we may assume that only numbers 1 to n exist.

Since we are working by the hypothesis that a solution exists as long as every sequence ends in a different number, if some sequences are like as follows:

1, 2 2, 3 3, 1

We can truncate the sequences to form {1}, {2} and {3} respectively, retaining the uniqueness of the last numbers in the sequences. More specifically, we imagine a directed graph, where each number from 1 to n is a node. Then we draw an edge from x to y if the sequence ending with x contains y. If there is a cycle, then we can truncate the sequences as described above. If there is no cycle, then we can now do the toposort to retrieve the solution.

I will try my bestest to actually code it out tomorrow, and once again, I'm sorry to anyone who was led astray by my logic.

finds a cave to hide in

Did you copy the wrong solution and resubmit it ?

Last year I got mine in August.

This was discussed already.

Thanks for this! A really nice proof for this problem.

For the reference, the graph anta is talking about is the bipartite graph where customer vertices on the left and seat numbers on the right. We can see that colours can represent rides, since one customer can't have two colours (that would mean one person on the same ride) and one seat can't have two colours (that would mean two of the same seat number on the same ride).

I'm not sure I understood your approach. But if I did, it fails because you assign a ticket to a seat when you promote it. This is wrong. When you promote a ticket, it becomes a flexible ticket, therefore it can't be fixed as you do with not promoted ones. The testcases your code gives incorrect outputs are something like this:

3 3 3
3 1
3 2
2 3

You force customer 1 to seat 3, customer 2 to seat 2, promoting its ticket and customer 3 to seat 1, promoting its ticket aswell. The correct answer would be to let customer 1 and 3 seat in their tickets and promote customer 2 to seat on 1.

But solving only smalls was enough to advance :)