ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1514. National Park

Alias (Alexander Prudaev) WA16 What is special in this test? i can't find the bug in my prog [6] // Problem 1514. National Park 17 Feb 2007 20:52
Alias (Alexander Prudaev) please help me! [5] // Problem 1514. National Park 17 Feb 2007 21:49
i have write brute-force procedure solve()
and test my program on random tests.
my program always gives correct answer.
I have not so twisted imagination, which
have autors this tests, so i can't think up such test.

My congratulations to  autors:
your imagination is more twisted than rand() :)
svr Re: please help me! [4] // Problem 1514. National Park 17 Feb 2007 22:04
Your should be greatful to authors who
keep in secret speeding up methods and
give you(and us) chance to create them.
Now I can't see how avoid O(n^3)
For example may be 16000 smal identical triangles and so on.
I think 15-test is last with small N.
So not-top-coders may move to solution by
exchanging with ideas on forum.

Edited by author 17.02.2007 22:04
Alias (Alexander Prudaev) to SVR [3] // Problem 1514. National Park 17 Feb 2007 22:09
there is NlogN solution
svr Re: to SVR [2] // Problem 1514. National Park 17 Feb 2007 22:17
Why in this case you use use brute force and random?
Alias (Alexander Prudaev) Re: to SVR [1] // Problem 1514. National Park 17 Feb 2007 23:11
because my NlogN solution gives wrong answer on 16th test
and i tryed to find such test, that BruteForce answer differs
with MyNlogNSolution answer
svr Re: to SVR // Problem 1514. National Park 18 Feb 2007 00:26
Try to prove your algorithm.
If proof right and authors is'n mistaken you
will pass test 16 without difficulties.