|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | You can find test cases here | die_young | 1695. Работа для роботов | 24 июл 2018 19:04 | 1 | 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 | | TLE 65 (+) | Erop [USU] | 1695. Работа для роботов | 2 июн 2012 15:09 | 1 | 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? | | Problem 1695 "Work for Robots" has been rejudged | Vladimir Yakovlev (USU) | 1695. Работа для роботов | 17 май 2011 11:49 | 3 | 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. | | got tle , need help. | William Chou | 1695. Работа для роботов | 13 апр 2011 08:25 | 6 | 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. | | why tle on test 41? | skoier6 | 1695. Работа для роботов | 9 авг 2010 05:43 | 3 | my program first find the largest independent set,then DP. Try using a random permutation | | Solution | Amir Hessam Moltaji | 1695. Работа для роботов | 10 сен 2009 16:03 | 1 | Solution Amir Hessam Moltaji 10 сен 2009 16:03 | | Why ML only 64Mb? | Victor Barinov (TNU) | 1695. Работа для роботов | 21 мар 2009 08:56 | 5 | 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. | | WA on test #2 | Dim@ | 1695. Работа для роботов | 16 мар 2009 19:47 | 4 | 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? |
|
|
|
