Блог пользователя jonathanirvings

Автор jonathanirvings, история, 19 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
19 месяцев назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
Insects
  • »
    »
    19 месяцев назад, # ^ |
    Rev. 5   Проголосовать: нравится +30 Проголосовать: не нравится

    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
»
19 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
a more natural way to derive the formula in Circuits imo
  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

Spoiler
»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
A question about Radio Towers
  • »
    »
    19 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится
    Spoiler
    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! I have another question though.

      Another question
      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Spoiler
»
14 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hi! I'm sorry for necroposting.

I'm questioning, is there another editorial for day 1, problem Towers? Official editorial was difficult to understand, and I wonder if anyone has better explanation for >60 points solution?