Stream_Cipher's blog

By Stream_Cipher, history, 4 weeks ago, In English

This is the original version of problem ,during the contest I tried to solve it using some combinatorics logic but i can't and for this version of problem we can just iterate over all possible PIN codes because constraints are small, yes i didn't able to get this logic during the contest, but i am curious to know the approach to solve this question if PIN size will be of 10 digits.

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Same here.. I was about to start a post on this. I am finding it difficult to find a way of formulating the case of avoiding identical PINS. Somehow, I feel that the formula for Permutations with Repitition will come into use.

»
4 weeks ago, # |
Rev. 5   Vote: I like it +1 Vote: I do not like it

I was curious about this too (and I am skeptical to think this is the only better way), but we can do pins of slightly larger size using bitmask dp:

Let dp[i][bm] = the # of "good" strings of length i where bm = the digits that are used (a 10 bit number where 1 in a bit position indicates that digit was used, 0 otherwise). Then we can see that the transitions are:

// we decide to use this digit in position i, and the digit is of type 'o' or '?'

dp[i + 1][bm | (1 << digit)] += dp[i][bm]

Then we use the string they gave us to precompute the "good" bitmasks (aka, if the string they gave us says that we need a digit in our string, then we only look at bitmasks with this bit on). This gives us a runtime of doing digits * 2^10 * 10 operations, which should be able to handle 10 digits.

https://atcoder.jp/contests/abc201/submissions/22653905 is my submission for this (using this idea), although I am willing to hear other (probably better) solutions

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Exactly , I did this question in the exact same way using bitmask recursive dp.

    My dp is like dp[i][mask] represents the no of pins which do not have a digit masked as 'o' in the string then i finally subtracted from all possible pins

    i.e. pow(no of digits having 'o' or '?', 4 )-dp to get the final answer.

    You can see my submission here My bitmask dp submision

    since the dp is of type dp[4][1024], if we increase the digits in pin-pattern , the complexity would be O(no. of pin-pattern digit* pow(2,10)).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can see my submission.I used basics of combinatorics.link