retired.coder.1's blog

Interesting problem! Need help.
By retired.coder.1, history, 8 years ago, In English

Problem Statement : Nimxor and Bit-Strings

Please help me with the above problem which is being placed in the DP category. Also there is no editorial provided for this problem.

Tags dp
  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My guess would be write a function that can perform integer division between the string given and an integer using a standard algorithm. Then for each of the numbers j between 1 and 100 inclusive store the result of the division between the string given and j. Say the result is stored in an array called dp. Finally assume we have stored the q integers that they gave in an array called A. Set the ans to 0 then for each A[j] add dp[A[j]]+1 to the answer. Also you would have to take the modulo of results repeated throughout the whole process.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is a 3 state dp problem where the states should be as follows:- (a) Index up to which str has been processed, (b) Value of the new str mod n and (c) Flag value z which stores whether a bit smaller than the bit str has been used or not till now. Overall complexity is (10000*100*2)*100 as there are 100 distinct possible mod values which will pass the time. Here is the AC Code : http://paste.ubuntu.com/24223122/

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

This problem could be solved with the natural approach involving a little bit of dynamic programming (basically memorization).

First, denote X as the decimal value of the bit-string. The number of bit-strings smaller than or equal to X which are divisible by n is simply the integer part of the division X / n, which is (X — r) / n, where r is the remainder part of the division X / n.

As we only need the answer in module MOD = 1000000007, we would need to compute X % MOD, r % MOD and 1/n % MOD (the inverse modulo of n in modulo MOD).

X % MOD could be computed in O(Nlog(N)), as X could be represented as a sum of power of 2, and each power of 2 can be computed in O(log(N)).

r % MOD is dependent on n. Thus for each n, we compute its r % MOD. This pre-computation takes O(Nn).

1/n % MOD is also computed for each n. This pre-computation takes O(nlog(MOD)).

Then, we can answer each query in O(1) time complexity with the formula (X — r) / n.

The overall complexity would therefore be O(q + Nlog(N) + Nn + nlog(MOD)), which is at most around 10^6 iterations.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You could also just use Python and preprocess all queries.

→ Reply