Thought process for AB problem on Topcoder.

ab.txt

Topcoder AB problem
Inputs: N,K
Problem: Generate a string of length N that consits of only letters A and B and contains K pairs (i,j) such that s[i]='A' and s[j]='B'

I'm going to assume K is at most N/2

Trying to simplify the problem. What if we have a string of length two (N=2) and we want to make a string with 1 ab-pair (K=1). The result will be either "ab" or "ba".

N=10
K=12


The 'a' always has to come before the 'b'. My mistake!!!

The problem I'm having is figuring out how to generate the string. Also, how do we know if a string cannot be generated?

N=4
K=2

Theoretical solution:

Start with a string of 'a's of length N. Then replace the characters with 'b's at the positions which generate pairs until K pairs are made.

N=10
K=12

Step 1:
AAAAAAAAAA
Step 2:
Place a B at the end
AAAAAAAAAB

the # of pairs is now 9

A A A A A A A A B B

now the # of pairs is 16
Reduce this to 10 by changing two As to Bs at the front of the string, thereby removing two pairs.

B B A A A A A A B B

# of pairs is now 12

--------------------------------
N=5
K=3

Step 1:
A A A A A
Step 2:
A A A A B (pairs=4)
    |
    v
B A A A B (pairs=3)


N=5
K=8

Step 1:
A A A A A
Step 2:
A A A A B (pairs=4)
A A A B B (pairs=6)
A A B B B (pairs=6)
A B B B B (pairs=4)
B B B B B (pairs=0)

Return empty string

I'm seeing a pattern here. The number of pairs is the number of As * the number of Bs. We know if it's an invalid pair if the number of Bs is equal to the length of the string.

This algorithm can run in O(n) time and O(1) space:



string createString(int n, int k) {
  string result(n, 'A'); // "AAAA....A"
  int i = 0, j = n - 1; // indexes to modify the string
  int numPairs = 0; // number of pairs
  int countA = n; // count of As in the string
  int countB = 0; // count of Bs in the string
  do {
    if (numPairs > k) {
      result[i++] = 'B';
    }
    else if (numPairs < k) {
      result[j--] = 'B';
      countB++;
    }
    else {
      return result;
    }
    countA--;
    numPairs = countA * countB;
  } while (numPairs != 0); // numPairs will eventually go to 0 as more Bs are added
  return "";
}

Bug fixes/optimizations:
1) Instead of having countA-- and countB++ in both paths just put those statements after the if statements.
2) Also, set countA=n instead of countA=0 in the beginning.
3) doing countA*countB is incorrect. It will multiply the count of A by the count of Bs on the left and right side (meaning before and after an A). To fix this, multiply countA by j (or only increment countB when j--).

n=3
k=2

Step 1:
A A A (pairs=0)
Step 2:
A A B (pairs=countA*countB=2*1=2)

correct!

n=14
k=7

Step 1:
A A A A A A A A A A A A A A (pairs=0)
Step 2:
A A A A A A A A A A A A A B (pairs=13*1=13)
B A A A A A A A A A A A A B (pairs=12*1=12)
B B A A A A A A A A A A A B (pairs=11*...)
B B B A A A A A A A A A A B (pairs=10*...)
B B B B A A A A A A A A A B (pairs=9*...)
B B B B B A A A A A A A A B (pairs=8*...)
B B B B B B A A A A A A A B (pairs=7)

n=2
k=15

A A (pairs=0)
A B (pairs=1)
B B (pairs=0)


n=10
k=12

A A A A A A A A A A (pairs=0)
A A A A A A A A A B (pairs=9)
A A A A A A A A B B (pairs=16)
B A A A A A A A B B (pairs=7*3=21) XXX!! (Fixed with 3rd bug fix) (pairs=7*2=14)
B B A A A A A A B B (pairs=6*2=12) correct

n=13
k=29

A A A A A A A A A A A A A (pairs=0)
A A A A A A A A A A A A B (pairs=12*1=12)
A A A A A A A A A A A B B (pairs=11*2=22)
A A A A A A A A A A B B B (pairs=10*3=30)
B A A A A A A A A A B B B (pairs=9*3=27) <---

(test)
n=8
k=7
A A A A A A A
A A A A A B A (p=5)
A A A B A B A (p=3*1+3*1+1=3+3+1=7)

n=4
k=3
A A A A
A A A A

B A A A A A A A A B B B B (pairs=8*4=32)
B B A A A A A A A B B B B (pairs=7*4=28)
B B A A A A A A B B B B B (pairs=6*5=30)
B B B A A A A A B B B B B (pairs=5*5=25)
B B B A A A A B B B B B B (pairs=4*6=24)
B B B A A A B B B B B B B (pairs=3*7=21)
... 
Should return something valid instead returns "" because it goes to 0

Basically since 29 is a prime number there will be no countA*countB that equals K, even if it is possible to make the string.

Old code:
#include<string>
using namespace std;

struct AB {
    string createString(int n, int k) {
        if (n == 0) return "";
        if (k == 0) return string(n, 'A');
        if (k * 2 > n) return "";
        string res;
        while (n > 2) {
            res += "AB";
            n -= 2;
        }
        if (n) {
            res += "B";
        }
        return res;
    }
};

I think that 'B' should be add ahead of 'AB'.
it failed on test case #4.