Since there's no related post about this, I'd like to post this to remind you all:

Topcoder SRM 634 will be taken place in 40 minutes.(Since now CST 08:20) LINK.

Don't miss the Round.

We can discuss the problems here after the round.

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | tourist | 176 |

7 | sus | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | SecondThread | 169 |

Since there's no related post about this, I'd like to post this to remind you all:

Topcoder SRM 634 will be taken place in 40 minutes.(Since now CST 08:20) LINK.

Don't miss the Round.

We can discuss the problems here after the round.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2021 09:38:19 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Too early in Belarus. 4 AM

In Poland, it was about 3AM, but I participated :)

Me too, but in result during challenge phase I copy-pasted wrong array and lost 25 pts instead of getting +50 :P. But piob took 2nd place solving all the problems!

Aha，same here. (Create a test data in a hurry, which made me pay for my carelessness.)

Any one has an idea how to solve 1000?

The idea is to try every segment (i.e. place the line so that it overlaps the segment, the rotate it by a little bit). We can show that every line in the plane can be reduced to one of those O(N^2) lines above.

We now want to process each line in constant time or logarithmic time. To iterate through all these configurations efficiently, fix one point, then sort the other points by angle around that one point. Then, rotate around the endpoints, keeping two pointers at a 180 degree angle. All we need to do is find way to update the cost of the segments we cut in constant time. The cost is defined as (x_1 — x_2)^2 + (y_1 — y_2)^2, and expanding gives x_1^2 — 2x_1x_2 + x_2^2 + y_1^2 — 2y_1y_2 + y_2^2.

For now, let's focus on only x-coordinates. If L2 is the sum of squares of x coordinates on the left side of the line, L1 is the sum of x coordinates, and L0 is the number of points (similarly define R2, R1, R0 for right side), then our total cost is L2 * R0 — 2 * L1 * R1 + L0 * R2. Similarly, we can get the y coordinate score like this as well and just add the two together.

Now, updating these sums is relatively simple as we're rotating around, and rotating around each point will take O(N) time total. Since we need to sort before, the total running time of this solution should be O(N^2 log N)

For me it was a good round. Two successful hacks while lying on my bed and 6th place in DIV 2.