Z-Roaming: FloodFill

@admin:
What did you mean when you wrote:
More Info - By Z-trening users :) ?

well , I guess it should mean that this competition is added by z-trening users.

I don't know who is directing this one, but maybe it wasn't the smartest idea to schedule it at midnight again...It could have started at 9 or 10 pm, so we could think until the end, not collapse in front of our PCs....I hope this can be moved a bit earlier :)

I agree. 10pm would be optimal. What do rest of you think?

i agree. 0:00 is a bit to late :)

I agree too.

I agree too. I've worked Z-95 Round 1 from 00-00 to 05-30 and i was so tired that i have slept until 17-30. :(

I slept for 3 hours, and now I'm trying not to stop breathing xD Igore, ti si direktor? :D

Director? You mean about these starting times? Nope, it's admin's decision, but I doubt that he won't agree too when he checks out this topic.

And... Please keep you posts in English. :)

result?:D

Please tell me how to solve the third task from z-roaming and a faster way than brute force on second

In the second u sort by angle each point makes with other points and then sort them and see the longest same subsequence...mine is a bit too slow though....

http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100018177

I submited right code on third, then wanted to submited a little correction and I submited wrong file. Damn it. -.-

so whats the solution on third?

dynamic programming :)

Turgond your solution doesnt seem faster:D we have same amount of points :D
Or maybe you just implemented it badly:D

well n^2 * logn should do the trick, is that how you did it?

yea

Thanks a lot bora :D , something more in detail:D

ups ...

If you think about 3rd task ( and if you ask me )
then: O( N*N*O )

Boris your hint is really helpful :D
My DP got 60, and it's the worst complexity possible :D

Mine seems n^3 but it has little optimisations and memorises already checked lines so that i dont check them again

Mine was n^3*o^2....should have gotten like...30 :D
As for the second, I made a fraction struct to evade any tolerance checking, cause it was hard to do here, but it made it too slow....

Ok but just complexity of third want help me figure the solution:D

I don't know how to calculate my complexity, but I'm getting WA on two test cases :-/

I don't know what I'm doing wrong in 2nd, if anyone care to help..

well, i have int dp[ MAXO ][ MAXPL ],
where dp[ a ][ b ] means:

what is minimum if i set one outlet on position b, and before i have a-1 of outlet.

so first i fill dp[ 1 ][ i ] i = 1..pl
and then i go i = 1..o and fill every case.

I can explane more, but some users maybe wouldn't want that.

Is it something like : "what is the best result you can get from n1 to n2 using m outlets"?

n1<=n2 <=N
m<=M , number of outlets

In the second test examples are BAD!!!!!!!!
NO TOLERANCE NEEDED.....
Come on.....i can find an example where the AC solution I just sent breaks, and it didn't :D
Vasja, in the third i made dp[i][j][k] where it represents minimum sum from i to j with k outposts....and updated them so i check every smaller in it....

well, yes and no..

it is: "what is the best result you can get from 0 to b if you put one outlet on position b and before b there are m-1 outlets."

what's AC solution?

Accepted :)

Well thanks , i will try to implement something:D

@vasja: I did on another way.

Mine dp[ i ][ j ][ k ] tell ms what's the best way of arranging K outlets on positions from I to N if last outlet before I-th is on J-th position

I think z-Garden's time limit was too low. My solution was O(N^2 log N) and was exact (integers only - no doubles), but I got TLE on four cases.

Did anyone have an O(N^2) solution? If the people who got accepted within the time limit simply used optimizations or heuristics, I think the time limit should be increased.

Wu how did you solve the third? I see you got lightning fast solution:D ?

@neal_wu: it was enough to use double for slope and not check tolerance at all....I used fractions to evade tolerance and it made my program too slow....the limit SHOULD be up...

i agree

LOL my 2nd fails for:

1
1 1

and

1
1 1
2 2

But passes for the test example from the problem statement :D

heh mine fails for
4
0 0
1 1
2 2
1000 1001
for sure, and the right solution works for anything, but the limit is too low for it :D
Not to mention that n^3 works for 85...

Can somebody tell's what am I getting wrong. I find the length of the array from that I can form with any k numbers power that will beat Frank. I don't know what's wrong. Someone take a look at my code please. ;)

turgond - you're right; I just submitted a "dumb" solution that compares doubles for equality and passed all the test cases. It fails this case though:

3
0 0
-999999999 -1000000000
1000000000 1000000001

by printing 3 instead of 2, because 999999999 / 1000000000 and 1000000000 / 1000000001 differ by only about 10^-18, which is more than the accuracy of doubles (and is also why I decided to submit an exact integer solution, which instead conveniently resulted in TLE :P).

vasja: I just submitted an O(P^2 * O) solution, which uses a faster method of computing the distances to the nearest neighbor. (Several other people seemed to have done this as well.)

In fact, the test cases are extremely weak - boba5551's code just compares slopes using integer division and passes all the test cases.

Also, since the problem states that "X and Y are known to be in the range of signed int," I assumed that there could be coordinates around 1 or 2 billion and thus used long long to multiply numbers, while many other people with very similar solutions managed to run in time because they used int.

I've done some tests and found that all the coordinates are actually in the range [-20000, 20000]. If a number in the input is at most 20000, please don't tell us that it can be up to 2 billion.

@neal wu: same here, I used fractions to compare accurately, because using tolerance couldn't help with:
3
0 0
1 1
1000000000 1000000001
But it was user-made contest, not by z-trening administration :)

Sure - I am just requesting problem setters to try to make sure that in general, constraints given in the problem are as accurate as possible, since different constraints often require very different solutions.

I have solved the task z-Attack, and It counted it as solved but on my profile

under solved problems there's nowhere the task name.

P.S not only this task,

Anyone else have this problem?

well, I submited all tasks again , and they appeared.