| ENG RUS | Timus Online Judge |
Обсуждение задачи 1695. Работа для роботовdie_young You can find test cases here // Задача 1695. Работа для роботов 24 июл 2018 19:04 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 Erop [USU] TLE 65 (+) // Задача 1695. Работа для роботов 2 июн 2012 15: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? Vladimir Yakovlev (USU) Problem 1695 "Work for Robots" has been rejudged [2] // Задача 1695. Работа для роботов 8 сен 2009 03:05 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. Sandro (USU) Re: Problem 1695 "Work for Robots" has been rejudged [1] // Задача 1695. Работа для роботов 23 янв 2011 02:11 New tests by Sergey Kopeliovich were added. 11 authors lost AC. Vladimir Yakovlev (USU) Re: Problem 1695 "Work for Robots" has been rejudged // Задача 1695. Работа для роботов 17 май 2011 11:49 New tests by Maxim Buzdalov were added. 6 authors lost AC. William Chou got tle , need help. [5] // Задача 1695. Работа для роботов 11 апр 2011 10:16 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. ありがとう ございます。 William Chou Re: got tle , need help. [4] // Задача 1695. Работа для роботов 11 апр 2011 10:22 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. William Chou Re: got tle , need help. [3] // Задача 1695. Работа для роботов 11 апр 2011 13:11 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 William Chou Re: got tle , need help. [2] // Задача 1695. Работа для роботов 12 апр 2011 08:06 Oh ! after i use a new way to random , i got tle #69 now. faint. svr Re: got tle , need help. [1] // Задача 1695. Работа для роботов 12 апр 2011 08:47 I think that jury has some ideas for quick algo without random absolutely. Try to find mathematical ways to speed up. William Chou Re: got tle , need help. // Задача 1695. Работа для роботов 13 апр 2011 08:25 Oh ! I got AC now. Just a little Optimization. skoier6 why tle on test 41? [2] // Задача 1695. Работа для роботов 22 мар 2009 07:37 my program first find the largest independent set,then DP. skoier6 Re: why tle on test 41? [1] // Задача 1695. Работа для роботов 22 мар 2009 08:30 any tricks in test 41? Aleksey (BMSTU IU7) Re: why tle on test 41? // Задача 1695. Работа для роботов 9 авг 2010 05:43 Try using a random permutation Amir Hessam Moltaji Solution // Задача 1695. Работа для роботов 10 сен 2009 16:03 What's the solution? Victor Barinov (TNU) Why ML only 64Mb? [4] // Задача 1695. Работа для роботов 20 мар 2009 15:27 Hello! In this problem in original ML is 256 Mb But on Timus it is 64... Maybe admins have to increase it? Samsonov Alex [USU] Re: Why ML only 64Mb? [3] // Задача 1695. Работа для роботов 20 мар 2009 17:42 Yes, the problem is much more challenging now than it was originally, but it is still solvable. We will not increase memory limit. Victor Barinov (TNU) Re: Why ML only 64Mb? [2] // Задача 1695. Работа для роботов 20 мар 2009 19:22 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???? Vedernikoff Sergey (HSE: АОП) Re: Why ML only 64Mb? // Задача 1695. Работа для роботов 21 мар 2009 04:56 I think, one may use the same trick, but twice svr Re: Why ML only 64Mb? // Задача 1695. Работа для роботов 21 мар 2009 08:56 In international contests just them would be paid for unexpected skills and mastering. Dim@ WA on test #2 [3] // Задача 1695. Работа для роботов 14 мар 2009 16:16 what is the problem? nevermore Re: WA on test #2 [2] // Задача 1695. Работа для роботов 14 мар 2009 16:24 I have the same problem. plz give us the test №2 Dim@ Re: WA on test #2 [1] // Задача 1695. Работа для роботов 14 мар 2009 17:33 I'm sorry, this is my mistake each two robots in group must be friends Varun Kumar(Fundu) Re: WA on test #2 // Задача 1695. Работа для роботов 16 мар 2009 19:47 I am gettin the same issue for WA test#2. I have checked all the ranges min n max but no hint. Any idea?
|