janardan_sharma's blog

Cisco Hackathon Question for internship
By janardan_sharma, history, 2 years ago, In English

could anyone please help me out with an approach for this question which came in an hackathon by cisco for SWE interns.

String Wars

In this question you are given an integer n and you have to construct a string of length n using only two uppercase letters A and B and there is a condition that you cannot use two B's adjacent to each other in the constructed string and the string should be mth lexicographically smallest string. if the mth string is not possible then print -1.

Given : 1 <= n <= 90 1 <= m <= 10^19

Testcase 1: n = 2 m = 3 answer : "BA"

Testcase 2: n = 2 m = 4 answer : "-1" , as only 3 distinct strings can be constructed --> "AA", "AB", "BA".

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

Comments Comments (5)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Should this work? Base 2 encoding: A is bit 1 B is bit 0

So
AA is 11
AB is 10
BA is 01
counting backwards
AAA is 111
AAB is 110
ABA is 101
....

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

deleted

→ Reply
»
2 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it
My attempt

An important thing to understand is how should we construct the answer when going from n to n - 1 (see the code). I thank charan2628 for the insights!

UPD: thanks forcdc, I have edited the comment.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think there is a bug, your dp[1][0] is 2, you should initialize dp[1] and then start the loop from i=2, rest looks fine.

    → Reply