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

Vasya and good Sequences
Автор code_warrior, история, 4 года назад, По-английски

This is the problem[This is the problem](http://Vasya and Good Sequences)Can someone explain me why it is so written in its tutorial that if the length of sequence is greater than 61 than we don't need to check the maximum condition![problem:1030E]

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

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

Atleast provide the link to the question.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

$$$a_i > 0$$$, so every number has at least 1 bit set. So over a segment of length 61 or more, we are guaranteed to have a sum $$$S \geq 61$$$. Since the maximum value for $$$b_i$$$ is 61, we can be sure that this segment has $$$S \geq b_i$$$.

Do comment back if you didn't understand something :)

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

    Ok, so it means that even in the worst case in a segment with more than 61 elements where only one element is 61 and all the rest 61 are 1,I will have my sum equal to or greater than 61 excluding the max (61). Thanks, for explaining!

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

poor Vasya

→ Ответить