Given a rectangular grid with N rows and M columns. Each its cell is either empty, contains an enemy, or contains a laser. Each laser can shoot in one of three directions: either left, right or up. When a laser shoots at some direction, it kills all the enemies on its way. There’re L lasers on the grid.
You are to determine whether it’s possible to kill all the enemies on the grid.
Explanation:
The key observations are that there’re at most 16 lasers on the grid and there’re only 3 directions to shoot.
So, let’s just choose those lasers, who will shoot in the up direction(let’s call them “vertical” lasers, those who are not chosen are “horizontal”) There’re at most 216 variants, so we can simply iterate through them. After that, we can solve the problem independently for each row. How?
If there’re no alive enimies left on a row(after the “vertical” lasers shot), then it’s OK. Otherwise, if there’re no “horizontal” laser in the row, then the current variant fails. If there’re one “horizontal” laser on the row, then we should check if all the enemies lies to the one side of the laser. If there’re one “horizontal” laser on the row, then it’s OK anyway(we can make the most left one shoot to the right, the most right one shoot to the left - so all the row will be covered).
Total complexity is O( 2L NM ) per testcase.
Please, check out Setter’s and Tester’s solutions for your better understanding.
I couldn’t solve this problem. I haven’t studied greedy in detail, I just know what it is. But after reading the solution, I don’t think greedy was used.
I think it can be solved by Maxflow make Bipartite Graph The one set contain (Lasers) and another set contain (Enimies ) match both the sets and capacity of each edge is one. Then find the maximum flow .
if the maximum flow ==No of Enemise then output “possible” else maxflow is always less than Enemies so in this case it is “impossible”. Am i correct ??
I will be really happy if someone could look at my code here. I think it should work with complexity O(2^L ⋅ max(N,M) ⋅ L ⋅ log(max(N,M))), but it gets TLE. I tried to add some modification to it, but it didn’t work then.
The idea is pretty simillar, we check every combination of lasers vertically and horizontally. We go over all vertical and simply erase them from board using set. Then we check every row. If there is at least two lasers in a row, we can set them opposite and we’re done. If there is one laser, we have to check if he can shot all points in the row. If there is no laser in this row - we need to check another combination.
@selfcompiler: Your solution is wrong and needs to be patched up (Not sure whether it can be patched up or not).
You need to make sure that you shoot in only one direction.
I doubt that you can solve the problem so easily because you can visualize the problem as some kind of SAT formula.
the standard solution seems too bruteforce.My solution’s complexity is O(2^L * nlogn)(although it costs 0.66s…),by using bitwise operation to do some optimization.
@kostya_by Although it is a smart solution but could you please elaborate more on why we need to classify the lasers and be more specific on how to classify them as horizontal and vertical.
I have a solution with complexity O(2^L*max(L,N)). The main trick is in bitmasking and bitwise operations.
First of all, store bitmasks of all columns containing enemies for each row (it fits into long long), e[i]. Now, if we fix the bitmask of lasers pointing up, we can process the grid from bottom to top and keep a bitmask b of all hit columns from the current row up using 1 pointer in a sorted array of lasers’ positions. When computing b, we can also compute the leftmost and rightmost laser in each row that’s not pointing up.
The bitmask of living enemies in the i-th row after all the up-pointing lasers fired is q=((2**M-1)^b)&e[i]. If there are at least 2 horizontal lasers available here, the solution exists. If there are none, then q=0 must hold. If there’s one, all enemies must be to its right or left, so all or no enemies must be to its left, and their bitmask is q&(2**c-1), where c is the column where this single laser is located; we just need to check if it’s 0 or q.
Therefore, we process all lasers and all rows for each of 2^L bitmasks, each with O(1) operations.
stop using set,there is an easier way to check if an enemy is out or not.For every enemy you cand codify the lasers down to him like this.Let’s say down to an enemy is laser number 8,then you add to the integer of the enemy 2^8.
When you want to see in O(1) if an enemy is out because of the chosen lasers(“vertical” lasers),you make & between the integer of the enemy and the chosen lasers.If the result is >0,then you know the enemy is out.
Just take and example,you should understand it easily,and that codifying is useful for a lot of problems
