Alohomora 2022 Problem Spidey Editorial

editorial
,
1

Problem D : SPIDEY
SETTER : lamda_cdm_10
TESTER :vishaaaal
Editorialist : lamda_cdm_10

DIFFICULTY

Medium

PREREQUISITES

SOS-DP , Bit Manipulation

PROBLEM

You are given an array and you are given queries in the form [ L ,R , X ] you need to find the sum of elements in the indexes (i) of the array where i|X=X where | is bit wise OR operator. The value of X for current query is (X+PREV) where PREV is the answer of the previous query PREV=0 for first query.

EXPLANATION

Let’s define a function F(R) which gives us the sum of values in the range [0-R] we can find the answer for this query by F(R)-F(L-1).
Let’s try to understand the implementation of F(R).
Check that the value of X can be very high but we require the bits which are at the right of MSB of (2*N) . so for each X can be take mod by (2*N) everytime.
We create the SOS dp table.
Now we go through the following conditions :smiley:

  • If R is less than 0 we simply return 0
  • If X is less than or equal to R we simply return dp[R][20]
    Now comes the condition where X is larger than R we need to analyze the cases carefully
  • We form 2 vectors that contain the binary representation of X and R+1 namely A and B respectively for each of the conditions we find the cases where the submask of X is strictly less than R+1.
    What we do now is try to traverse through from the MSB of X and analyze the conditions.
    For this we take a Variable pref = X and move from 0 to 20 .
  • if we find A[i] = 0 and B[i] = 1 that means we have to break from the loop as B is no longer the submask of A and add dp[pref][20-i] to result.
  • if we find A[i] = 1 and B[i] = 1 then we add dp[pref^(1<<(20-i))][20-i] to the result , what we have done here is find all the submask such that A[i] is 0 .
  • if we find A[i] = 1 and B[i] = 0 set pref^=(1<<(20-i)) because this bit needs to be 0 for A[i]

TIME-COMPLEXITY

The time complexity is O(Q*log(N)) as we expend log(N) time to answer each query.

CODES

SETTER'S SOLUTION

e1oU1m - Online C++ Compiler & Debugging Tool - Ideone.com

TESTER'S SOLUTION

2z98Gc - Online C++ Compiler & Debugging Tool - Ideone.com

Any other solution or feedback can be posted in the comments. We are always open for them . :smiley: