Editorials are available (click on the problem statement and click on the analysis tab).

i just made the constraints smaller i.e. if ai>20 make ai=20 or 21 depending on ai-20 is even or odd respectively. rest is just digit dp

The intended solution should be DP, but I get it passed by randomly generating numbers and check whether it is divisible... (The order doesn't matter so I only generate the frequency of each number in odd/even positions)

Anyone wants to hack?

Create a graph where each node is a diagonal. See the problem as coloring the nodes with black and white (Black means we are using the diagonal. White means not using.) Then we want the graph to have a minimum number of black nodes.

Suppose we have a grid that is black, and it can be changed by two diagonals $$$A$$$ and $$$B$$$. Then in the final coloring $$$A$$$ and $$$B$$$ should be in the same color. If the grid is white, then $$$A$$$ and $$$B$$$ should be in different color. Then we can do something similar to bipartite graph checking to color the graph, and take the minimum of two colors in each connected component.

although I didn't solve it, I think below solution is right. since till the end I found the bug that doesn't separate odd/even two part.

first separate graph into odd/even diag-part, i.e. (i+j)&1?

note for one graph, there are exactly two ways to flip, since once some diag decided, can deduce others. so you can use dfs or two_sat to get the cnt(=how many diags choosen to flip), then result = min(cnt, N-cnt). where N=#diags of that part graph.

final result is sum of two part.

I just brute forced for diagonals of the same length (starting with the longest) with bitmasks and then recursed. There is always some field that is not touched by smaller length diagonals, so one can prune some states early.

I did it like this:

1. brute-force whether to "flip" values at 2 upper-left "/-diagonals": 1st diagonal is (0,0), 2nd diagonal is (1,0) and (0,1) (there will be 2*2==4 choices).

2. Depending on cell (0,0), flip "\-diagonal" (0,0), (1,1), ... , (N-1, N-1) (main diagonal)

3. Depending on cell (1,0), flip "\-diagonal" (1,0), (2,1), ... , (N-1, N-2) (1-below main diagonal).

4. Depending on other cells (not (0,0) or (1,0)) cells, flip "/-diagonal" that contains (i, i) or (i+1, i).

5. Depending on values in (2, 0), (3, 0), ... (N-1, 0), flip "\-diagonals" that contain (i+2, 0) (below 1-below main diagonals)

6. Depending on values in (0, 1), (0, 2), ..., flip "\-diagonals" that contain (0, i+1) (above main diagonals)

7. Check that you have all '#'s, update result

Overall complexity: $$$O(4\times N^2) = O(N^2)$$$

However, I've seen other simpler solution:

1. brute-force whether to flip "\-diagonal" (0,0), (1,1), ... , (N-1, N-1) (main diagonal) and "\-diagonal" (1,0), (2,1), ... , (N-1, N-2) (1-below main diagonal) (still 2*2 == 4 choices)

2. Depending on value in cell (i, i) or (i+1, i), flip "/-diagonal" that contains this cell

3. Either flip or don't flip all other "\-diagonals" (just like steps 4., 5. in previous solution).

4. Check that you have all '#'s, update result.

Complexity: still $$$O(N^2)$$$

i used masking for one direction diagonal and after applying operations in one direction,check for other direction diagonal whether it is possible to do operations to make grid complete black.

As for one diagonal we can do operations either 0 or 1 time that's why masking

Soon