Temotoloraia's blog

By Temotoloraia, history, 3 years ago, In English

Does anyone know the live standings of IZhO 2022?

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Today and tomorrow IZHO 2022

»
3 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

standings of day 1

»
3 years ago, # |
Rev. 6   Vote: I like it +15 Vote: I do not like it

How to solve A?

Spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +

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

    DP on substrings

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +56 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you have the other tasks too?

»
3 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

IZHO 2022 day 1 problem A really difficult for me

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Does anyone know the standings of IZhO 2022 day 2?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

standings of day1 + day 2