Блог пользователя elite_c0der

Автор elite_c0der, история, 3 года назад, По-английски

Recently I have given the Google Online Test. There were 2 questions that are to be done in 1 hr. Even after the contest I am not able to solve the question and now I need help for this question.

Problem

You are given a string S of length n. The string S consists of characters 0's and 1's only. For each subsequence for string s, you need to find decimal representation and display the number of distinct decimal values of the subsequences. display answer%1000000007. 1<=T<=10 1<=n<=10^5 eg 1 3 110 output- 5 Any help will be appreciated. Thanks....

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 5   Проголосовать: нравится +19 Проголосовать: не нравится

I have an approach for this problem.

Let total denotes, total number of distinct numbers possible.

Let one denotes, number of numbers in total in which if we append 1 at the end then the number will already be present in the total set.

Let zero denotes, number of numbers in total in which if we append 0 at the end then the number will already be present in the total set.

So, let's say we are at character i and

int newNumbers;
if(i == '1'):
    newNumbers = total + (total - one);
    one += (total - one);
    
else 
    newNumbers = total + (total - zero);
    zero += (total - zero);
total = newNumbers;

Think it like this Like If my total set contains 0, 1, 10. Then if the current character is 0 then the possible new numbers are 0, 10, 100 and two of these three numbers were already present in my set, so I have to remove them.

Code

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks a lot!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Then if the current character is 1 then the possible new numbers are 0, 10, 100 and two of these three numbers were already present in my set, so I have to remove them.

    I think the current character should be 0.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can u pls refer what technique/method/algo is this? I didn't got this wholly, so want to read on this.

    Firstly I thought doing this will stuck in infinite loop, but now this seems magical !!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

another approach would be to remove prefix consecutive zeros , come at first index lets call it idx such $$$ s[idx]$$$ == '1' , now apply total number of distinct sequence algorithm which is classic DP question for the string $$$ s[idx+1:] $$$, that will be your answer, also you have to add one if there is zero in the string.

reasoning behind this is basically, after you get '1', whatever you append multiplies prefix by 2 and current number in it, and it suffice for the distinct decimal condition. in other words every distinct subsequence has unique decimal representation.

»
3 года назад, # |
Rev. 7   Проголосовать: нравится -9 Проголосовать: не нравится

Deleted

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Does Anyone Knows similar problem like this on codeforces ?? it will be highly appreciated !!