Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Koptanovia's blog

By Koptanovia, history, 3 months ago, In English,

Problem Statement: http://codeforces.com/gym/100623/attachments/download/3210/20082009-acmicpc-neerc-northern-subregional-contest-en.pdf

Problem F: Fenwick Tree.

"Let us call an array self-fenwick if it coincides with its Fenwick tree. For example, the array (3, −1, 4, 1, −5, 9) above is not self-fenwick, but the array A = (0, −1, 1, 1, 0, 9) is self-fenwick."

fenwick tree of array A = (0, -1, 0, 1, 0, 10). How do these 2 arrays "coincide"?

Any help / hint is greatly appreciated.

Thanks!

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

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it
F[1] = A[1] = 0
F[2] = A[1] + A[2] = -1
F[3] = A[3] = 1
F[4] = A[1] + A[2] + A[3] + A[4] = 1
F[5] = A[5] = 0
F[6] = A[5] + A[6] = 9

F = {0, -1, 1, 1, 0, 9}