Voroni diagrams perhaps (O(N*log(N))

1) When bruteforcing, random shuffle both m rows and n ships
2) When solving one subset sum problem inside bruteforcing, use bitset (array of bitsets) instead of bool array (2d-array). Instead of max() in subset sum problem, use operator OR and operator "right bit shift". Just search "subset sum problem bitset" and you'll find out. This will speed up your dynamic programming in 32 or 64 times (if you are using both 64-bit compiler and 64-bit processor)

It will not totally solve problem, but you will get TLE#67 which is better and giving more hope :)

Edited by author 12.04.2024 01:08

Edited by author 12.04.2024 01:09

Edited by author 12.04.2024 01:11

dp[i][j] - amount of i-digit numbers ending with j.

therefore we form 2d table dp[n][2]

then

dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
dp[i][1] = dp[i - 1][1]

It's not hard to see that dp[i][0] + dp[i][1] (i.e. number of all valid sequences) forms a fibonacci sequence.

dp[i][0] + dp[i][1] = 2*dp[i - 1][0] + dp[i - 1][1]
you can treat as f_n = 2*f_(n - 2) + f_(n - 3)

But still, I don't know how to solve this problem :)

Edited by author 23.01.2022 01:36

Edited by author 23.01.2022 01:37

Thanks!

dang. thanks for it

Thanks!

OK, found my mistake. 777&222 would be very helpful test cases)

yes

ok, it was a perpendicular but what about 15 test

AC with big integers