|
|
| Show all threads Hide all threads Show all messages Hide all messages | | WA13? | Programmer | 1624. Go out of here! | 24 Apr 2010 03:53 | 1 | WA13? Programmer 24 Apr 2010 03:53 | | Why TL such a large? | Kurpilyansky Evgeny (USU) | 1624. Go out of here! | 29 Aug 2009 17:36 | 7 | Accepted
0.062 1 486 КБ
I solve this problem with O(log K*(K+(W*H)^2)).
P.S. Sorry for my bad English. My algo's complexity is the same (haven't applied yet). Maybe, author have less efficient algo. Maybe, you realization is pretty fast... Well, the solution and the tests for this problem were written when I had just finished the first course. I had been quite a "weak" programmer that time. Actually, I'd implemented the first solution that came in my head and designed TLs and tests for it. Certainly, this problem had been stored on HDD without any change for one and a half year, and then it was given to the PTZ camp. Yes, we designed a lot of more efficient solutions, but it was laziness that prevented me from implementing them and creating new tests.
Nevertheless, probably it would be better for the tests to be unchanged. As I can see, this problem remains a great challenge for Timus coders, and the main difficulty is not to fit the speed limits. Still, I think TL is too large. Now I wrote it and also got AC in 0.062 sec. I think that 1 sec. for this problem is more than enough... I agree because even obvious O(W*H*K) solution, written quite optimal, works less then 0.5 sec. Hm... This, IMHO, already means that testset is weak, and admins should try to improve it I think it's strange to discuss large TL and weak tests for problem that was solved by 12 people on Timus (and one of them is the author of this problem). | | One question (+) | Sergey Lazarev (MSU TB) | 1624. Go out of here! | 2 Jun 2009 20:22 | 3 | What should my program output if every scout explored some part of the map (without any contradiction to himself), but there is no map that satisfies scout's "submaps" together? You are not asked about "submaps", but instead whether it is possible to construct a map with two given routes. So, as you see, your question is completely rhetorical. Ok.
1) There aro two routes.
2) It's impossible to determine coordinates of at least one scout.
3) It's possible to construct map with the first route (without the second).
4) It's possible to construct map with the second route (without the first).
5) It's impossible to construct map with both routes together.
What to output: "There is not enough data" or "A mistake has been made at step number X"?
And (if the second case) how to determine X? Take maximal X? |
|
|
|
