I_love_tigersugar's blog

TopCoder SRM 636
By I_love_tigersugar, 10 years ago, In English

Tomorrow, the next SRM will be held at 07:00 EDT. Don't miss!

Have a nice SRM. Good luck :D

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

»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

7 AM
SRM
Makes me regret
Choosing STEM

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Can anyone tell me how to solve div1 500? Looks rather tricky for me.
I've seen several solutions, but still haven't got the whole idea.

UPD: OMG, second problem in last few weeks in which there's such "shortest-distance" graph is constructed and I don't manage to understand that the cycles can be only of length 2. Hopefully, I won't forget it next time.

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

    The number of connected components depends on the number of cycles. It can be proved that there exist only cycles between 2 vertices. Hence, we can reduce the problem into calculating the expected number of cycles between 2 vertices.

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

      calculating the expected number of cycles between 2 vertices.

      I got this far, but how to solve this kind of problem?

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

        For each vertex you can sort other vertices by priority (first distance, then y coordinate, then x).

        Then for each pair of vertices you want rabbits to NOT be in the cells that have higher priority compared to the picked vertices in at least one of the list.

        If there are n places for rabbits, r rabbits and e cells must be empty, the chance for that is C(n - e - 2, r - 2) / C(n, r) (two picked cells are already occupied by rabbits, which leads to minus 2). Add this chance to ans for each pair.

        That's O(n^6), not sure if it's quick enough, as I didn't implement it during the contest :c

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

      but the problem said the graph is undirected, so the cycles are edges between two points or not?

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

    A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees. Therefore number of components is equal to the number of cycles of size two.

    Expectation of this value is equal to sum of probabilities for every two empty cells of grid to form a 2-cycle. Two points form a 2-cycle iff no point is closer to the first point than the second, and vice versa; so, all points must lie outside some set. The probability for this is Csr - 2 / Cpr, where s is size of the set, p is number of empty cells.

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

      Congratulations for the victory!

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      There exist people who denote Newton's symbol using that weird notation with Cij :OO!

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

        This notation is widespread in Russia.

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

      "A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees.". What if the connected component is a cycle of size 3, like 1 -> 2 and 2 -> 3 and 3 -> 1? It does not contain cycle of size 2.

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

Hmm, 1000 didn't seem tricky or really hard to me this time (meet in the middle), I wonder if the fails were due to TLE on constant/log factor...

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    I think so too. If you had implemented it, you'd see that the time limit was very tight.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      I did implement it actually, but didn't manage to debug it in time :D

      (and now, I'm getting Uncaught exception in the practice room on something that should totally pass: an assignment in an existing map memlimit exceeded — speaking of which, didn't TC use to report memlimit exceeded specifically?)

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

    Yes, there were not enough time for me to make one simple optimization. And that's why my solution failed during contest

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

I was never able to solve the task 250 in regular DIV 1 (I solved some in TCO) during contest, but today I solved the task 500 :D

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

    But in SRM 635 you was able to earn 0 points but increase your rating, that looks strange :o

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

      Yeah, and not only my rating increased. It's pretty funny. Do nothing and earn points. :D Nowise it does not give much satisfaction, at least not me. I prefer well-deserved successes.

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

        Well, rating systems can act weird in unexpected situations (in this case, tricky 250). How much did you gain exactly?

        In a sense, you did well by not losing points :D

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

          I gained 4. xD

          And several contests ago in TCO 2A I gained 81 (also doing nothing), but then I was grey.

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

            Well yes, a grey user isn't really expected to get to round 2, so it's normal to gain rating just by being there.

            Getting +4 is like nothing at all... so it's not really a fail, I guess.

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

        It's always better try, than do nothing :)

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

can somebody explain, how to solve div2 1000?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • Binary search the lower bound of the minimum sum of the 16 sub-rectangles
    • brute force the 3 vertical cuts
    • greedily pick the horizontal cuts in order to exceed the lower bound
    • total complexity O(n^4 log n) .. using pre-calculated partial 2D sums
    → Reply