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]
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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]
Name |
---|
Atleast provide the link to the question.
$$$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 :)
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!
This is the accepted code, for your reference :)
poor Vasya