Hi Codeforces community!
I'm just reaching out to see if anyone could help me model a max flow solution. I'm preparing for Code Jam Round 2, and was looking at Round 2 2017 problem B (https://code.google.com/codejam/contest/5314486/dashboard#s=p1). And while I'm aware that it's not the large test case solution, for educational purposes it caught my eye in the editorial that this problem could be modelled and solved with max flow for the small test case bounds. I've been struggling with it for a while, max flow is also pretty new to me, I can easily model a graph that would implement the restriction of each ticket only being used once, or each customer only taking a single seat on each ride, but I can't seem to model a graph that takes both into account.
Also I'm assuming the solution would use binary search right? Or is there a way to maybe assign costs to the solution so that a max flow min cost algorithm could also minimize the amount of rides needed?
Thank you in advance!
Just going to attempt a single bump with this, if it doesn't work so be it :). Thanks in advance if anyone can give a helping hand
EDIT. This is wrong, ignore please.
I can only think of having a source node $$$s$$$, two customer nodes $$$c1, c2$$$, $$$M$$$ ticket nodes, $$$N$$$ seat nodes and a sink one $$$t$$$. There are edges from $$$s$$$ to $$$c1, c2$$$ of infinite capacity. From each ticket-vertex $$$M_i$$$ there are capacity 1 edges to each seat-node that is less or equal than ticket one. From each seat-node there are edges of capacity $$$K$$$ to the sink. If there exists flow of value $$$M$$$ then one can satisfy condition in at most $$$K$$$ rides. The parameter $$$K$$$ is binary searched. I don't know how to find the minimum number of promotions with just max flow, but I could think of introducing costs to ticket-seat edges: an edge connecting ticket with its seat has cost $$$0$$$ and cost $$$1$$$ if it connects to a seat that has a smaller number (is in the front of a roller coaster). However, there are too many edges in this solution and min cost max flow has pretty terrible time complexity.
EDIT. This is wrong, ignore please.
In fact, this is still just max flow solution. You first find the minimum $$$K$$$ only with max flow (ignoring costs) algorithm and binary search and then run some bellman-ford algorithm to deal with negative cycles. The biggest problem is that there are up to $$$2000$$$ nodes and $$$1000^2$$$ edges. Perhaps, there is a better model.
EDIT. This is wrong, ignore please.
Number of vertices and edges can be reduced. Get rid of ticket-nodes. Now, $$$(s, c_i)$$$-edges have capacity equal to the number of tickets of each customer. There are only $$$M$$$ edges of type $$$(c_i, n_i)$$$ with each having capacity equal to number of tickets with seat $$$n_i$$$ customer $$$c_i$$$ has bought. From each seat-node $$$n_i$$$ there is an edge to node $$$n_{i - 1}$$$ (of infinite capacity?).
Hey! Thank you so much for replying.
I'm thinking that another way of reducing the nodes is realizing that each ride will only ever have 2 seats taken (as there are only 2 customers) so you can maybe reduce the number of seats to 3 or 4 or something like that and prune the rest? Haven't thought it through completely yet, also because I wanted to make my following point:
Though I may just have missed how it's handled what you were thinking about was very similar to what I did, but I don't think it handles the constraint of each customer not being able to take the same ride more than once. Wouldn't a testcase which has a single customer with let's say 5 tickets for seats 1 through 5 pass a max flow with K = 1? As it would just assign the same customer to all 5 seats
Consider a graph with $$$2 * N + 2$$$ nodes, with $$$N$$$ being the number of seats. It looks like a bipartite graph but has two special nodes source $$$s$$$ and sink $$$t$$$. For each seat $$$n_i$$$ compute how many tickets with this seat each customer has and call it $$$f(c_i, n_i)$$$.
There are $$$N$$$ edges of type $$$(s, n_i)$$$ each having capacity $$$f(c_1, n_i)$$$ and cost $$$0$$$.
There are $$$N$$$ edges of type $$$(N + n_i, t)$$$ each having capacity $$$f(c_2, n_i)$$$ and cost $$$0$$$.
For each pair $$$(i, j)$$$ such that $$$i \ne j$$$ there is an edge $$$(n_i, N + n_j)$$$ having infinite capacity and cost $$$0$$$. For each pair $$$(i, i)$$$ with $$$i \gt 1$$$ there is an edge $$$(n_i, N + n_i)$$$ with infinite capacity and cost $$$1$$$. There is no edge $$$(1, N + 1)$$$ as you can't promote seat $$$1$$$.
Output cost of this network as the minimum number of promotions. Output $$$FLOW + (M - 2\cdot FLOW) = M - FLOW$$$ as the minimum number or rides. Each flow unit corresponds to some pair, that is, decreases number of tickets to be considered by $$$2$$$. Each flow unit corresponds to one ride. Consequently, $$$FLOW$$$ is the number of rides with both customers being on the roller coaster and $$$M - 2\cdot FLOW$$$ is the number of rides with only one of them being present. As minimizing number of rides is your priority you first try to maximize the number of pairings.
Forget about my other solution though...
Ahh awesome! Thank you so much, that's really educational.
So basically you abstracted the problem into one of Maximum Cardinality Bipartite Matching (but with increased weights instead of making several nodes per seat ticket), taking advantage of there only being two customers to try and match their tickets instead of the route we were both going originally that tried to model the whole large test set as a max flow problem, and then just assuming constraints would be too large for the runtime. I like it!
And then you add a cost to matching two tickets with the same seat, and then after doing the Maximum Matching you simply add the leftover tickets as single rides.
Awesome, thank you so much sheaf, if you ever need help for something in the future I hope I can repay the favour :). I'll try and implement it now and post a link to my submission if I get it to work
Here is a working implementation for the small test case using the above approach: https://pastebin.com/PLiNnUew. Only runs a bit slowly on one or two of the test cases and does the rest pretty instantly. Thanks once again for putting in the time to solve this with max flow!