P___'s blog

SRM 731 — starting in less than 2 hours
By P___, history, 7 years ago, In English

Hi,

Since nobody has mentioned this SRM, I do that here:

Time.

I am not the author, just want to increase the number of participants.

Thanks!

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

Comments Comments (13)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what can be done when the applet says "A connection to the server cannot be established" when I try to login? I tried autodetect, it doesn't work. It was working well a few weeks back.

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

Thank you so much for posting this! I always miss SRMs, and finally get to compete in one. GLHF everyone!

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

Does anyone have proved solution for 1000?

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

How to solve medium? (I have O(k3) with small constant which gets AC in 1.6s)

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 5   Vote: I like it +21 Vote: I do not like it

    Unable to parse markup [type=CF_TEX]

    is an expected sum of heights of nodes in tree with i nodes.

    dpi is an expected sum of length of paths in tree with i nodes.

    Unable to parse markup [type=CF_TEX]

    by linearity of expectation.

    Similary,

    Unable to parse markup [type=CF_TEX]

    because sum of length is sum of length in both subtrees and sum of length of paths going through root.
    → Reply
»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

About Div1 Hard.

My solution was to look at only Pareto-optimal choices. First, we sort the friends by decreasing number of bits set. After that, we recursively pick or kick them in that order. The single important check which makes it run faster than like

Unable to parse markup [type=CF_TEX]

is as follows: if we kick a friend X, we also have to kick all further friends which have a subset of X's skills (otherwise, the choice wouldn't be Pareto-optimal).

In practice run, this takes <100ms on all the given tests. Can someone please either construct a test where this becomes slow, or prove a reasonable asymptotic bound for the number of Pareto-optimal choices?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    What about all (

    Unable to parse markup [type=CF_TEX]

    ) masks with 4 bits? Then it will be like

    Unable to parse markup [type=CF_TEX]

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

      Challenge succeeded :) .

      A pity you were not in my room.

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

        I wanted to challenge you with this exact test..

        However, I was so stupid that I did not know paste in TC is ctrl+v (while in macOS is it command + v). :P

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

    On all vectors with 4 1-bits out of 8 it will be 708 / 8! ≈ 1010

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

how to solve div2b

→ Reply