supersonic11's blog

By supersonic11, 6 weeks ago, In English

Given an binary string 100000... of size '$$$m$$$' on day 0 , For each subsequent day, the updated value at each index >= 1 is given by xor of the value of (i-1)th index and ith index on the previous day . Print the binary string on nth day . where $$$1<=n,m<=1e5$$$ .

I am able to see some pattern after writing down the string for several days but not able to make it concise .

Edit : Following is the link

Read the first question of coding round.

question is slightly different from the link given (since that question can be solved by brute force)

I asked this question and my contribution went from 0 to -15 . I agree that i am not helping someone but i thought people might find this problem interesting and i can get help . Also i tried for few hours before posting . Even small help from your side will motivate me to grow and work harder .

So many nice ideas provided . I want every one in comment section THANK YOU for helping !

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

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

Can you post the link to question?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    You can ask me if something not clear in question description.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Can you post the link? Generally, without posting a link to the source, people will suspect this is from an in-progress contest or interview.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi , i have provided the link . The question is slightly different from the link given (since that question can be solved by brute force)

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it
      1. What is the length of the bitstring?

      try doing brute force to exploit the pattern here's what i think :

      find i such that bit(i)==1 let ans[n] be the answer array or bitstring. Then a[0],a[1],...a[i] will all remail same for any n.

      bit(i+k) will remain zero for k days and change depending on the bit(i+k-1). For example bit(i) is set. then bit(i+1) flip everyday. bit(i+2) will flip after 2 days. Except (i+1) and (i+2) bit(i+3) will stay zero for 3 days and turn 1 and then back to 3 days zero and so on You just have to worry about when will the flipping start based on previous bits flipping.

      P.S : I am still a noob in programming this is my thought process and i may very likely be wrong so i suggest you verify and then consider.

      Thank you

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i have provide both link and more details . If i understood your solution correctly then are you are telling some diagonal pattern ? Can you please explain with help of an example.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I had messed that observation sorry about that.

          Answer for n=16 is (printed as b31,b30,...,b0)

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

          0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

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

Where is the 1st index?

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • P.S. I'm sorry. The statements I posted are completely wrong.
»
6 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

The binary string (0 based indexing) would be constructed as the following :

  • If the index is a submask of n, the character would be of value '1'

  • If not, it would be '0'

A number $$$X$$$ is a submask of another number $$$Y$$$ iff $$$X \ AND \ Y = X$$$

I am not sure exactly how to explain how I got this, however, since I randomly tested weird ideas.

Specifically, I tested writing out the strings, then saw it has a "recursive" pattern with a similar shape to Sierpinski's Triangle, and has a "binary"-ish pattern to it.

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it
Spoiler

It's clear by inspection of the first few iterations of this process that they form a finite Sierpiński triangle-like structure. If you're familiar with this then Lucas's theorem may come to mind. If not, you might notice that on some days the string contains only two ones, and that this happens on days 1, 2, 4, 8, 16, ..., $$$2^k$$$. It's then easy enough to prove by induction that the string on day $$$d + 2^k$$$ is equal to the xor of the string on day $$$d$$$ with its $$$2^k$$$-th shift. With that observation in hand, it is easy enough to write an $$$O(m \log n)$$$ solution using the binary representation of $$$n$$$ and bitsets, and not very much harder to optimize this to $$$O(m)$$$.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

[deleted, my approach was incorrect]

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    if on day 12 string is 111100001111 then on day 13 string should be 100010001000 but according to this, it will be 10101010101

    I think we have to do a simultaneous update on the string

    Am I missing something?

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

      Yes you are correct, i made a mistake in constructing the sequence.

      Will edit my comment. Thanks for pointing that out!