shashank21j's blog

By shashank21j, history, 9 years ago, In English

Week of code https://www.hackerrank.com/w16 is starting soon 6 July 16:00 UTC. Please join.

Monday to Friday Every day 1 challenge will go live.(Easy to Hard)
Score decreases by 10% at the end of every 24 hours.
Your submissions will run on hidden test cases at the end of every 24 hours.
time of each challenge will be counted since open, it allows you to start late.

Top 10 get T shirts.

GL & HF

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

»
9 years ago, # |
Rev. 4   Vote: I like it +26 Vote: I do not like it

Contest has ended, and I'd like to share my approach to last problem — White Falcon and XOR. It took me almost two days to invent, and it differs from the one in editorial.

Suppose we already know about dynamic programming that runs in 64 * N * (N - 1) / 2 — for every possible value of xor-sum (which can be 0..63) keep number of ways to produce it. When we want to extend current segment to the right, update DP in the following manner:

for val in range(64):
  next[val ^ a[position]] += dp[val]
  next[val ^ b[position]] += dp[val]
for val in range(64):
  dp[val] = next[val]
  next[val] = 0

(position is the endpoint of current segment).

Now we want to speed this up. We can notice that:
1. When we xor numbers 0..63 with a number X, we get numbers 0..63 in shuffled order (the only exception is X = 0, which does not permute anything).
2. Since we have exactly 64 states in our DP, we can denote it as a single unsigned long long value. Actually, we will keep track of what states are "reachable", i.e. dp[v] = 1 if we can achieve a xor-sum equal to v, else dp[v] = 0.
3. Let's look at DP updates separately for array a and array b. Good news are, "reachable" DP states are either "reachable" in one case, or in both. In other words, we can't possibly have dp[i] updated by, for example, a[position], but not updated by b[position].
4. Xor operation with a fixed value V can be viewed as shuffling some blocks of lengths 2i, where i-th bit is set in V. For example (with integers up to 7):
x: 0 1 2 3 4 5 6 7
x^6: 6 7 4 5 2 3 0 1
We can do this in two steps (subject to 6 = 1102):
- Permute two blocks of length 22 = 4: 4 5 6 7 0 1 2 3
- Now switch places of every pair of blocks of length 21 = 2: 6 7 4 5 2 3 0 1
Therefore, we can use some bit operations with unsigned long long's to compute out modified DP and get all "reachable" states. The pseudocode is like:

get_next_state(state, V):
  for i in 5..0:
    if i-th bit is set in V:
      low_half = state & 11..100..011..100..0 // here each block of same bits has length 2 ** i
      high_half = state & 00..011..100..011..1
      state = (low_half shl 2 ** i) OR (high_half shr 2 ** i)
  return state

Taking point 4 into account, we now can see for each segment L..R whether 0 can be reached. It takes 6 * N * (N - 1) / 2 operations to do that.
Now remember point 3. It implies that every original DP state have value of the form 2k, and it can only be increased. Let's keep track of current k. When L = R set k = 0. Then, if the modified state for a[position] is equal to modified state of b[position], increase k by one. Otherwise, it stays the same.

My code for reference: link. It runs in 1.73 seconds almost on all testcases.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, this is a very nice solution. Thanks for sharing.

»
9 years ago, # |
Rev. 3   Vote: I like it +34 Vote: I do not like it

I have not author's solution for last problem too.

At first, let's say that we have another two sequences: a and c, where ci = ai ^ bi. Then element of sequence wi will be either ai or ai ^ ci ( = bi).

So the answer for segment [L, R] (number of sequences w1, w2, ..., wR - L + 1 such that w1 ^ w2 ^ ... ^ wR - L + 1 = 0) will be number of subsequences of c such that ci1 ^ ci2 ^ ... ^ cik = aL ^ aL + 1 ^ ... ^ aR, L ≤ i1 < i2 < ... < ik ≤ R. Why so? Suppose we have elements from b in w with indices i1, i2, ..., ik and w1 ^ w2 ^ ... ^ wR - L + 1 = 0. We can replace every bj with aj ^ cj and get aL ^ aL + 1 ^ ... ^ aR ^ ci1 ^ ci2 ^ ... ^ cik, that is equivalent to ci1 ^ ci2 ^ ... ^ cik = aL ^ aL + 1 ^ ... ^ aR.

Let's fix left end of segment on i-th position and move right one from i to n. We can notice that now problem is similar to knapsack problem, which could be solved in O(N·MAX), where MAX is the maximum value of ai (64). But it's not enough, O(N2·MAX) is too much.

Suppose L is left end of our segment, i is current right end.

We can denote such interesting fact: if we had ci before in our segment (among cL, cL + 1, ..., ci - 1), then it's easy to calculate new values of dynamic: every value will be increased twice.

Why is it so? Suppose we have k values of ci before. How many are there subsequences with even number of occurences of ci? X·(Ck0 + Ck2 + Ck4 + ...) = X·2k - 1, because we should choose even number of places, where we take ci in our subsequence.

And after i-th index we have k + 1 values of ci. Similarly, number of subsequences with even number of occurences of ci will be X·(C0k + 1 + C2k + 1 + C4k + 1 + ...) = X·2k = 2(X·2k - 1). Similarly with odd number of occurences.

It's obvious that we are interested only if number of occurences is odd or even, not exactly in number.

Finally, solution is so: we fix left end of segment and move right end. If we meet new value, we calculate dynamic in O(MAX), otherwise we increase counter twice. Events of first type could happen at most MAX times, so we have O(N·(N + MAX2)) solution.

For more details see code