| ENG RUS | Timus Online Judge |
Обсуждение задачи 1323. ОдноклассникиDanica Porobic Nice problem, but too big time limit... [9] // Задача 1323. Одноклассники 25 июл 2004 23:58 1 second is just enough. Yoyo Re: Nice problem, but too big time limit... [1] // Задача 1323. Одноклассники 4 сен 2004 22:25 Any hints? Dmitry 'Diman_YES' Kovalioff Just brute force :) (-) // Задача 1323. Одноклассники 5 сен 2004 12:43 Aleksey (BMSTU IU7) Re: Nice problem, but too big time limit... [5] // Задача 1323. Одноклассники 30 сен 2004 01:20 just 0.1 sec. Neumann How can you do it so fast? [4] // Задача 1323. Одноклассники 5 фев 2005 10:32 Because of enough time,I used dfs in 0.9sec. But I think bfs+binary will much faster... What is your algo? Lifanov Re: How can you do it so fast? [3] // Задача 1323. Одноклассники 9 сен 2005 12:35 I used dfs and get AC with 2.1 sec. Then i use simple optimization and get Ac with 0.17 sec? It's very simple. Ilya Rasenstein (Lyceum #40) Re: How can you do it so fast? [2] // Задача 1323. Одноклассники 6 май 2007 14:35 there is a simple dp-on-subsets solution... SPIRiT Re: How can you do it so fast? [1] // Задача 1323. Одноклассники 21 июн 2007 02:08 I tried to solve it with dp-on-subsets but WA at test 7. Any hints? Also, when I use stricmp in C++, I get CE. Is this function illegal? Also, are the names unique in case-sensitive sense, or case insensitive? Does the last line in file always contain word 'Tanya'? hoan Re: How can you do it so fast? // Задача 1323. Одноклассники 8 дек 2010 19:28 the last can be change. Jane Soboleva (SumNU) Re: Nice problem, but too big time limit... // Задача 1323. Одноклассники 3 мар 2016 06:58 AC with the help of "if currentTime - startTime > 3.98 then exit"~ Without this limitation, it works almost full 40 seconds on test with maxed N and M. I feel too lazy to think of effecient ways when i see such a generous time limit... liujian WA 10 please help // Задача 1323. Одноклассники 3 окт 2015 07:42 scythe WA 4??? // Задача 1323. Одноклассники 4 июн 2012 02:56 Try this: 1 0 a A: 0 M@STeR.SoBG WA [3] // Задача 1323. Одноклассники 6 ноя 2007 21:45 What's the second test?? Any hints?? Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) Re: WA [2] // Задача 1323. Одноклассники 6 янв 2008 14:27 In this test n=m=8 I also had some problems with this test.. And it's all that I found out about it.. =( [ONU]Denis Shchelkonogov Re: WA [1] // Задача 1323. Одноклассники 20 июл 2010 21:46 I also have WA3, but program solves all my tests. Can anyone suggest some tricky test? Edited by author 20.07.2010 21:55 Edited by author 20.07.2010 21:56 mastersobg Re: WA // Задача 1323. Одноклассники 18 май 2012 04:27 Accepted. 5 years have passed since my first comment in this thread. Oh... Ostap Korkuna (Lviv NU) I was worrying about TL... but got AC 0.031 :) [6] // Задача 1323. Одноклассники 30 июн 2007 20:14 It's a great problem. I enjoyed solving it! DP on subsets + match in bigraph - was not hard to implement at all. Just nice step-by-step implementation! And what a great time! Only 0.031 ! AlexF [USTU] Re: I was worrying about TL... but got AC 0.031 :) // Задача 1323. Одноклассники 30 июн 2007 21:14 It's really great!) Edited by author 30.06.2007 21:15 elmariachi1414 (TNU) Re: I was worrying about TL... but got AC 0.031 :) [4] // Задача 1323. Одноклассники 10 июл 2007 13:27 What is your complexity? Does your solution use (2^n) * (2^n) memory? Edited by author 10.07.2007 13:39 Ostap Korkuna (Lviv NU) Re: I was worrying about TL... but got AC 0.031 :) [3] // Задача 1323. Одноклассники 10 июл 2007 22:21 The complexity of my solution is approximately O((2^N)*(2^N)*N*N). More exactly it is O(Mk*N*N), where Mk = C(N,N-1)+C(N,N-2)*2^2+C(N,N-3)*2^3+...+C(N,2)*2^(N-2)+C(N,1)*2^(N-1) where C(N,M) - is the number of combinations :) I use as much as O((2^N)*(2^N)) memory. Good luck! elmariachi1414 (TNU) Re: I was worrying about TL... but got AC 0.031 :) [2] // Задача 1323. Одноклассники 16 июл 2007 15:32 Thank you for answer. I have tried to find algo with O( 2^n ) memory, but it seems, that there does not exist such "non factorial" algorithm :( So I have implemented O( (2^n)*(2^n)*n*n ) algorithm that uses O((2^n)*(2^n)) memory (asymptotic is correct). This algorithm does not use bipartite matching algo at all. AC in (0.015 :: 1 287 KB). UPD: Also I realized O((3^n)*n) algo with O((3^n)*n) memory which has taken AC in (0.031 :: 8 439 KB), but I was aware of low level optimization Edited by author 17.07.2007 15:58 Denis Koshman Re: I was worrying about TL... but got AC 0.031 :) [1] // Задача 1323. Одноклассники 12 авг 2008 01:37 It's easy to implement O(2^N) memory algo - just DP on subset of pupils that know those news, each bit 1 can spawn at most one more bit 1 if there is an edge, the set of transitions can be calculated at O(2^N * N^2) overall time (state with 2^P ones leads to at most 2^(N-P) ones and these transitions can be calculated by BFS - number_of_src_bit1 X number_of_dst_bit1) P.S: AC in 0.015 sec / 305Kb, 1st effort :) Edited by author 12.08.2008 02:14 ValenKof Re: I was worrying about TL... but got AC 0.031 :) // Задача 1323. Одноклассники 19 дек 2011 01:47 There is 3^n * n^3 algo. For every mask check its sub masks (total 3^n checks). Every check - finding bipartite matching in graph. But a do it easy: for every 2^n masks generate all masks what we can achieve with recursive function. hoan algo // Задача 1323. Одноклассники 8 дек 2010 19:04 i use O((n-1)!* n^2) and got AC in 0.109 s. just use o(n^2) memory. for all permutation check its valid or not, for example for this test: 4 3 1 2 2 3 3 4 the permutation 1 2 3 4 is valid but 1 3 4 2 is nonvalid. GOOD LUCK!!! Orfest (Novosibirsk SU) Week tests [4] // Задача 1323. Одноклассники 20 окт 2010 10:43 My solution works 5.5 sec on the following test. I believe my computer is faster than yours. So, please add this test and make me lose AC. 10 27 a b a c a d a e a f a g a h a i a j d h d i d j e f e g e h e i e j f g f h f i f j g h g i g j h i h j i j a Sandro (USU) Thank you. Your test was added. (-) [3] // Задача 1323. Одноклассники 20 окт 2010 11:54 :| Re: Thank you. Your test was added. (-) [2] // Задача 1323. Одноклассники 20 окт 2010 14:12 Why did you add the test which is not formatted correctly ? I had go to my old pascal code, install some compiler for it and then it appears that the input format of that test is incorrect and that's why my solution fails. Sandro (USU) Sorry. Test will be fixed. (-) [1] // Задача 1323. Одноклассники 20 окт 2010 15:55 Sandro (USU) Test is OK now. Wrong verdicts are fixed. (-) // Задача 1323. Одноклассники 20 окт 2010 16:06 Tchurov_Tim (PomorSU) Fail(validator) [2] // Задача 1323. Одноклассники 21 авг 2009 01:02 What is Fail (validator)? Checker returned this error on test 4 for my some crazy solution. Sandro (USU) Re: Fail(validator) [1] // Задача 1323. Одноклассники 21 авг 2009 11:53 Validator is fixed. You have got WA on test 4. Tchurov_Tim (PomorSU) Re: Fail(validator) // Задача 1323. Одноклассники 22 авг 2009 13:50 Thanks! Ilya Rasenstein (8 class) How? [1] // Задача 1323. Одноклассники 29 май 2004 18:00 Can I solve dis with dinamic and match in bigraph? Peter Ivanov Re: How? // Задача 1323. Одноклассники 1 дек 2006 04:25 I think this is possible. Initially I started writing some dp with O(2^n * n * 2^n * something_for_the_bigraph). It is too complex for a problem that can be solved using only a dfs. But the idea is still good!
|