| ENG RUS | Timus Online Judge |
Discussion of Problem 1533. Fat HobbitsxMagGTU Дмитрий Тишкин GPRS к жюри [8] // Problem 1533. Fat Hobbits 3 Mar 2007 14:00 перепроверте тесты задачи B pls Sergey Pupyrev [USU] Re: к жюри [7] // Problem 1533. Fat Hobbits 3 Mar 2007 14:13 Перепроверили :) ryu Re: к жюри [6] // Problem 1533. Fat Hobbits 3 Mar 2007 15:12 а теперь условия pls xMagGTU Дмитрий Тишкин GPRS чё за [5] // Problem 1533. Fat Hobbits 5 Mar 2007 00:00 исходя из условий задачи необходимо вывести номера хобитов(строк) состоящих из одних нулей предворив список на отдельной строке числом таких строк засада при случае когда таких строк нет( возможен когда матрица содержит ошибочные данные тк как всегда должен имется легчайший хобит) ВОПРОС почему так мало ac? у такой на первый взгляд простой задачи? намекните pls! diver[rus] Re: чё за // Problem 1533. Fat Hobbits 5 Mar 2007 02:21 not so easy, try this test: 3 0 0 0 1 0 0 1 0 0 answer: 2 2 3 or this: 3 0 0 0 0 0 0 1 1 0 answer: 2 1 2 Denis Koshman Re: чё за [3] // Problem 1533. Fat Hobbits 14 Jul 2008 02:01 По-моему так это NP-полная задача на 100 узлов Sandro (USU) Re: чё за [2] // Problem 1533. Fat Hobbits 14 Jul 2008 09:39 SanKeaR No subject // Problem 1533. Fat Hobbits 25 Aug 2008 21:24 Edited by author 16.09.2010 19:25 -XraY- Re: чё за // Problem 1533. Fat Hobbits 26 Mar 2014 01:54 Эта задача решается за O(n^2) + Кун. Так что совсем быстро :) Victor Barinov (TNU) How to solve correctly? [3] // Problem 1533. Fat Hobbits 31 Oct 2007 18:20 Hi! I know that exists theorem: Minimal number of paths that cover such graph equals to maximal number of independent vertices. If I found this paths how can i recieve necessary vertices? Thanks! svr Re: How to solve correctly? [2] // Problem 1533. Fat Hobbits 31 Oct 2007 20:21 I think that it is some clever ways to solve NP problems. It works only in authors limits. O(n^3)exists! Apply bipartie maximal cardinality matching. Standard matchig programm must be strengthening by finding minimal vertex covering. All vertex out of minimal covering - hobbits! Edited by author 02.11.2007 09:02 Sandro (USU) Re: How to solve correctly? [1] // Problem 1533. Fat Hobbits 31 Oct 2007 23:21 This problem can be solved in O(N^3) time. Denis Koshman Re: How to solve correctly? // Problem 1533. Fat Hobbits 24 Aug 2008 17:34 Victor. To solve what you want, you should find maximum clique in inversed transitive closure graph. Anyway, such level of abstraction leads to NP solution, try some other way. Transitive closure graph has some extra properties which allow O(N^3). ProgBeat How to solve this problem ?? // Problem 1533. Fat Hobbits 18 Jun 2007 01:37 I got AC with very optimized backtraking, I think the problem has simple solution.. Could you tell me your algo or send me your code in case if you solved it without backtraking ? e-mail: www-www-www@mail.ru EfremovAleksei i got ac, but don't understand how! please, send me your sol! [1] // Problem 1533. Fat Hobbits 30 Mar 2007 16:00 efrcom [at] inbox [dot] ru Olecksandr Voeca [Lviv NU] Re: i got ac, but don't understand how! please, send me your sol! // Problem 1533. Fat Hobbits 22 Apr 2007 17:28 Edited by author 04.05.2007 01:03 EfremovAleksei WA#47? Special case? // Problem 1533. Fat Hobbits 27 Mar 2007 14:48 closed! AC! Edited by author 27.03.2007 14:51
|