chrome's blog

Topcoder Single Round Match 674
By chrome, history, 9 years ago, translation, In English

Hi there!

Tomorrow at 05:00 MSK, will be held Topcoder SRM 674.

Let's discuss problems after contest.

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

Comments Comments (21)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Yaaah..... Hope the Problems will be interesting

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wake up people, registration is open!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain their solution to 1000? I couldn't understand what the AC codes were doing.

→ Reply
»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

|num| <= 20 and O(N) passes...

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

    That constrain was totally deceiving >_<

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

    Sorry for that. We will not use this kind of misleading constraints anymore.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +220 Vote: I do not like it

      Why? The constraints made the problem fresh. I started from bitmask, realized 3^20 is too much, moved to combinatoric solutions and finally realized it's greedy one. We're too used to think solutions along with constraints.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +39 Vote: I do not like it

        I'm kind of surprised to see in fact more people like this unconventional setting. So maybe we can try more 'fresh' things in SRMs in the future.

        Thanks for your feedback (and 182 people who liked it).

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it +31 Vote: I do not like it

      on the contrary, such constraints make the problem more interesting, at least to me, because we do not have much information about expected complexity, thus encouraging fresh, unbaised solutions.

      This is one of the things i have liked about TC problems :)

      → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

My code:

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My solution to Div2 500: O(n^4)

The question can be rephrased as:

"Place the origin the orient the coordinate axes in such a way that you get maximum points on the axes"

So we know that if we have 3 distinct points, then we have can place the axes in such a way that the x-axis lies on 1st two points and the y-axis lies on the 3rd point. (This is because you can always place the coordinate axes in such a way that vertices of a triangle lie on the axes). So iterate over all triplets in O(n^3) and for a particular triplet, check how many points lie on the axes including these 3. The maximum will be the answer. I did a small silly mistake but my code passed the system tests later on. Hence overall complexity = O(n^3 * n) = O(n^4)

Code: http://ideone.com/vdyaTI

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

    Thanks, I gathered something like that from the solutions, but I keep thinking about the case where you have 3 points on a line, for this case the placement of the origin is still not certain as it could be translated along the y axis as much as you want and still contain all 3 points.

    Could you help me understand why it works in this case?

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

      Just like I said, we have a triplet of points (a,b,c) then we can assume that a and b lie on the x axis and c passes through the y-axis.

      In the code, I have considered all possible triplets hence, all 3!=6 triplets will occur corresponding to (a,b,c) and therefore no case will be missed out.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Also, what exactly was the solution to Div 2 1000? No one actually solved it so I think it must have been a tough one. cgy4ever's solution suggests that it was DP+Bitmask.

Can anyone explain the solution?

→ Reply
»
9 years ago, # |
  Vote: I like it +24 Vote: I do not like it

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with my D2 500? http://www.textsnip.com/13653a

I couldn't think of the integer-only solution. So instead I do this:

  for (each point p)
     translate all points so that p is at the origin
     for (each transformed point q)
         a = angle of q
         rotate all points by angle 2pi-a, so that q is on an axis
         count number of points on x/y axes using 1e-8 precision

I have a test case it's failing on, so I can figure it out eventually. But just wondering if it is the approach or is it the precision? Thanks!!

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

    According to your algorithm, if the test case consists of 4 points that lie on the vertices of a square then your answer will be 3 but the correct answer should be 4. (If you keep the origin in the center of the square)

    Test case your code fails on: http://ideone.com/4yLHqN

    → Reply