|
|
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 I think that the 65th test is a hell for cache. So it is better to use as little memory as possible. I use 48Mb, but some people - less than 10. How they do it? New tests have been added to this problem against inefficient solutions. Previously accepted solutions have been rejudged. 15 authors have lost AC. Thanks to Maxim Buzdalov for the set of new tests. New tests by Sergey Kopeliovich were added. 11 authors lost AC. New tests by Maxim Buzdalov were added. 6 authors lost AC. I have tried so many times , but i have no idea to avoid tle. I use memory search to solve it , and get tle on #58. Although i use random method when i choose a node , but it doesn't work. I just know that somebody have accepted this problem use the same method one years ago. Maybe he also get tle after rejudged. e...I think this is a NP problem. Could anybody help me? Thank you! sorry for my poor English. ありがとう ございます。 I use C++ stl map to save information. And it's a Red-Black Tree(O(logn)). Will it be faster if i use hash(O(1)) instead of map? If anybody know how to solve it , please tell me. Here is my e-mail : 419481620@qq.com. I also have tried to use hash instead of map to save information. But still tle #58. Here is my code. After i accept , i will delete my code (if i could get accept , and i wish so , haha...). [code deleted]. Edited by author 13.04.2011 08:22 Oh ! after i use a new way to random , i got tle #69 now. faint. I think that jury has some ideas for quick algo without random absolutely. Try to find mathematical ways to speed up. Oh ! I got AC now. Just a little Optimization. my program first find the largest independent set,then DP. any tricks in test 41? Try using a random permutation Hello! In this problem in original ML is 256 Mb But on Timus it is 64... Maybe admins have to increase it? Yes, the problem is much more challenging now than it was originally, but it is still solvable. We will not increase memory limit. OK, I have solved it with less than 32Mb and faster than 1sec. BUT! Can anybody expalin HOW it is possible to solve it with ~0.1 sec and ~2Mb???? I think, one may use the same trick, but twice In international contests just them would be paid for unexpected skills and mastering. what is the problem? I have the same problem. plz give us the test №2 I'm sorry, this is my mistake each two robots in group must be friends I am gettin the same issue for WA test#2. I have checked all the ranges min n max but no hint. Any idea? |
|
|