ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1394. Ships. Version 2

Posted by IntoTheDusk 3 Apr 2024 14:48
When I tried the brute force algorithm, I TLE at #15

How to solve this problem? Please send the solution to 13588731339@163.com
Re: Help!!!!
Posted by Ramil 12 Apr 2024 01:08
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