Really cool, we did the first part but couldn't figure out how to actually do the queries in time.

What if the optimal solution required people from left_group and right_group to live in the same home?

Find all bitmasks that represent valid house assignments. Then use fast subset transform to OR "polynomials" of these bitmasks till you get the polynomial which has all bits 1 mask present. Answer is number of times you had to use FST+1. Complexity n^2*2^n

It be like that

This is really cool. I tried establishing connections between k and k+1, never thought there would exist something between k and 2k.

I mean that consider the graph you get as $$$G=(X+Y, E)$$$. Creating this graph and then getting $$$X$$$ and $$$Y$$$ is easy in $$$O(N+M)$$$ and since $$$O(M) = O(N)$$$ the result is $$$O(N)$$$. Now using Hall's Theorem you can say that the maximum bipartite matching will have a size of $$$min(|X|,|Y|)$$$. You don't need the actual coverings.

As for why Hall's theorem is applicable, assume $$$X$$$ to be the smaller set with LOG. We can use induction on the size $$$A$$$ where $$$S$$$ is a subset of $$$X$$$. The base case is trivial, there must be one edge from the $$$S$$$. Now, notice that whenever we add a another node to this subset, it must add at least one new node to the neighborhood. Therefore, the proof is complete.

Why must it add at-least one node? Well, I haven't been able to prove that part yet but I'm pretty sure it's related to being the smaller set.

Using hall's theorem you can show that the maximum matching set will have the same size as the smaller of the two bipartite sets. So you don't actually need to solve the flow problem.

All cells are node. Edges between adjacent cells. You get a bipartite graph. Find the largest matching in it.

All cells are node. Edges between adjacent cells. You get a bipartite graph. Find the largest matching in it.

There are infinite guests. Read the question correctly, I made the same mistake.Not just 0 and 1 but every integer from -inf to +inf. You've to ensure that after shifting, everyone goes into a unique room.

It seems to be correct and is exactly what I did. My implementation is a little over complicated but if you can check it out in my submissions and it was accepted.

Yes. That's what kinda what I did. I found an euler tour that also ran through all the edges.

You can't log in to m1/m2/m3 sites with a google account because of which I couldn't submit for the first 15 minutes.

Got it. Thanks a lot, that helped!

So assume that the question said instead of 11 degrees the polynomial is 2 degrees only. Then the polynomial interpolated from above info is 1 — 2x + x^2, again obviously wrong. Maybe, it will give the correct value of zero when taken MOD 1e6+3 but I don't find in intuitively clear.

my bad. But the point stands? The function could be changed.

In problem E, how can we be sure that the value of f(xi) that we use to interpolate the polynomial is actually the value of the polynomial or less than the actual value because of MOD 1e6 + 3

For example, if the polynomial is 1 + (1e6+1)x + x^2, f(0) = 1, f1(1) = 1e6+2, f(2) = 2e6 + 7 MOD 1e6 + 3 = 1. Now the polynomial we interpret will be wrong.

sorting?