SHOOTING - Editorial

general
, , ,
21

@dpraveen I dont take into account the number of test cases, unless when explicitly needed, cuz normally the worst case will appear in a small subset of cases, so the number of test cases is just a constant negligible factor

22

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.

6 Likes
23

Unfortunately, your solution is wrong and the test data is weak. Here is one test case which makes your solution fail:

1
3 4
.EE.
ELLE
ELLE
26 Likes
24

I donā€™t think that this problem can be solved by maxflow.

  1. Need to ensure that one Laser only shoots in one direction. Although this can be circumvented by creating 3 nodes for each laser. L_top, L_left, L_right.
  2. This cannot be modeled as a maximum-bipartite matching as each enemy can be destroyed by multiple lasers.
  3. There is not way to control flow out of enemy(E).

I tried this approach during the competition and failed miserably. I was checking if maxflow >= number_of_enemies.

25

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.

1 Like
26

Can anyone explain what the editorials want to explain i am not getting it :frowning:

27

My solution http://www.codechef.com/viewsolution/4625405 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

28

Laser can shoot only once?