code_warrior's blog

Vasya and good Sequences
By code_warrior, history, 4 years ago, In English

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]

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Atleast provide the link to the question.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$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 :)

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

    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!

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

poor Vasya

→ Reply