GOJO_GOKU_KURAMA's blog

By GOJO_GOKU_KURAMA, history, 6 months ago, In English

https://codeforces.net/problemset/problem/243/A Hey cfers can anyone please provide me with an simple editorial for this problem. Thank you

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea is prefix or of array the values can change atmost 20 times, so iterate over all the prefix and mark all the distinct values occuring in the prefix or. TC will be O(20 * n) or O(1e6) as there are only 1 test case

code
  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think a simpler implementation is to maintain a set of all currently possible trailing possible values of bitwise OR i.e. if we are at index i our set has all possible values of f(l, i) for l <= i, this set can never have size more than 20.