There is simple undirected graph with n vertices and m edges. ( N<=10 , m<=n*(n-1)/2 ) At most how many edges can we pick so that in graph with n vertices and edges we picked, degree of every vertices is equal or less than P. ( P <= n-1 )
I know this problem is about bitmask dp but i cant figure out dp-state.
Is there any hint or similar problem in codeforces or atcoder?
Here's a very very rough sketch, but it should, for the most part, works. It would be quite a pain to implement though.
Divide the graph into two parts. For simplicity, let's assume n = 10. Then there would be at most sz1 * (n — sz1) edges between the two sides. Iterate through all possible subsets of those edges, we would have the problem reduced to f1(lim1, lim2, ..., lim(sz1)) * f2(lim(sz1 + 1), lim(sz1 + 2), .., lim10) where f1 represents the way of choosing edges in the first side such that deg[1] <= lim1, deg[2] <= lim2, ..., and similar for f2 but in the second side and with nodes (sz1 + 1) — 10. Getting the states can be done in O(1) per mask if you use backtrack, as it's possible to modify from a mask m to m ^ (1 << bit) and back in O(1).
Iterate through all subsets of edges which lie completely in each parts to figure out g1(deg1, deg2, ..., deg(sz1))/g2(deg(sz1 + 1), deg(sz1 + 2), ..., deg10) where g is basically what f is except you replace the <= sign with the = sign. Then f1 and f2 are prefix sums of g1 and g2, which can be calculated in O((2 * (sz1 — 1))^sz1) ((sz1 — 1)^sz1 states, and 2^sz1 operations per state).
Assuming sz1 >= n — sz1, this works in O(2^(sz1 * (n — sz1) + 2^(sz1 * (sz1 — 1) / 2) + (2 * (sz1 — 1))^sz1) (probably * sz1 as well since the states we access are of size sz1). I think choosing sz1 = 6 would be optimal, resulting in something which runs in ~1 sec, which should work for most of the time. Of course, this is only slightly better than sz1 = 5 (i.e. dividing into two parts of equal size), but I figure you might appreciate some optimization considering that this already seems very tight.
There are probably some cheeses (for example, devising an independent solution for complete graph cases, allowing us to reduce the runtime of certain parts by ~2), but I'm not good enough to figure them out. It should obviously be noted that this is a very bad solution, and while you can take it in for consideration, using it would probably be a bad idea.
Sorry for misleading question in advance Should be changed to "at most how many edges can we pick so ..."
And thank you for sharing your approach. I will try dividing graphs
Auto comment: topic has been updated by p__ce1052 (previous revision, new revision, compare).