lets consider theatre to be a matrix of size n*m(n-rows,m-colums) and define adjacent seats to seat s(i,j) as s(i+1,j),s(i-1,j),s(i,j+1),s(i,j-1).Also some 'q' seats are blocked(may be chair is broken in theatre).what is the maximum number seats that u can select with given constraints?? n<=5; m<=1000; q<=m*n
my idea--i represented it as a graph and eliminated the broken seats,but for all connected componets i have find the maximum seats with this condition(but i do not know how?)
any ideas?
My guess would be that some greedy exists, but I can't come up with it on the spot (maybe it doesn't, no clue really)
Your approach is fine. For an arbitrary graph finding the maximum independent set is NP-complete, but the graph produced by a matrix is bipartite (you can color the matrix like a chessboard to see why it is bipartite). For bipartite graphs you can find the maximum independent set using maximum matching https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory). If written well, it should very comfortably pass with the given constraints.
wow nice! but i have a dumb doubt in finding maximum independent set of each connected component.for each component can we just color a node with red and the adjacency list with blue and its adjacency list with red....now we can count how many are colored in red and blue and the max of no of blue and red isn't maximum independent set?I found there exist algo to do it so i am sure i am wrong.could u tell where i was wrong(i could'nt find counter example)
Your suggestion is just equivalent to "take the bigger side of the bipartite graph". This is not optimal (otherwise we'd have a really easy algorithm for bipartite matching!).
Now your graph isn't an arbitrary bipartite graph, it is significantly more restricted. Unfortunately, even in this restricted graph this greedy is not correct.
Consider this case (grey = blocked, red and blue are the coloring of your algorithm):
There are 4 reds and 4 blues — so you would answer 4. However, the optimal answer is 5:
Define dp[i][mask] being the maximum amount of seats you can select in the first i columns such that the seats selected in last column is represented by "mask" (i.e. if mask = 3 = 11 (binary), then seats 0 and 1 have been selected). A mask is valid in a column if it does not contain any pair of adjacent bits or a bit representing a broken seat (i.e. 3 is invalid because it contains bits 0 and 1, and if seat (0, 2) is broken, then mask 1 will be invalid in column 2 because it contains bit 0).
Transitions will be dp[i + 1][new_mask] = max(dp[i + 1][new_mask], dp[i][mask] + __builtin_popcount(new_mask)) for all pairs of valid (mask, new_mask) such that mask and new_mask doesn't share a bit (because you can't select both (i, j) and (i, j + 1)). This runs in O(4^n * m * n), can be easily optimized to O(4^n * m) by precalculating the validity of masks in each column, and to O(3^n * m) by using SOS DP, but with the given limits that presumably is unnecessary.