Traffic jam

will the boxes be numbered from 1 to n??

I am sorry if this is already there in the FAQ section, but could someone let me the memory limit.

What does this mean? “Then, n integer values describing the sizes of boxes in the sequence.” (emphasis added)

@Ankit There appears to be nothing in problem statement indicating anything about the numbers on the boxes.

@Kailash There is no fixed upper memory limit, but 64K is the lower limit for available memory.

what is the range of the numbers on the boxes? is it always from 1 to n (n being the number of boxes)?

please give the range of the numbers on the boxes

what is the time limit for the solution to run?

the problem page says 5 secs, but some of the successful solutions have executed in about 13 secs.

may i know the time limit for this problem cause I got TLEd a few times on about a nlogn solution, which must fit in.

@kapil:

The given time limit is for one test FILE (which for this problem could have up to 10 individual cases).  If there are multiple files, the time shown for accepted solutions is the sum of the time taken for each file (where each individual file fit in the time limit).

sorry, no range will be given for you

hi, cud someone kindly explain the example?

I'm unable to figure out how to solve it in 2 moves.. Thanks.

The example is definitely correct: you can sort the boxes in ascending order in 2 moves. I also took a while to figure it out.

As this is a contest, we probably should not say more than this.

oh ok. i got it. was thinking that the subset should be continuous sequence of boxes.. stupid me..

My program is running for 8.44 sec andgiving WA. It means for atleast one test file my program giving correct output?

Sorry if it comes in the category of hints then don't reply on it.

I'm sure I'll feel silly when I figure out whatever stupid mistake I'm making, but in the meantime it would be nice to be 100% sure I'm not misunderstanding the problem itself.  If the row of blocks is "abcdef" and Johhny selects "ace", then will the new order be "bdface"?

Yes.

@David Yes.

I'm also at the stage of re-reading the problem, to make sure I got it right. What is the result for sequence "2 3 1 2"? Should the order of boxes with number 2 be preserved or are we allowed to sort this sequence in a single move by selecting first two numbers?

@Tomaz

everything you need is in problem statement

What is the RANGE of each number?

And will them be DISTINCT ?

@Chen

everything you need is in problem statement

@mahbub

what do you mean correct? is anything broken with this problem?

@Przemyslaw: I think what Balajiganapathi and Chen are referring to is that "n integer values" may or may not imply that the values will fit in a standard integer type, and it's not something that the programmer should be left to guess.

@Stolp, Well that's not my problem. (yes that should be explicitly stated in the problem statement, but i am not referring to this)

Problems with the problem statement:

1. The word "ascending" is ambiguous: it could mean "strictly increasing" or "non-decreasing".

2. The goal is to sort the boxes "in ascending order of numbers" on their side, but those numbers are not given :) Instead, "the sizes of boxes" are given.

uh,oh, Tomek,you are right..

ad1 - non-decreasing

ad2 - sizes==numbers

What I find strange is that mahbub, who solved the problem, claims there's something wrong with it. Or did his fears turn out to be false?

mahbub is correct, i failed. problem will be corrected and rejudged soon.

@Przemyslaw: I was beginning to lose my mind over this problem.  I wrote multiple brute force checkers and ran millions of random tests, but couldn't find any discrepencies.  I bet my second submission passes rejudge.

So, the problem had been fixed now?

What had been fixed? Problem statement or the data?

@judge

Why i am getting runtime error ?

I have only used a single array and my code file is only 3 kb.

Many correct solutions hav used up 40 mb of memory.

So why my solution is not accepted?

@ Przemysław Uznański has the judge data been fied??

@ Przemysław Uznański.. has the judge data has been fixed ?

@Mahesh

I'm not an admin here.

I sent them new testcases, waiting for rejudge.

If they're going to rejudge it it had better be soon, or 50 people who haven't checked this thread are suddenly going to have no time to resolve the problem.

@Admin: When will this problem be rejudged??

how to check whether i'm still having AC or not after this rejudge...

@Przemysław Uznański

how can i know result of rejudge....

@David Stolp:

it seems that only your first submission passes after the rejudge. Since you said yourself, that you expect only your second submission to pass, do you think there might still be a mistake in the judge data?

@soc: for the time being, you can check the status of this problem on your profile page!!

@Adrian Kuegel:

I'd say there's still something wrong with the judge data. I've submitted two different solutions of which one is definitely wrong, and this one gets AC now. The other which I'm pretty sure is correct gets WA.

@Mark Greve: good to know. I also have a solution which I am pretty sure is correct, and I still have WA.

@Przemysław Uznański: can you please check your own solution against a brute force program?

@admins: can you please consider to increase the contest deadline, so that everyone still has enough time to solve the problem after the rejudge?

My AC solution is definitely wrong.  Either that or the problem statement is wrong, since it would take a very small ammendment to the statement to make my AC solution correct.

has the contest rankings been also updated yet according to this problem??

Now I see, my "AC" is also wrong, and it also takes very small change.

I'm going to rethink problem.

Noone is perfect, and I'm far from being even close. (especially with noone to verify my ideas)

Are you saying nobody else tested your problem at all? No wonder all these bugs keep getting through :(

I agree, the contest deadline definitely needs to be increased.

On TopCoder they are paying problemsetter, then they are paying several testers.

Here, I'm asked to deliver problem and paid for problem.. and thats all. I am trying very hard, but it's impossible to verify own problem.

I think it might be still something wrong now...

I hope there will be some tester in next competition like TopCoder.

So whats the conclusion?

We need to submit again , rt?

It now shows WA on My Submissions page, however, there seems to be no change in the overall rank listing , as well as in the "successful submissions for this problem"......

Also , itd be better if other participants are also informed about this (by mail maybe) , because many who got AC earlier may not have a look at this page again.....

The conclusion is I probably figured how to solve it, but maybe someone better will figure it that its still wrong.

I'm going now to upload new tests and rejudge whole problem.

It seems the judge data is now correct, at least the submission 2 of David Stolpe passes which he said he tested against brute force, and the last submission of Mark Greve passes as well. And I got Accepted too :-)

Let's all thank to Ania Piekarska for helping me a lot :)

is the time limit to the problem increased because i see accepted solution more than 5 sec

Please read the FAQ before posting comments. It is there for a reason.

@Przemysław Uznański

Since we have very little time left (unless the deadline is extended) i feel that atleast now you should give the range of the integer values(i.e size of the boxes). I am getting WA and dont know wether it is being caused due to the range of the integers or my algorithm. I am sure many others will also feel the same.

Has the range of integers been changed too when the judge test data was changed?

Can you please notify people who had AC and now don't?  I would never have known that I still need to solve this problem if I hadn't read David's posting in the forum. :(

You can figure out the range of input by yourself, using asserts.

AndI didn't answered that question simply because it's not the part of problem hardness.

@Josh

I cannot notify anyone, I'm not admin here.

@Przemysław Uznański I feel if something is not part of problem hardness, there is even stronger reason to give an answer to that question.

Thanks to all!

I got AC now~

I agree. People should not have to guess at ranges of input. If the values fit inside an integer, the problem should say so, unless you are expecting everyone to use arbitrary precision arithmetic.

i feel my solution is correct.. bt it's still showing WA... :-( ... can anyone help me.. find out.. where i am going wrong.. coz.. i can't find any now!!! :-( .. or.. jst give me... more test.. cases mail me @ nitinkumar810@gmail.com

Thanx..

Another possibility is to discount this problem completely, and determine the winners of the contest based on the other 5 problems only.

But this one is one of the most tough problem.

This month's NX problem is not so good , lots of people got 1.000000 score~

IMPORTANT:

The successful submissions shown for this problem are not correct. We are currently making the required changes. This will be fixed soon.

When will this be fixed?  Everyone who solved the problem under the old judge is still listed in the successful submissions on this page.  At least the point for solving it has been taken away so ranks are correct on the main MARCH10 page.

Also, you really need to e-mail the people whose submissions were AC and are now rejected, at least Qinz who hasn't made a submission since before this was rejudged and probably thinks he has already finished this competition tied for 1st.

I'm really sorry to say this. But the CodeChef birthday is turning out to be pretty bad.

It seems that the Chef baked a really bad cake, and someone used the candles to put things on fire.

@Keshav Dhandhania

You are absolutely right. The least CodeChef can do is to change their problem submission system so that a problem is thoroughly tested before using it in a contest. This can save a lot of time for the contestants. I hope CodeChef seriously considers this.

I may be understanding the question in a wrong way, the simpler way.. but i cannot think of anything "very difficult" in the problem. I mean, trying to figure out an efficient solution to a difficult problem is one thing. Trying to understand why is the problem difficult is another. Its really bad that we don't know whether we are misinterpreting the problem or not. It would be worse if we actually are.

@Admin

The rankings  are still not correct.

Many contestants.. (including few in top 10 ) haven't even attempted  4 problems  but still given the score of 4.

I hope it gets fixed soon.

IMPORTANT:

The submission information for this problem is now correct. Kindly post here if you find any discrepancies.

@ admin..But i find discrepancy in the ranking list on main contest page. When I am clicking on someone,s profile who,s score is 4 then it is showing only 3 problems solved in his profile.

IMPORTANT:

This has been fixed now.

umm, when I tried to submit my solution it said

The smiley is a nice touch,  but does that mean my code is disastrously wrong, or it's actually a problem?

Ah, never mind. It stopped happening.

If my code is running for 5.87 sec and giving wrong answer then does that mean that till 5.87 sec whatever it printed was correct?? please reply.

FAQ

Thank you stephen..1 more question..not related to this contest though.

In the practice problem "just a simple sum" in medium section I have implemented the code according to your tutorial. But I am still getting TLE. I have posted the code there in the comment list there. Can you please see my code ?

Thank you in advance.

@Stephen:

xD

now that the contest is over, could someone please explain which ws the family of input cases that caused all this difference?

I did notice one set of cases which got passed earlier but were wrong. However, it seems there were many other similar cases.

Thank you.

Well, for example my original AC submission for sizes 4 3 2 1 gave an output of 3, when the answer is clearly 2, as an example, though I expect virtually all other test cases would give wrong answers too. The second rejudge appears to be due to duplicate sizes not being handled properly at first.

Sorry if this is too trival but how does 4 3 2 1 gives an output of 2.

4 3 2 1

Choose 4 and 2

3 1 4 2

Choose 3 and 4

1 2 3 4

So what approach did you use to solve the problem. I was always going in the wrong direction. I was constructing a BST according to the list. If the number a left child i was incrementing by 1. And since worst case it will time out i was using a AVL tree and handling the duplicate entries as well as keep tracking if it is the left child or not. But looks like the apporach was completely wrong.

First solve for a simple case when the numbers are distinct. For each number from smallest to the largest, check if the link from the current number to the next number goes from left to right. If not, it counts towards an error. The answer is simply a function of the total number of errors.
For example in case of {4,3,2,1}, there are 3 errors. f(3)=2

In case of {5,4,3,1,2}, there are 3 errors. So the answer is f(3)=2. and the strategy is

{5,4,3,1,2}->{1,2,4,5,3}-?{1,2,3,4,5}.

The problem is to figure out what f is. In case on non-unique numbers, we need to find an ordering such that the total number of errors is minimized.

But is it simple enough to find f(n) in nlogn time?

f(n) can be found in O(1), if you use a formula. If can be found in O(log(log(n))) if you dont use a formula. But I was lazy and implemented a O(log(n)) solution for f(n) (which happens to be 3 lines of code).

Just another small clarification. For the following test case is the number of errors 3? And output 2?

5 8 1 4 6 3 7 2

If 2 could you explain how?

. . 1 . . . . 2
. . . . . 3 . .
. . . 4 . . . .
5 . . . 6 . 7 .
. 8 . . . . . .

Four 'errors', output 3.

Thank you very much. I think my solution was otuputting the number of errors correctly. Need to figure out a way to find f(n).

It's a pity this problem was formulated the way it was. The natural formulation is that the sequence contains every number from 1 to m, and nothing else, (i.e. there are no gaps). There is then a linear time solution. You can eliminate multiple occurences in linear time, without changing the answer. Adding the simple exercise of eliminating gaps first just allows O(nlogn) solutions to an interesting O(n) problem.

But how would you eliminate the gaps? I am assume when you are talking of a linear solution you are going to maintain a array of size m and if you encounter a number say x you will check if x-1 is set or not and based on that calculate the number of errors. So can you eliminate the gaps when you dont know the range of numbers. (or the range is too big).

You sort the numbers, then you renumber the smallest number to 1, the next one to 2, and so on. (Not that you have to actually do this renumbering, but that's the idea.) I'm not sure what you mean by not knowing the range or the range being too big. You are given that there are at most 100000 numbers.

But if you are sorting the numbers you complexity will still remain at nlogn right? So the best solution for the above problem will be in nlogn right. And i am still under the impression that if you need a O(n) solution you will need to maintain a temporary storage. And if you need to maintain that you will need to know the range. For example if you know the numbers are from 1 to n you can maintain a boolean array from 1 to n. But the max n value in this case will be maximum of int which is too big to store.

Yes, the problem as it stands is O(nlogn). If we were given that there are no gaps, there is a O(n) solution, with O(n) storage. Given that n is at most 100000, there is no problem. (n<=10000000 would still be fine). Whether there is an algorithm that can handle enormous input sets on real computers, with their limited memory, an algorithm that processes data as it's read without storing all of it, is a completely different question. One you can ask about any problem. Anyone want to answer it for this case?

But O(nlogn) from sort and O(n) are indistinguishable, so no test would be able to force linear time solution.

Is f(n) = 1 + f(n/2)?

@Przemyslaw: Setting the time limit appropriately should do it (1 second total for all test cases?). If someone manages to make a O(nlogn) algorithm work, good for them. That would probably be harder than finding a O(n) solution.

You can consider O(logn) to be the same as O(1) for practical purposes, but that big-oh still implies a constant. log_2(100000) is over 16, so all else being equal, O(n) is still 16 times faster than O(nlogn). (The constant in the O(n) algorithm is small, btw.)

@Kailash: You're close.

@ Michel..f(n) = ceil(log2(n)). isn,t it???

@Michael:

You are totally wrong, reading input would take much longer than difference between O(nlogn) and O(n).

And still, O(n) can be slower than O(nlogn) that uses sort().

I am curious to know what was the  old solution that the judge had for this problem?

I think the previous solution to the judge gave just the number of errors.

@kailash.. yes Even I think so because Stephen,s very fiirst AC was giving ans=3 for the sequence 4 3 2 1.

And i think f(n) = 1 + f(n/2) corresponds to ceil( log2(n) ) only. what do u think??..

But using this approach i didint get my solution acceped. May be i was not handling the duplicates well.

Re duplicates: what does your code output for this?

7
1 6 5 3 2 4 3

Answer should be 2. My second attempt at this problem (which was accepted after the first rejudge, then wrong) output 3 instead.

f(n) = 1 + f(n/2) is equal to ceil (log n to base 2). I hadnt gotten this. I was only outputting the no. of errors. I need to submit with the change once the problems are moved to practice rooms.

when will you make the solutions public?

will these problems be moved into the practice tab ? If so when ?

@Przemyslaw: You're talking about a specific O(nlogn) solution that happens to be fast. I'm talking about general O(nlogn) solutions that can be ten times slower than the O(n) solution. So sure, you can't force us to find the intended solution, but you could have tried. There could very well be a slow solution that passes this, but misses the point of the problem, namely that the answer is a simple function of the number of errors.

Apart from that, allowing gaps spoils the problem. Please tell me that you if you knew the no-gaps case has a fast linear-time solution, you wouldn't have allowed gaps. You understand why that spoils the problem, right? The point of this problem clearly is that the answer is a  function of the number of errors, and that there is a simple procedure for eliminating repeated numbers. That there happens to be a O(nlogn) solution that is just as fast (I can give you a pretty fast one that doesn't even find the answer as a function of the number of errors) is unfortunate, and makes the problem somewhat less interesting than I thought at first. Forcing solutions to be O(nlogn) spoils it for those who found it interesting to look for a O(n) solution (while making no difference to those who are happy with a fast O(nlogn) solution). With no gaps my algorithm should take less than a second, but as it is it takes 13 seconds. Can you understand that that kills it? Running time totally dominated by solving a simple and inessential part of the problem? Yes, it could be faster. I did a stable sort using a comparison function, to simplify the code. Can you understand that there's no fun in optimizing sorting when that's not what the problem is about? For some people, at least?

Why not keep things simple? Why don't you stick to the essential problem? Refusing to give the range of input, for instance. (Btw, using asserts is not as easy as you seem to think. It's possible to get a WA before an assertion fails.) Why add these exercises? Another example is K-important strings. The interesting part is finding the length K. Having to give the actual sequence and offsets is just a pain. That one wasn't a big deal, but still.

It looks like the answer is ceil( log ('errors' + 1) base 2). I won't call it a good problem in this case. I can't see any programming challenge involved here. The real challenge might be asking to come up with the subset of numbers selected in each step.

@ venkatraman Im ny solution I was outputting ceil(log2(errors+1)) only. But still it was not being accepted even In the final rejudge. That mean I was not handling the duplicates properly.

Can anybody please explain how to handle duplicates in this problem??

@Michael:

It's not O(n) if you translate numbers from decimal to binary on input in the straightforward manner, without employing additional tricks to do it in constant time.

@Michael:

Having to give the actual sequence and offsets is just a pain.

I disagree. It asks you to print the optimal solution not just its length, I see no problem with that. It's a bit more programming than not having to print it, but it is a programming contest, it's pain for you but fun for me :) I don't see a problem there.

Forcing solutions to be O(nlogn) spoils it for those who found it interesting to look for a O(n) solution [...] there's no fun in optimizing sorting

You seem to be contradicting yourself here. First you talk of all the fun you could have had by optimizing sorting to be O(n) by using some version of count-sort for a specific kind of input with limited values, then you say it's no fun optimizing sorting.

Refusing to give the range of input, for instance.

Totally agree, I see no reason for that. Especially since the input numbers were actually quite small, so basically the worst case (humongous numbers) wasn't covered.

The comment system reversed my italics in the first paragraph. Weird.

@Venkataramana

I can't see any programming challenge involved here. The real challenge might be asking to come up with the subset of numbers selected in each step.

You are interpreting the word "programming" too restrictively, in the context of programming contests. Solving the challenge you mention is part of programming.

For what its worth, I'm with tomek on all the above points. It was a cute problem, and should not have been changed in any way other than specifying input constraints. Saying they fit in 32 bit signed integers would suffice. Telling us we are expected to find them with assert statements is just rubbish.

@Michael:

Problem is, task was supposed to be rather simple problem and by suprise and my failure, it accidentally happened to be rather hard problem. If from the beggining my intention had been to make hard problem, i would have make rather elegant problem. But instead, i added some unnecessary programming excercises.

@Tomek,Stephen:

I was just lazy, and then simply stubborn. Next time I improve, I promise :)

@Tomek: Actually, I was under the wrong impression that Codechef calls these contests "algorithm challenges". The "December Algorithm Challenge" must be where I got it from, but that turns out to be a one-off description. That, and the fact that these contests look a lot like what I understand by "algorithm challenges". The challenge always lies in finding the algorithm, never the implementation. But I see now it's "Programming Competitions". Whoops. Sorry. So "programming" it is. Not a big deal. I like programming too, just not as much when it feels out of place.

I didn't contradict myself. If there are gaps, I use sort() to find for each number x that occurs (other than the maximum one), the smallest number greater than x that also occurs. If there are no gaps, I know it's x+1. No sorting required. The solution I submitted takes advantage of the sequence being sorted anyway, but the O(n) solution doesn't sort anything.

About translating input not being O(n). True. Of course, I should never have used complexity when making statements about actual performance. It seemed convenient. I did say early on that the O(n) algorithm is in fact fast, and then I explained that by O(nlogn) I really mean 10 times slower.

@Przemyslaw: Ok, good to know. Personally I'd still prefer that, but as it turns out, programming exercises are part of what it's all about. In fact, rather make these exercises more challenging then. Use humongous numbers. Make us optimize our code. Make me learn AT&T syntax. (Not really the last one, please.)

Michael:

It's difficult to read through your sarcasm.

Let me just say: I don't see "programming" and "algorithms" as separate or contradictory. Programming is the formal way of describing algorithms.

Finding an optimal solution often requires a little more complicated algorithm and data structures, hence a little more lines of code, than just finding its score.

@Tomek: Wow. I simply wasn't being sarcastic. I see algorithms as part of programming. A part you do on paper. An algorithm contest is then about paper problems, with some programming required to enable automated judging.

I honestly believed that CodeChef is all about algorithms. When you said "programming contest" I checked. Somehow I never noticed that only the December contest (my first) was called an algorithm contest.

I do feel that for a programming contest, there is too little emphasis on areas other than algorithms. What there is beyond finding algorithms is so little that it just seems out of place.

Code optimization is part of programming. One I like, so that wasn't sarcasm either. I don't see anything wrong with a problem that isn't about finding an algorithm, but about an efficient implementation of one.

Well, there were also January, February and March Algorithm Challenges (as you can see in the "Compete" menu), which is why I assumed sarcasm. And then I'm confused by first your dislike for having as input a sequence of numbers with gaps, and then "Use humongous numbers. Make us optimize our code." which is where I again assumed sarcasm.

Given it's not sarcasm, I am very confused by your opposing views, between your dislike for optimizing and preference for fast solutions, and "make us optimize our code". Also between "don't have gaps between numbers" and "use humongous numbers". I don't understand how it depends on whether it's an "algorithm challenge" or a "programming contest", since both are pretty much same to me, and CodeChef also uses them interchangeably. You like these things if it's call one thing, but fervently oppose them since they're no fun if it's called another? I just don't get it.

There was no need to optimize anything, BTW. I just used STL's sort, and it ran in time. I just don't see what the problem is - you'd want larger inputs? What for? Would that eliminate some solutions?

I believe your quasi-O(n) solution must be somewhat similar to count-sort (both being simple algorithms that involve having an array entry for each possible value). Count-sort would have been an obvious way to speed it up for me. Given 32-bit numbers, you could still sort pretty fast by radix-sort, if you cared to have  a quasi-O(n) solution.

Basically you're saying: there are some "dull and easy" pieces of the tasks, and you don't like them. Well, if they're so easy, I believe they should cause you no trouble to solve in 5 minutes. If it takes you more and causes you pain, that's proof they are not so easy.

But then you turn around and say "oh, it's a 'programming' contest, I see, let's have more of those dull and easy tasks" which I completely don't understand.

Anyway, sorry for complaining so much about your comments Michael...

I guess you have a certain vision of what the problems should be which I don't quite share, and I think you'll find it hard to convince people to reduce every problem to just some bare essentials - without extra sorting steps, without computing extra solution details, etc. I think such a borderline simply doesn't exist - I don't think these are less valuable parts of an algorithm than others, and I think this approach could be taken to absurdity by becoming a math puzzle that you just answer or not.

But of course maybe you have a valid idea for some problems, and then what you could do is to set some problems.

I think Michael's opinion of what an algorithm contest should be isn't shared by most other people. Even the Google Codejam itself which is:

a programming competition in which professional and student programmers are asked to solve complex algorithmic challenges in a limited amount of time

is similar to this - a couple of years ago there was one problem which algorithmically was a trivial BFS, but the steps involved were complex leading to a lot of code. Another problem had a solution which could be written in very little code but was one of the harder problems.

If you're looking for something where the point is to solve things on paper, you should go to projecteuler.net instead. You won't find that idea in any online programming competition, whether its name contains the word 'algorithm' or not.

Tomek, I tried sending you a pm on the forum. Not sure if it worked. Here I'll just say this:

I didn't see those links. I see now how sarcastic my post looked. Sorry about that.

I never said "give us more dull and easy tasks". I said "make these exercises more challenging". In other words, DON'T make the extras dull and easy.

I never said I don't like optimizing. In a particular place I didn't like it. All you have to understand is that what's fun in one context may spoil things in another context. For me. You may disagree, but that doesn't make it a contradiction.

Also, I didn't mean add huge numbers to TrafficJam. I meant use that somewhere appropriate. What I said about an optimizing problem that doesn't involve finding an algorithm shows that I wasn't talking about TrafficJam. Ideally, non-algorithmic problems should be problems on their own, but it's ok if they're added in appropriate places.

And yes, I realise that not many people agree that problems should ideally be bare-bones (algorithmic or not). I gave my feedback, hoping some people would agree. So they don't. Now I know. Let's move on.

@{Tomek,Stephen}: +1

Thanks for defending my point of view better than I could.

Sorry (for being off-topic), but I couldn't resist: http://xkcd.com/386/

Can some one give a proof of correctness of the solution to this problem

Thanks Chen for your answer. I could understand it only partly. Can you please tell on what basis is a particular number picked or not during a step(operation).

Here is a method simpler to explain.

Consider 5 1 8 2 7 9 3 6 4

Start from 1, and go forwards, marking each consecutive number with an A; if we need to go backwards to get to the next number, go to B etc.

1,2,3,4 get marked as A

5,6 get marked as B

7 gets marked as C

8,9 gets marked as D.

BADACDABA

Now pick all the As, Cs, Es, .. (every second letter)

AACAABDDB

In the next step, all the As are before all the Bs, all the Cs are before all the Ds, etc. So the As and Bs will become one letter, the Cs and Ds will become the second letter etc. In other words, the number of letters gets halved (roughly, actually n -> ceil(n/2)).

When we get down to one letter, we're done.

Thanks Stephen. I understand it now.