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

Автор Temotoloraia, история, 3 года назад, По-английски

Does anyone know the live standings of IZhO 2022?

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Today and tomorrow IZHO 2022

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

standings of day 1

»
3 года назад, # |
Rev. 6   Проголосовать: нравится +15 Проголосовать: не нравится

How to solve A?

Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    +

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    DP on substrings

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +56 Проголосовать: не нравится

    Let's look at the difference between adjacent elements.

    Assume that $$$b_i = a_{i+1}-a_i$$$, and now our task will be to remove equal neighbors, and put the doubled value instead.

    Now let's do some dynamic programming here, $$$dp_{l, r}$$$ — which determines whether we can remove a subarray $$$b_{l \dots r}$$$.

    The observation is that, for the fixed $$$l$$$, there at most $$$log_2(n)$$$ such $$$r$$$. Hence, for each $$$l$$$, we can just maintain a set that stores those rightborders. Try to come up with transitions by yourself.

    After calculating these $$$dp$$$ values, the problem can be solved with another dynamic programming. $$$d_i$$$ — minimal length of after performing operations on prefix $$$b_{1 \dots i}$$$. Answer to the problem will be $$$d_n$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you have the other tasks too?

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

IZHO 2022 day 1 problem A really difficult for me

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Can anyone tell me IZHO 2022 day 1 problem B and problem C

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Does anyone know the standings of IZhO 2022 day 2?

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

standings of day1 + day 2