| ENG RUS | Timus Online Judge |
Discussion of Problem 1323. ClassmatesDanica Porobic Nice problem, but too big time limit... [9] // Problem 1323. Classmates 25 Jul 2004 23:58 1 second is just enough. Yoyo Re: Nice problem, but too big time limit... [1] // Problem 1323. Classmates 4 Sep 2004 22:25 Any hints? Dmitry 'Diman_YES' Kovalioff Just brute force :) (-) // Problem 1323. Classmates 5 Sep 2004 12:43 Aleksey (BMSTU IU7) Re: Nice problem, but too big time limit... [5] // Problem 1323. Classmates 30 Sep 2004 01:20 just 0.1 sec. Neumann How can you do it so fast? [4] // Problem 1323. Classmates 5 Feb 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] // Problem 1323. Classmates 9 Sep 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] // Problem 1323. Classmates 6 May 2007 14:35 there is a simple dp-on-subsets solution... SPIRiT Re: How can you do it so fast? [1] // Problem 1323. Classmates 21 Jun 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? // Problem 1323. Classmates 8 Dec 2010 19:28 the last can be change. Jane Soboleva (SumNU) Re: Nice problem, but too big time limit... // Problem 1323. Classmates 3 Mar 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 // Problem 1323. Classmates 3 Oct 2015 07:42 scythe WA 4??? // Problem 1323. Classmates 4 Jun 2012 02:56 Try this: 1 0 a A: 0 M@STeR.SoBG WA [3] // Problem 1323. Classmates 6 Nov 2007 21:45 What's the second test?? Any hints?? Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) Re: WA [2] // Problem 1323. Classmates 6 Jan 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] // Problem 1323. Classmates 20 Jul 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 // Problem 1323. Classmates 18 May 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] // Problem 1323. Classmates 30 Jun 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 :) // Problem 1323. Classmates 30 Jun 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] // Problem 1323. Classmates 10 Jul 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] // Problem 1323. Classmates 10 Jul 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] // Problem 1323. Classmates 16 Jul 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] // Problem 1323. Classmates 12 Aug 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 :) // Problem 1323. Classmates 19 Dec 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 // Problem 1323. Classmates 8 Dec 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] // Problem 1323. Classmates 20 Oct 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] // Problem 1323. Classmates 20 Oct 2010 11:54 :| Re: Thank you. Your test was added. (-) [2] // Problem 1323. Classmates 20 Oct 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] // Problem 1323. Classmates 20 Oct 2010 15:55 Sandro (USU) Test is OK now. Wrong verdicts are fixed. (-) // Problem 1323. Classmates 20 Oct 2010 16:06 Tchurov_Tim (PomorSU) Fail(validator) [2] // Problem 1323. Classmates 21 Aug 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] // Problem 1323. Classmates 21 Aug 2009 11:53 Validator is fixed. You have got WA on test 4. Tchurov_Tim (PomorSU) Re: Fail(validator) // Problem 1323. Classmates 22 Aug 2009 13:50 Thanks! Ilya Rasenstein (8 class) How? [1] // Problem 1323. Classmates 29 May 2004 18:00 Can I solve dis with dinamic and match in bigraph? Peter Ivanov Re: How? // Problem 1323. Classmates 1 Dec 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!
|