|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Nice problem, but too big time limit... | Danica Porobic | 1323. Classmates | 3 Mar 2016 06:58 | 10 | Because of enough time,I used dfs in 0.9sec.
But I think bfs+binary will much faster...
What is your algo? 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. there is a simple dp-on-subsets solution... 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'? 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... | | WA 10 please help | liujian | 1323. Classmates | 3 Oct 2015 07:42 | 1 | | | WA 4??? | scythe | 1323. Classmates | 4 Jun 2012 02:56 | 1 | | | WA | M@STeR.SoBG | 1323. Classmates | 18 May 2012 04:27 | 4 | WA M@STeR.SoBG 6 Nov 2007 21:45 What's the second test?? Any hints?? Re: WA Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) 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.. =( Re: WA [ONU]Denis Shchelkonogov 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 Re: WA mastersobg 18 May 2012 04:27 Accepted. 5 years have passed since my first comment in this thread. Oh... | | I was worrying about TL... but got AC 0.031 :) | Ostap Korkuna (Lviv NU) | 1323. Classmates | 19 Dec 2011 01:47 | 7 | 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 ! It's really great!)
Edited by author 30.06.2007 21:15 What is your complexity?
Does your solution use (2^n) * (2^n) memory?
Edited by author 10.07.2007 13:39 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! 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 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 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. | | algo | hoan | 1323. Classmates | 8 Dec 2010 19:04 | 1 | algo hoan 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!!! | | Week tests | Orfest (Novosibirsk SU) | 1323. Classmates | 20 Oct 2010 16:06 | 5 | Week tests Orfest (Novosibirsk SU) 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 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.
| | Fail(validator) | Tchurov_Tim (PomorSU) | 1323. Classmates | 22 Aug 2009 13:50 | 3 | What is Fail (validator)? Checker returned this error on test 4 for my some crazy solution. Validator is fixed. You have got WA on test 4. | | How? | Ilya Rasenstein (8 class) | 1323. Classmates | 1 Dec 2006 04:25 | 2 | How? Ilya Rasenstein (8 class) 29 May 2004 18:00 Can I solve dis with dinamic and match in bigraph? 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! |
|
|
|
