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

Advertisements

18 responses to “ACM ICPC 2014 solution to problem A – baggage

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

    • 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

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

  2. Pingback: Dancing Algorithms | Keet blog

  3. Pingback: UVALive 6770 – Baggage (构造) » kuangbin博客

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s