abzaloid's blog

By abzaloid, 11 years ago, translation, In English

Hi there!

Problem from past regional olympiad: There are N ≤ 5000 distinct points |xi|, |yi| ≤ 104 on the plane. You are asked to find the number of different right triangles, where the vertices are from N points.

TL: 2s, ML: 64MB

Thanks

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

»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Denote a right triangle as with the right angle at vertex . Try choosing each point as . Sort the other points by angle around it, then try choosing each point as (in sorted order) and use 2 pointers to keep the range of points which are at 90° to it (candidates for ). Time: due to sorting.

Can be improved to O(N2) — if we choose , there are just N interesting lines (the ones perpendicular to some ), and we need to count the points lying on each of them; that can be achieved using hashmaps.

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

    Can be improved to O(N2)

    Still not so good, because of GCD calculation.

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

      So, how can it be improved, maybe converting to unit vectors?

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

        Well, in such a case you'll be dealing with floating-point numbers. If you want to hash them, you need to round them first. It's inherently not a very good thing.

        You can still do it, but you need to calculate the needed precision for rounding first.

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

          Do you have any other suggestions?

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

            If you really want to do something, you can implement all of the three solutions and choose the fastest one :).

            Or you can try to prove that this problem can be solved only in ω(n2) time :).

            None of these ideas is really serious, though.

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

      Good point. I considered the coordinates to be O(1), since they're pretty small, but even if they weren't, they're limited by int size anyways, and there's a large constant factor in the hashing solution anyways. I estimate guess that even if we had all |x| and |y| coprime, we wouldn't get a serious boost in complexity. And the is actually quite fast, because it stands on quicksort, which can have a really low low constant factor (in a contest, I'd code that immediately).

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

        For N=5000 it seems not the optimal solution

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

          Many contests in Kazakhstan are not prepared well, you must know it. There can be no maximal test cases or the solutions can be run and checked manually, ignoring the limits. So, from exactly what contest did you take this problem from?

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

              It's obvious that arti's solution is exactly the same as was described by Xellos (with hashtable).

              But why didn't you try just to run the solution? I've done this and the result is exactly what should have been expected: TLE (my laptop is obviously much more powerful than the judges' machines in 2008).

              BTW, the solution with sorting is really faster, when implemented correctly.

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

                I've also tried to run my solutions but got TL with different methods: using gcd, unit vectors and just angles, all of them give me TL. I will try to do it using quicksort, but how to be sure that solution will not give TL for N = 5000?

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

                  You can't be 'sure' with anything, but you can speak from experience — some solutions passed 372C - Watching Fireworks is Fun. The runtime depends a lot on what the algorithm actually uses, and quicksort is... well, quick. And 2 pointers also have a low constant.

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

      GCD could be precalculated in O(n^2) for all a,b<5000

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

        They're up to 104 here, but yeah, with some tricks like first few steps of GCD + precalc, that'd work pretty fast, too.

        The question at this point is rather whether there's a solution that takes O(N2) when the coordinates can be arbitrarily large (provided we can do constant time arithmetics on them).

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

          The question at this point is rather whether there's a solution that takes O(N2) when the coordinates can be arbitrarily large (provided we can do constant time arithmetics on them).

          Such a solution does exist. I've asked a question in Russian yesterday and Igorjan94 has given me a link to an article.

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

I've come up with some ideas that tell me that this problem should be solvable in O(n2). I'll describe the solution when it'll be ready.