# ACM ICPC 2014 solution to problem A – baggage

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 BABABABA, i.e., the first AB, like with n = 3, BABABABA, and BABABABA 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)!

## 21 responses to “ACM ICPC 2014 solution to problem A – baggage”

1. james says:

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

2. Dhaval Kapil says:

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).

3. 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…

Maria

• sushant says:

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

• sunil says:

i have to c in program my mail id

4. Ankur Mali says:

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.

thanks bruhhhhhhhhh:)

5. Pingback: Dancing Algorithms | Keet blog

6. kundan baheti says:

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

• tuza chhava says:

ani tula milala ki mala pn pathivvvv…bhavaa pleaseeeeeeeee …muaahhhh

7. Sunil says:

any some one if can your c in coding to provide.

8. Sneha says:

Please give me code for baggage problem in cpp language.

• I don’t have the code, sorry. I like solving problems more than implementing them.

This site uses Akismet to reduce spam. Learn how your comment data is processed.