|
|
back to boardYou can find test cases here You can make this problem even harder by setting TL to 1s. My current solution runs in 0.96s and there are two optimizations that aren't too hard to come up with that can speed up program significantly (probably sub 0.1s). Firstly, for any complete graph on N vertices the answer is 2^N. Secondly, if you program has TL issues look up 3-regular graphs, they are the worst case of my algorithm. My solution uses no random, there is a nice deterministic solution, i.e. no hashes or shuffling. The following tests should be enough to get rid of all WAs Tests: 3 001 000 100 Answer: 5 6 000001 001001 010000 000001 000000 110100 Answer: 11 6 010010 101010 010100 001011 110100 000100 Answer: 15 4 0011 0000 1001 1010 Answer: 9 4 0110 1011 1101 0110 Answer: 12 4 0001 0000 0000 1000 Answer: 6 10 0001111111 0011111111 0101111111 1110111101 1111011110 1111100111 1111100111 1111111000 1110111001 1111011010 Answer: 195 7 0111101 1011110 1100111 1100111 1111000 0111001 1011010 Answer: 39 Edited by author 24.07.2018 19:09 |
|
|