#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/c

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/c

Repovive

And and Or - Repovive Premier Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

3C. And and Or

1500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

Consider one operation on values $x=a_i$ and $y=a_j$ . After the operation we get $(x \& y,\ x \vert y)$ .

Look at one bit independently. If the bit values are $(0,0)$ or $(1,1)$ , they stay the same. If the bit values are $(0,1)$ or $(1,0)$ , after the operation they become $(0,1)$ where the AND side gets $0$ and the OR side gets $1$ .

So for every bit, the number of ones in the whole array is invariant. For every bit, the operation on indices $(i,j)$ acts like a compare-swap on that bit, producing $(\min,\max)$ for that bit.

Consider one operation on values $x=a_i$ and $y=a_j$ . After the operation we get $(x \& y,\ x \vert y)$ .

So for every bit, the number of ones in the whole array is invariant. For every bit, the operation on indices $(i,j)$ acts like a compare-swap on that bit, producing $(\min,\max)$ for that bit.