HandIeNeeded's blog

By HandIeNeeded, 5 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Too early in Belarus. 4 AM

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any one has an idea how to solve 1000?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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)

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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