SHOOTING - Editorial

[kostya_by]

Problem Link: contest, practice

Difficulty: Simple

Pre-requisites: Bruteforce, Greedy

Problem:

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 2¹⁶ 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( 2^L NM ) per testcase.

Please, check out Setter’s and Tester’s solutions for your better understanding.

Setter’s Solution: link

Tester’s Solution: link

[kostka]

For both solutions there is AccessDenied.

[sharmaeklavya2]

Why is greedy a prerequisite?

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.

[selfcompiler]

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 ??

[kostka]

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.

Thanks in advance.

[minitracyzhu]

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.

[xellos0]

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.

[krooonal]

how about this: I actually got AC during the contest.

1. for each enemy define degree of enemy by how many unused lasers can kill it.

2. find an enemy which has degree less than or equal to 1. If we can’t find such enemy then the answer is Possible

3. If we find an enemy with degree 0 then the answer is Impossible

4. we have an enemy with degree 1. Use it to direct the laser which is pointing to it and mark that laser as used

5. Update the degree of remaining enemies and go back to 2.

This can cause at max 16 iterations. and since the constraint are small w.r.t. the dimensions of grid, it is not so expensive to do all the other tasks mentioned above.
I don’t have any formal proof for this approach. But Intuitively I convinced my self during the contest. I would appreciate if some one can come up with formal proof or an counterexample.

[caioaao]

I did one with complexity O(3^L + N*M): scan lines from bottom, and from left to right, keeping the state variables:

• bool A: has enemy alive in line before this column,
• bool B: some laser shot right, cleaning the rest of the column,
• long long bm: bitmask with columns that had some laser shooting up.

so my recursive function looked like this: func(int row, int col, bool A, bool B, long long bm). whenever we hit an enemy, we check if B is true. if it isn’t, A = true for the next function call. if B is true, we simply call func(next_row, next_col, original_A, original_B, bm). For the lasers, I just call func(next_row, next_col, original_A, original_B, bm|(1<<col_id)) OR func(next_row, next_col, 0, original_B, bm) OR func(next_row, next_col, original_A, 1, bm).

whenever we hit a column = 0, we check if A is true. If it is, then some enemy on the lower rows is still alive, and as we can’t kill it (no lasers shoot down), it returns false already. if the row -1 is reached and A is false, returns true.

unfortunatelly, I couldn’t debug it in time, and only got it Acc in practice. I did an O(2^L*n*m*log(2^L)) solution using a memo table first, but the solution was faster without it.

[archazey]

My solution CodeChef: Practical coding for everyone is 2^LNM and it takes tle.Please help me!
I knew from the first that T2^LN*M is too big,but that’s the complexity of the editorialist.And it should work

[kostya_by]

They will be uploaded soon. Sorry for delay.

[kostka]

No problem, I just wanted to point it.

[kostya_by]

I guess you are, but it’s too cool solution for this problem. The constraints allow to use simple approaches. =)

[win_ay]

How do you make sure that each laser is shot only in one direction??

[dpraveen]

@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.

[selfcompiler]

@win_ay For this each laser is associated with only one edge that is select by after running the maxflow algorithm !!!

[stud_ious]

T*(2^L)NM is 1.6e^9 which shouldn’t come in time…Don’no how that gave accepted?

[selfcompiler]

@dpraveen may be you are correct

[chandan721]

@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.

[caioaao]

@stud_ious your math is wrong. 2^L x N x M = 2^16 x 50 x 50 = 1.6e8, which is ok for the TL