Some of you already know I was on-site coach for the UCT team at the ACM Inter Collegiate Programming Contest World Finals in Ekaterinburg, held from 22 to 26 June, 2014. The problems were unusually hard this year, and solving 4 out of the 10 problems already got teams into the bronze medal range [results]. The technical coach of the UCT team, Bruce Merry, has written an analysis of 6 problems on his blog (D, K, C, E, B, and F–update: now also I and G, J, L, and H), and over at TopCoder, SnapDragon discusses 4 of the 10 problems (A, E, F, G), except that SnapDragon does not provide a solution to A (and I don’t like his hint of brute-force code-and-try) [update 3-7: there’s description of his solution here now]. Googling, I couldn’t find someone else discussing the solution to problem A, so here’s mine, which I solved on the plane from Moscow to Frankfurt (among other activities, and one among the four flights we had to take to arrive back in Cape Town).

**The problem**

Stripping the “baggage problem” to its essentials: you have a sequence of alternating Bs and As, which has to be reordered to first all the As then all the Bs, and the reordering has to occur moving two letters at the same time, and remain adjacent. For instance, with an n = 4, we have 2n characters, BABABABA, and in the end after sorting, it then will be AAAABBBB, and this has to occur in the minimum amount of moves. N is randomly chosen, and is an integer between 3 and 100. The cells on your tape are numbered from 0 to -2n+1, so with our n = 4, from -7 to 8, and the first B is on position 1.

Update (3-7): This problem appears to be “Tait’s counter puzzle”, which Peter Guthrie Tait, a Scottish mathematical physicist, described in 1884 [see description] (thanks to Davi Duarte who mentioned it in the topcoder thread).

**Solution**

Informally, there are two parts to the algorithm: move around the As and Bs to pair them as AA and BB, which cost you n/2 moves if n is even and n/2-rounded up moves if n is odd, and then sort those pairs in the remainder to a total of n moves. The first part occurs alternating moving AB from the right to the left, starting at the last AB (position 2n-2) and then every other 4 to its left, and BA from left to right, starting from position 3 and every other 4 positions to the right (i.e., 7, 11, etc.), and then the BBs are ferried to the right from left to right, and the AAs from the right to the left, also alternating. N=3 is an exception.

One can do this with a neat mathematical proof, but I found out with pattern creation and recognition, visualizing the provided sample input and moves for n = 5 and n = 8, which can be done in 5 resp. 8 steps (given in the problem statement as sample output). Here’s a description of that approach.

First, devising one for 3 is trivial, using the following moves (the only option), using the position indicated with the position of the first letter, and highlighting the ones that will be moved next:

Start: . . . . . . BABABA

Move 2 to -1, which gives . . . . ABB . . ABA

Move 5 to 2, which gives . . . . ABBBAA. .

Move 3 to -3, which gives . . AAABBB . . . .

This already suggests that the minimum amount of moves will always be n, because it is n moves also for n = 5 and n = 8. Next, devising one for n = 4, and knowing the moves for n = 3 and n = 5, I tried to work it out for B**AB**ABABA, i.e., the first AB, like with n = 3, BAB**AB**ABA, and BABAB**AB**A like with the n = 5 case. The last one is the only one that worked in 4 moves, starting with moving 6 to -1, again. Again, because for all ns so far, the first move is to -1.

Let’s put this to the test with n = 7, with the ones to be moved in bold and the empty cells indicated with dots:

..BABABABABABABA

i.e., move the last AB (thus, position 12) as this worked for n=4 and n=5, then

ABBABABABABAB..A

i.e., move the first BA after position 1 (thus, position 3)

ABBA..BABABABBAA

i.e., move the last AB before a pair (thus, position 8)

ABBAABBAB..ABBAA

i.e., move the first BA after position 1 (thus, position 5). Then sorting the BBs and AAs:

ABBAAB..BBAABBAA

A..AABBBBBAABBAA

AAAAABBBBB..BBAA

AAAAABBBBBBB..AA

AAAAAAABBBBBBB..

This was enough for me to have discovered the pattern of alternating for the matching and alternating for the sorting.

What is ‘nasty’ in the problem description, retrospectively and for the pattern-based approach vs. a neat maths-y proof at least, is that the pattern deviates for n = 3, and the provided sample output for n = 8, although in 8 steps, is an alternative solution, not one that one obtains with the algorithm. With the approach as mentioned above, we have for n = 8 the following (I did that one to double-check):

..BABABABABABABABA

ABBABABABABABAB..A

ABBA..BABABABABBAA

ABBAABBABAB..ABBAA

ABBAABBA..BBAABBAA

A..AABBABBBBAABBAA

AAAAABBABBBB..BBAA

AAAAA..ABBBBBBBBAA

AAAAAAAABBBBBBBB..

This confirmed it works. It may look a bit craft-y, but the patterns show beautifully with larger n, which are shown below for the even and odd case (made just for the blog post, not in solving it); squint your eyes if it’s not immediately clear.

N = 16

..BABABABABABABABABABABABABABABABA

ABBABABABABABABABABABABABABABAB..A

ABBA..BABABABABABABABABABABABABBAA

ABBAABBABABABABABABABABABAB..ABBAA

ABBAABBA..BABABABABABABABABBAABBAA

ABBAABBAABBABABABABABAB..ABBAABBAA

ABBAABBAABBA..BABABABABBAABBAABBAA

ABBAABBAABBAABBABAB..ABBAABBAABBAA

ABBAABBAABBAABBA..BBAABBAABBAABBAA

A..AABBAABBAABBABBBBAABBAABBAABBAA

AAAAABBAABBAABBABBBB..BBAABBAABBAA

AAAAA..AABBAABBABBBBBBBBAABBAABBAA

AAAAAAAAABBAABBABBBBBBBB..BBAABBAA

AAAAAAAAA..AABBABBBBBBBBBBBBAABBAA

AAAAAAAAAAAAABBABBBBBBBBBBBB..BBAA

AAAAAAAAAAAAA..ABBBBBBBBBBBBBBBBAA

AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB..

N = 17

..BABABABABABABABABABABABABABABABABA

ABBABABABABABABABABABABABABABABAB..A

ABBA..BABABABABABABABABABABABABABBAA

ABBAABBABABABABABABABABABABAB..ABBAA

ABBAABBA..BABABABABABABABABABBAABBAA

ABBAABBAABBABABABABABABAB..ABBAABBAA

ABBAABBAABBA..BABABABABABBAABBAABBAA

ABBAABBAABBAABBABABAB..ABBAABBAABBAA

ABBAABBAABBAABBA..BABBAABBAABBAABBAA

ABBAABBAABBAABBAABB..BAABBAABBAABBAA

A..AABBAABBAABBAABBBBBAABBAABBAABBAA

AAAAABBAABBAABBAABBBBB..BBAABBAABBAA

AAAAA..AABBAABBAABBBBBBBBBAABBAABBAA

AAAAAAAAABBAABBAABBBBBBBBB..BBAABBAA

AAAAAAAAA..AABBAABBBBBBBBBBBBBAABBAA

AAAAAAAAAAAAABBAABBBBBBBBBBBBB..BBAA

AAAAAAAAAAAAA..AABBBBBBBBBBBBBBBBBAA

AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBB..

Neat. Writing the code is left as an exercise to the reader.

I’m looking forward to the other problems (except the crane balancing problem C, whose description I did not like, at all), the upcoming regionals and next year’s ICPC World Finals in Morocco (if not winning, then to have at least a great time like we had this time)!

It looks like your n=7 case takes 8 steps?

it does look like it… I’ll dig up my scribbles in the notebook to see if it’s a transcription mistake

What about for n = 6 or n = 9? Isn’t it violating your algorithm?

Hi Dhaval,

here’s the one I had for n = 9, which follows the pattern and has 9 steps:

. . BABABABABABABABABA

ABBABABABABABABAB . . A

ABBA . . BABABABABABBAA

ABBAABBABABAB . . ABBAA

ABBAABBA . . BABBAABBAA

ABBAABBAABB . . BAABBAA

A . . AABBAABBBBBAABBAA

AAAAABBAABBBBB . . BBAA

AAAAA . . AABBBBBBBBBAA

AAAAAAAAABBBBBBBBB . .

I’ll check the one for 6 (I skipped solving that one, for the pattern was already clear to me before then).

Yes but in the 6th line you didn’t follow your algorithm I guess. Won’t that create a problem while coding? I also got a problem with n = 6

It does for 9: there’s a minor difference between the even and the odd cases when it arrives ‘in the middle’. The one for 9 has the same pattern as for the n=17 (cf. n=16).

I’m conferencing at the moment so it will take a few days before I can respond regarding 6 and 7 (note: the ones for 4 and 5 do follow the pattern).

The solution given fails for n=10 too.

Hi Mnjovice,

Thanks for looking into it. The solution for n=10 I had in my notes and working in 10 steps actually indeed doesn’t follow the pattern at the ‘centre’/middle, but works for the other parts ‘ferrying around’ the AB/BA/BB/AA ones:

..BABABABABABABABABABA

ABBABABABABABABABAB..A

ABBA..BABABABABABABBAA

ABBAABBABABABAB..ABBAA

ABBAABBA..BABABBAABBAA

ABBAABBAABB..ABBAABBAA

ABBAABBAABBAB..BAABBAA

A..AABBAABBABBBBAABBAA

AAAAABBAABBABBBB..BBAA

AAAAA..AABBABBBBBBBBAA

AAAAAAAAAABBBBBBBBBB..

Also, to respond to a previous comment: I can’t get n=6 to work with the pattern (as lame excuse: also the solution with recursion requires a few cases hard-coded).

I had done the ones for n=12 and n=13 when writing this blogpost (not included because n=16 and n=17 look nicer), which both do follow the pattern, so here they are:

..BABABABABABABABABABABABA

ABBABABABABABABABABABAB..A

ABBA..BABABABABABABABABBAA

ABBAABBABABABABABAB..ABBAA

ABBAABBA..BABABABABBAABBAA

ABBAABBAABBABAB..ABBAABBAA

ABBAABBAABBA..BBAABBAABBAA

A..AABBAABBABBBBAABBAABBAA

AAAAABBAABBABBBB..BBAABBAA

AAAAA..AABBABBBBBBBBAABBAA

AAAAAAAAABBABBBBBBBB..BBAA

AAAAAAAAA..ABBBBBBBBBBBBAA

AAAAAAAAAAAABBBBBBBBBBBB..

..BABABABABABABABABABABABABA

ABBABABABABABABABABABABAB..A

ABBA..BABABABABABABABABABBAA

ABBAABBABABABABABABAB..ABBAA

ABBAABBA..BABABABABABBAABBAA

ABBAABBAABBABABAB..ABBAABBAA

ABBAABBAABBA..BABBAABBAABBAA

ABBAABBAABBAABB..BAABBAABBAA

A..AABBAABBAABBBBBAABBAABBAA

AAAAABBAABBAABBBBB..BBAABBAA

AAAAA..AABBAABBBBBBBBBAABBAA

AAAAAAAAABBAABBBBBBBBB..BBAA

AAAAAAAAA..AABBBBBBBBBBBBBAA

AAAAAAAAAAAAABBBBBBBBBBBBB..

maybe someone can/should implement it…

Best regads,

Maria

please give code for this in C++ .

regards,

sushant

Hi Sushant.

I don’t have the C++ code (nor the C nor the Java code); I find more fun in essentially solving a problem than coding it.

Maria

in above problem there is no fixed pattern to follow because single pattern falls apart for different value of n

The solution for n=6 is :-

10 -1

7 10

2 7

6 2

0 6

11 0

and for n=7

12 -1

5 12

8 5

3 8

9 3

0 9

13 0

the recurrence and method to decrease by 4 given cases , fails in some of the cases,there are 4-5 pattern involved which solves the problem,but dynamically analyzing pattern is the challenge while coding.

Pingback: Dancing Algorithms | Keet blog

Pingback: UVALive 6770 – Baggage （构造） » kuangbin博客

any one hav code for this problem in c language???? plz send