hmehta's blog

By hmehta, history, 7 weeks ago, In English,

Hi!

Topcoder SRM 754 is scheduled to start at 07:00 UTC -4, March 30, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Editorials: https://www.topcoder.com/blog/single-round-match-754-editorials/

Thanks to misof for setting the problems and adamant for testing the round.

This is the sixth SRM of Stage 3 of TCO19 Algorithm. This stage will also help you qualify and win reimbursements/tickets to TCO19 Regional Events.

Stage 3 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 755 — April 09, 21:00 UTC-4

Stage 3 Leaderboard

All the best!

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Gentle Reminder: Match begins in less than 40 mins :)

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Forced to solve 1st, left contest after reading 2nd xD

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When I opened Medium, I immediately scolded myself "Why didn't you go for the Hard strategy if Medium is 600 and obviously geometry?"

    Upon reading it, I asked myself "How would I write a checker for this?", and it was clear in couple moments. Then, not having any better idea, I spent rest of the contest tweaking a random walk solution. It didn't even get through Challenge phase :-)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Didn't you just miss n=1? A random walk solution should absolutely be possible, I had one that was fast enough.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +46 Vote: I do not like it

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          >yfw

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it +60 Vote: I do not like it

            Hi Xellos, long time no see. You have a nice CF rating, would be a shame if I organised a contest and something happened to it.

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it +21 Vote: I do not like it

              I'll bet you $1000 you can't do that.

»
7 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Ouch. It's been a while since I misjudged the difficulty of a problem this badly (div1 "medium").

Wait, should I blame the tester for solving it reasonably quickly? ;)

Nah, it's all my bad, and I'm sorry it all turned out this way. We are definitely aiming for much easier medium problems than this one.

I'm especially sad here because I'm quite fond of the hard problem and this way almost nobody had the time to attempt it. Hopefully you'll give it a shot in the practice room :)

If you have the time, I would like to hear your experience with this div1 medium so I can recalibrate my "difficulty estimator" for the future.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought it wasn't too hard, but since I didn't manage to pass the last sample, my opinion is clearly not too reliable. The starting idea (2*number of slopes and n=1) was obvious to me, at least.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    Apparently, I think this Div1 Medium is a great problem and I appreciate it. I even feel questioning why this announcement blog is not highly rated. I feel like my favorite is Div1 Medium rather than Div1 Hard. And also, I could only solve Div1 Medium during the contest.

    In my opinion, I think this problem is not so difficult for Div1 Medium. When I realized that $$$n$$$ equals $$$2 \times$$$ (the number of species of line passing point $$$i$$$ and $$$j$$$), it became a simple construction problem. This was an interesting part of this problem, and I realized in less than 10 minutes.

    Why did it became a simple construction problem? That's because we can divide points into "line set" (let the size $$$s_1, s_2, \dots, s_k$$$), and when $$$S = s_1 + s_2 + \cdots + s_k$$$, it will hold:

    $$$n = S(S-1) + (s_1(s_1-1) - 2) + (s_2(s_2-1) - 2) + \cdots + (s_k(s_k - 1) - 2)$$$

    So I could move to implementation when half of the contest ended (note that I spent quarter of the contest for Div1 Easy). But I made a mistake in "how to place lines without clashing slope". The implementation was not difficult, but I made wrong answer in test of n=100, and I didn't know why I got wrong answer and what is wrong with it. I didn't realize what was wrong, until I wrote the output-checker of my program.
    I think that this is why few people solved this problem. I see that many of participants for this problem was "compiled".

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got that construction reduction as well, but I don't really understand your solution. What sizes are the $$$s_i$$$ denoting exactly? Are you saying there are $$$k$$$ different line slopes and the number of points on the $$$i$$$th line will be $$$s_i$$$?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Yeah, the meaning of $$$k$$$ and $$$s_i$$$ is exactly what you're saying. Additionally, if $$$s_i = 1$$$, it is just a single point.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Wait, should I blame the tester for solving it reasonably quickly? ;)

    Oops, I forgot to warn that I'm non-representative sample :)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No worries, any sample of size 1 will have that property :)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, the editorial regarding Med. Div 1.

      The unit circle part is not clear. And also which segments it is referring to. And those two lines seems to be the crux to the solution.

»
7 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

I dont know if topcoder works like this. But if it is, then they need to change.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What exactly seems wrong to you? On both TC and CF successful hacks usually added to systests.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +42 Vote: I do not like it

      The "we keep it simple" thing? It sounds as though the systests were intentionally made weak. Hope they're not.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry! My idea was to point that successful challenges are added to systests.In the tests we make sure all the cases are covered. Sometimes in 1-2 contests in an year things happen where a tricky test case gets added.

        The idea was to point out that we are trying to not to make div2 hard as unsolvable. :)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm opening 900 over a 600 every day of the week (was 30 mins away from solving it too). It's just the extra value added to the normal 250-500-1000 makes me panic. Also, the opposite is true. Nice problems, thanks.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div1-Easy?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +7 Vote: I do not like it

    I'm sure the editorial will be better, but here's my idea if you cannot wait. I solved in practice room. Define S as the set of points, and N = |S|. Since N<=3000, it means an O(N^3) algorithm is no good. So you cannot check every 3 points, see if they are part of a square, and find the 4th. That would be too easy.

    Instead we take every distinct pair of points, which is O(N^2). For each pair of points A, B, compute the two other points C, D that make a square ABCD. Test if C and D are in S, this can be done with set<> data structure in O(log(N)). If C and D are both NOT in S, or both IN S, then move on. Otherwise the one which is NOT in S will be adding a new square, so add it to some other set T.

    Final answer will be |T|. Even if somehow every pair results in one point added to T, that is O(N^2) additions, but set operations are logarithmic and O(log(N^2)) = O(log(N)).

    Total time is thus O(N^2*log(N)). Can make it O(N^2) with unordered_set<> but it's not necessary to pass.

    For the geometry to compute the other points C, D, I had to google formulas because I don't like geometry. But as usual top guys implemented something in 10% of the code that I needed, and I don't understand it yet...

    Edit: for a really clean implementation, look at Egor's fastest solution, done in 6:38.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Edit: Nevermind, I just figured out the bug. I was adding last element twice which was causing the bug.

      Hi royappa, I have implemented the same idea in Haskell, but getting wrong answer for test cases.
      101 cases checked, 10 failures, 0 errors Failures: 20, 3, 35, 5, 6, 60, 61, 69, 76, 82
      The tool I am using is gettc[2] to run Haskell solution. The idea is, I generate all pairs of points and compute two other points according to given formula on mathstack[1], and simply check them according to rule. If both are in the set, or both are not in the set then continue, else add the one which is not in set and continue.
      Case 20 ... 4933ms Failed Input: <2971, 826, 7180, [638, 781, 538, 275, 145], [3828, 3214, 830, 6847, 6316]> Expected: <1884> Received: <1883>


      module MoreSquares where import qualified Data.List as List import qualified Data.Set as Set type Point = (Int, Int) addTuple :: Point -> Point -> Point addTuple (a, b) (c, d) = (a + c, b + d) genPoint :: Point -> Point -> [Point] genPoint (a, b) (c, d) = [u, v] where p = (-(d - b), c - a) u = addTuple (a, b) p v = addTuple (c, d) p countPoint :: [(Point, Point)] -> Set.Set Point -> Set.Set Point -> Int countPoint [] sfull s = Set.size s countPoint ((a, b) : xs) sfull s = ret where [fpoint, spoint] = genPoint a b ret = case (Set.member fpoint sfull, Set.member spoint sfull) of (True, True) -> countPoint xs sfull s (True, False) -> countPoint xs sfull (Set.insert spoint s) (False, True) -> countPoint xs sfull (Set.insert fpoint s) (False, False) -> countPoint xs sfull s countLocations :: Int -> Int -> Int -> [Int] -> [Int] -> Int countLocations n sX sY xprefix yprefix = ret where xlast = List.last xprefix ylast = List.last yprefix x = List.take n (xprefix ++ iterate (\x -> mod (x * 47 + 42) sX) xlast) y = List.take n (yprefix ++ iterate (\x -> mod (x * 47 + 42) sY) ylast) s = Set.fromList (zip x y) ppoint = Set.toList s zippoint = [(p, q) | p <- ppoint, q <- ppoint, p /= q] ret = countPoint zippoint s Set.empty

      [1] https://math.stackexchange.com/questions/964625/find-3rd-and-4th-co-ordinates-for-a-square-given-co-ordinates-of-two-points
      [2] https://github.com/seri/gettc

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hmehta (previous revision, new revision, compare).