jonathanirvings's blog

By jonathanirvings, history, 6 weeks ago, In English

IOI 2022 Task Discussion (Editorial) is now available here. The link has been posted in the IOI 2022 Tasks page as well.

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

»
6 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it
Insects
  • »
    »
    6 weeks ago, # ^ |
    Rev. 5   Vote: I like it +30 Vote: I do not like it

    In fact, I think the bound of the binary search solution will exceed $$$3N$$$ (at least when $$$N$$$ is large enough and the interactor is adaptive), and it's hard for me to imagine a simple optimization which could lead to a $$$3N$$$ bound (which has a formal analysis and is either deterministic or with $$$1 - \epsilon$$$ probability).

    My attempts, though failed
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
a more natural way to derive the formula in Circuits imo
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    This is also how I derived it. However, after reaching this form, we can find a more natural way to rephrase this in terms of probability.

    Let $$$p(u)$$$ be the probability that a random assignment makes $$$v$$$ evaluate to $$$1$$$. Then, we claim that $$$p(u)$$$ is the average of all $$$p(v)$$$, where $$$v$$$ ranges through all children of $$$u$$$.

    Proof: Let $$$c$$$ be the number of children of $$$u$$$. $$$p(u)$$$ equals $$$\frac{1}{c} \cdot$$$ (the sum of $$$i \times $$$ probability that exactly $$$i$$$ children are black). This is equal to $$$\frac{1}{c} \cdot$$$ the expected number of black children of $$$u$$$. By linearity of expectation, we have the desired conclusion.

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

    Yeah, it was such an easy cheese with generating functions. Not a fan of this task

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Thank you for the quick editorial! I really liked the task Thousand Islands.

Spoiler
»
5 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it
A question about Radio Towers
  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +16 Vote: I do not like it
    Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I have another question though.

      Another question
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Spoiler