I think that this problem should be solved with bipartite matching. But the fastest algo for this is O(sqrt(V)*E).

Did you send O(VE) and O(sqrt(V)E) solutions?
Has it got TLE?

I don't know implementation of O(sqrt(V)E), but Cormen writes that this is the fastest one. It can't get AC if the tests are OK, because V <= 1000 and it means E <= 10^6. Even this won't be able to fit into TL. I think that the tests are bad and would like to talk to someone who has already got AC. So I haven't sent any solutions for this problem yet.

Edited by author 03.04.2005 00:56

I also haven't sent any solutions for this problem yet.
But so many people had got AC...
I think tests are not such terrible :)

Sorry, Cormen writes only about algos using maxflow. There is another method, that uses chains and works in O(V^2), it is described in "Discrete Analysis" by Romanovsky.

subj. The best algo I know (I mean I know that it exists) is ABMP algo (Alt-Blum-Mehelhorn-Paul algo, but I did not find it anywhere). It is almost 10 times faster than Hopcroft-Karp.

Standart MaxMatch algos are not so slow as you think. Mostly they work in O(E) while worst time complexity is O(VE) or O(sqrt(V)*E). Actually it is VERY hard to construct worst case for max-match algo. For example if you try to fuck up QSort, you create some array. But! If you pick not middle element, but it's neighbour you will easily pass this test case... The same aplies to MaxMatch algo's... But since this algo is not so trivial, there exists a lot of almost equal implementations, which will behave absolutely different on critical tests...

E is lot less than V^2, since you won't be able to read all edges in time limit =).

Try submitting easiest implementation to this problem =).

P.S. Is "Discrete Analysis" by Romanovsky available somewhere in the Internet? (On Russian or English or Ukrainian).

Thank you very much for your reply. This is what I expected, so I said that this problem is a little bit unfair, because the worst case won't get AC.
I wasn't able to find Romanovsky's book in the Internet, I think it can be found in St.Petersburg only, because Romanovsky is our SU lecturer. The algo written there is rather difficult and seems to be a little bit wrong, but I think it can be corrected, so it will be O(V^2).

I couldn't find "Discrete Analysis" by Romanovsky. Can someone who had found it already give me I link. I would be very, very greatful :)

You are right! This problem is unfair and the tests are bad. I got AC with simple V^3 solution in 0.031 but for V=1000 it should be TLE. New test should be added.

I'll add no test for this problem!

Imagine the test with complete bipartite graph. It's size would be 8.5 MB! Reading routines would work at least 0.3 sec. As you have AC with time 0.031 you can see that tests are not so big.

But most solutions will work very fast on such tests!
I can't construct a graph that fail all O(V^3) solutions.

My O(V^3) solution works faster than my O(V^2.5) solution on every test I can make. My O(V^3) solution is Greedy+DFS. It has only 60 lines!

If I can't make the problem perfect then why should I change anything?

I agree that failing all O(V^3) solutions is too hard. When I started this thread I didn't know about greedy initializing, which works really perfectly!

Of course, it was obvious that there are not so many edges in this graph both because of TL and ML (and because of a lot of people getting AC). But why isn't it written in statement and we should guess this ourselves. Just writing that K <= "some value" will be much better I think.

To Vladimir Yakovlev: please, pay attention to problem 1040 (Airline company), it seems that there it's possible to add some tests making problem much more difficult than it is now.

On 1040: can you suggest a solution for this "much more difficult" problem?
On 1109. I think, it is possible to fail most of greedy solutions. If you want, I will send to you several tests.

I agree with Yaroslavtsev Grigory. Just change the problem text, so the big tests will not be possible. If there are no tests with N=1000, so the limit for N should be decreased. Or you can add the limit for K, which is maximum K from tests.

Such problems are often included in real problemsets. You just need to take the risk and write a solution that is not guaranteed effective enough.

It depends on problemsets, because I'm completely sure that I won't get such a problem on NEERC or just Northern Subregional contest. There such problems are treated as "bad" (especially like 1040). Also I think it's difficult to find such problem on acm.sgu.ru, all problems I solved there are "good". By the way, I think you know that many russian best programmers are training there. But "bad" problems are often found on IOI-like contests, where points are given for each problem, and it's ok there.

So it completely depends on you to try making problems better (as you did with "Ships") or not. My opinion is that problems should be "better".

1040: I don't know solution for this problem, if there were some tests I would try to pass them combining simple idea and some heuristics.
1109: please e-mail me on grigory@inbox.ru, thanks in advance.

And I would really like to know your real name and study place, as you got to the 2nd place on timus!

Edited by author 05.01.2006 17:23

As for me, I like this problem. Greedy init is ok, O(N^3) gets AC with flying colors meanwhile the test set is not as weak as you probably think. 1109 just shows that asymptotic complexity may be beaten sometimes. No test should be added imho.

P.S. TLE? Weak tests? Bad problem? Well, there are 3 options:

- create your own test set and solution, contact with the admin and prove your ones are better than we have now;
- host your own acm-server and make all the problems there as good as you can;
- join "the russian best programmers" on acm.sgu.ru... LOL ;)))

No offence.

Edited by author 05.01.2006 19:48

Sorry, I forgot to write the definition of "goodness". "Good" problem is the one, for which exists a solution which passes every possible testcase. This definition is a bit incorrect, because it doesn't include problems where some randomization is needed. But anyway it's obvious that 1040 is "bad". Unfortunately I lack time (because of my exam session) to find out whether 1109 is "bad" or not, but some people ("still alive") can even give tests. Anyway, I insist on adding limitation for K or/and N as "Sandro (USU)" said.

I like timus, but some of my friends don't and left it because of similar problems with testcases and statements. It's sad. So sometimes I'm trying to pay admin's attention to the things I don't like.

I don't think that all people that solve problems here compete in NEERC and Northern Subregional Contest as you do. Many other regional/subregional/local contests may contain such problems as 1109 and 1040. All types of problems should be presented on Timus. If you don't like a problem you need not solve it.

Your posts made me sure not to change anything :)
But for all people that like to solve only "good" problems I say that K < 60000 in this problem. And I won't add this to problem text.

PS.
1. I also want to make Timus better. I improved many problems and I can say that this problem is good enough. I tried to improve it already, but I decided to leave it unchanged.
2. Please tell me why did your friends leave Timus?
3. Some problems on acm.sgu.ru are "bad" also :( I'll do my best to make the number of Timus's "bad" problems less than sgu's.
4. Question about 1040 is still opened. Wait some time.

Of course in some way you are right, because even problems in World Finals have multiple test cases but the number of tests isn't written. On some training I got TLE in such problem with N <= 10 solving it in O(N^4) and AC with O(N^3). I think it is "bad", but so it is. I really like NEERC-like problems, but after all it's just my opinion.

It's your choice and it seems to be right, thanks for telling real limitation for K.

1.It's really great, that you are trying to do it. I understand how difficult it is, much more difficult than solving problems.

2.I think that one reason is bad tests and statements, there are usually a lot of bugs when a new problemset is added. The second reason seems to be that problems on timus differ from NEERC-like in ideas. I like it, but it is not so useful when you're preparing for the contest.

3.I also think so, I said that it is perfect just for contrast, anyway it seems to me that sgu is "better".

4.Thanks once more. I was really annoyed seeing no reply on Burunduk1's post about weak tests.

Good luck!