### janardan_sharma's blog

By janardan_sharma, history, 4 months ago,

# 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".

• -2

 » 4 months ago, # | ← Rev. 2 →   0 Should this work? Base 2 encoding: A is bit 1 B is bit 0So AA is 11 AB is 10 BA is 01 counting backwards AAA is 111 AAB is 110 ABA is 101 ....
•  » » 4 months ago, # ^ |   0 How do you take care of the consecutive B's condition?
•  » » 4 months ago, # ^ |   0 can you define some algo for string construction as the value of m is quite large so we cannot iterate over it.
 » 4 months ago, # | ← Rev. 2 →   0 deleted
 » 4 months ago, # | ← Rev. 3 →   0 Thinking this, didn't tried the implementation yet: T(n) = T(n — 1) (strings starting with A) + T(n — 2) (strings starting with BA) Now fix A see if T(n — 1) is below m then fix A and go for next characters else fix BA and go for T(n — 2) in same way
•  » » 4 months ago, # ^ |   0 private static String solve(int n, int m) { char[] ans = new char[n + 1]; int[] dp = new int[n + 1]; dp[1] = 2; dp[2] = 3; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } if (dp[n] < m) return "-1"; long cnt = 0; int currentCharacter = n; while (currentCharacter >= 2) { if (cnt + dp[currentCharacter - 1] >= m) { ans[currentCharacter--] = 'A'; } else { cnt += currentCharacter - 2 < 0 ? 0 : dp[currentCharacter - 1]; ans[currentCharacter--] = 'B'; ans[currentCharacter--] = 'A'; } } if (currentCharacter == 1) { if (cnt + 1 == m) { ans[currentCharacter] = 'A'; } else if (cnt + 2 == m) { ans[currentCharacter] = 'B'; } } StringBuilder builder = new StringBuilder(new String(ans)); return builder.reverse().toString(); }
 » 4 months ago, # | ← Rev. 7 →   0 My attempt#include "bits/stdc++.h" using namespace std; int main() { uint64_t n, m; cin >> n >> m; // dp[i][0] — how many good strings s such that (len(s) = i + 1 and s[0] = 'A') exist // dp[i][1] — how many good strings s such that (len(s) = i + 1 and s[0] = 'B') exist vector> dp(n); dp[0] = {1, 1}; for (uint64_t i = 1; i < n; ++i) { const auto prv = dp[i - 1]; dp[i][0] = prv[0] + prv[1]; dp[i][1] = prv[0]; } if (m > dp.back()[0] + dp.back()[1]) { cout << -1 << "\n"; return EXIT_SUCCESS; } string ans{}; for (int cur = dp.size() - 1; cur >= 0; --cur) { if (m <= dp[cur][0]) { ans += "A"; } else { m -= dp[cur][0]; ans += "B"; } } cout << ans << "\n"; } 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.
•  » » 4 months ago, # ^ |   +1 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.