How I solved the UVa 12004 - Bubble sort

Here's the Problem link. This blog entry is about how I solved the problem as it brought me lots of joy!

CAUTION: Read further only if you are stuck because the solution lies below. Beware of the spoiler below :-)

Inputs:
Max text cases 1000
each n will be 1<= n <= 100000

Output:
Average value of 'count' which is the number of swaps

Solution:
Number of permutations for 1 2 3 ... n = n!
To get to the average, we need to know the number of swaps and the frequencies of all the swaps so that
the we can multiply the number of swaps and the frequencies and divide by the factorial of the number.

So, a helper C++ implementation was created to print the number of swaps and the frequency of each swap using this format: Num swaps count~~frequency
1: # permutations= 1,       Num swaps count~~frequency for 1:,0~~1,
2: # permutations= 2,       Num swaps count~~frequency for 2:,0~~1,1~~1,
3: # permutations= 6,       Num swaps count~~frequency for 3:,0~~1,1~~2,2~~2,3~~1,
4: # permutations= 24,     Num swaps count~~frequency for 4:,0~~1,1~~3,2~~5,3~~6,4~~5,5~~3,6~~1,
5: # permutations= 120,   Num swaps count~~frequency for 5:,0~~1,1~~4,2~~9,3~~15,4~~20,5~~22,6~~20,7~~15,8~~9,9~~4,10~~1,
6: # permutations= 720,   Num swaps count~~frequency for 6:,0~~1,1~~5,2~~14,3~~29,4~~49,5~~71,6~~90,7~~101,8~~101,9~~90,10~~71,11~~49,12~~29,13~~14,14~~5,15~~1,
7: # permutations= 5040,    Num swaps count~~frequency for 7:,0~~1,1~~6,2~~20,3~~49,4~~98,5~~169,6~~259,7~~359,8~~455,9~~531,10~~573,11~~573,12~~531,13~~455,14~~359,15~~259,16~~169,17~~98,18~~49,19~~20,20~~6,21~~1,
8: # permutations= 40320,   Num swaps count~~frequency for 8:,0~~1,1~~7,2~~27,3~~76,4~~174,5~~343,6~~602,7~~961,8~~1415,9~~1940,10~~2493,11~~3017,12~~3450,13~~3736,14~~3836,15~~3736,16~~3450,17~~3017,18~~2493,19~~1940,20~~1415,21~~961,22~~602,23~~343,24~~174,25~~76,26~~27,27~~7,28~~1,
9: # permutations= 362880,  Num swaps count~~frequency for 9:,0~~1,1~~8,2~~35,3~~111,4~~285,5~~628,6~~1230,7~~2191,8~~3606,9~~5545,10~~8031,11~~11021,12~~14395,13~~17957,14~~21450,15~~24584,16~~27073,17~~28675,18~~29228,19~~28675,20~~27073,21~~24584,22~~21450,23~~17957,24~~14395,25~~11021,26~~8031,27~~5545,28~~3606,29~~2191,30~~1230,31~~628,32~~285,33~~111,34~~35,35~~8,36~~1,
10:# permutations= 3628800, Num swaps count~~frequency for 10:,0~~1,1~~9,2~~44,3~~155,4~~440,5~~1068,6~~2298,7~~4489,8~~8095,9~~13640,10~~21670,11~~32683,12~~47043,13~~64889,14~~86054,15~~110010,16~~135853,17~~162337,18~~187959,19~~211089,20~~230131,21~~243694,22~~250749,23~~250749,24~~243694,25~~230131,26~~211089,27~~187959,28~~162337,29~~135853,30~~110010,31~~86054,32~~64889,33~~47043,34~~32683,35~~21670,36~~13640,37~~8095,38~~4489,39~~2298,40~~1068,41~~440,42~~155,43~~44,44~~9,45~~1,

How to interpret the above data:
# permutations= 6,      Num swaps count~~frequency for 4:,0~~1,1~~3,2~~5,3~~6,4~~5,5~~3,6~~1,
0~~1 => 0 swaps occurs 1 times
1~~3 => 1 swaps occurs 3 times
2~~5 => 2 swaps occurs 5 times
3~~6 => 3 swaps occurs 6 times
4~~5 => 4 swaps occurs 5 times
5~~3 => 5 swaps occurs 3 times
6~~1 => 6 swaps occurs 1 times
The above data is generated using the following permutations of 1, 2, 3, 4
1, 2, 3, 4,
1, 2, 4, 3,
1, 3, 2, 4,
1, 3, 4, 2,
1, 4, 2, 3,
1, 4, 3, 2,
2, 1, 3, 4,
2, 1, 4, 3,
2, 3, 1, 4,
2, 3, 4, 1,
2, 4, 1, 3,
2, 4, 3, 1,
3, 1, 2, 4,
3, 1, 4, 2,
3, 2, 1, 4,
3, 2, 4, 1,
3, 4, 1, 2,
3, 4, 2, 1,
4, 1, 2, 3,
4, 1, 3, 2,
4, 2, 1, 3,
4, 2, 3, 1,
4, 3, 1, 2,
4, 3, 2, 1,
The permutations were generated using the next_permutation algorithm in C++ STL.

Doing a bit more math on:
0~~1 => 0 swaps occurs 1 times
1~~3 => 1 swaps occurs 3 times
2~~5 => 2 swaps occurs 5 times
3~~6 => 3 swaps occurs 6 times
4~~5 => 4 swaps occurs 5 times
5~~3 => 5 swaps occurs 3 times
6~~1 => 6 swaps occurs 1 times
-------------------------------
Adding up just the times: 1 + 3 + 5 + 6 + 5 + 3 + 1 = 24. Interestingly, that is the same as 4!
To get Average, first multiply the num swaps and frequency and add them all to get the numerator.
Numerator = (0*1 + 1*3 + 2*5 + 3*6 + 4*5 + 5*3 + 6*1)
Numerator = ( (6+0)*1 + (1+5)*3 + (2+4)*5 + 6*3) )
Numerator = ( (6*1 + 6*3 + 6*5 + 6*3) )
Numerator = ( 6* (1 + 3 + 5) + 6*3) )
Numerator = ( 3* (2*1 + 2*3 + 2*5) + 6*3)
Numerator = ( 3* (2*1 + 2*3 + 2*5 + 6))
Numerator = ( 3* (1 + 3 + 5 + 6 + 5 + 3 + 1))
Numerator = ( 3* (4!))

Denominator = n! = 4!

Avg = Numerator / Denominator
Avg = ( 3* (4!))/4! = 3
Observation: This is the same as (Max number of swaps / 2) = (6/2) = 3

Doing the same for 1 2 3 4 5
# permutations= 120,     Num swaps count~~frequency for 5:,0~~1,1~~4,2~~9,3~~15,4~~20,5~~22,6~~20,7~~15,8~~9,9~~4,10~~1,
Num permutations = 720
Swaps~~Times
0~~1,
1~~4,
2~~9,
3~~15,
4~~20,
5~~22,
6~~20,
7~~15,
8~~9,
9~~4,
10~~1,
Adding up the Times:
1 + 4 + 9 + 15 + 20 + 22 + 20 + 15 + 9 + 4 + 1 = 120 = 5!
To get Average, first multiply the num swaps and frequency and add them all to get the numerator.
Numerator = ( (0+10)*1 + (1+9)*4 + (2+8)*9 + (3+7)*15 + (4+6)*20 + (5)*22 )
Numerator = ( 10*(1 + 4 + 9 + 15 + 20) + (5)*22)
Numerator = ( 5* (2*1 + 2*4 + 2*9 + 2*15 + 2*20) + 5*22)
Numerator = ( 5* (2*1 + 2*4 + 2*9 + 2*15 + 2*20 + 22))
Numerator = ( 5* (1 + 4 + 9 + 15 + 20 + 22 + 20 + 15 + 9 + 4 + 1))
Numerator = ( 5* (5!))

Denominator = n! = 5!

Avg = Numerator / Denominator
Average = ( 5* (5!))/5! = 5
Observation: This is the same as (Max number of swaps / 2) = (10/2) = 5

Doing the same for 1 2 3 4 5 6:
# permutations= 720,    Num swaps count~~frequency for 6:,0~~1,1~~5,2~~14,3~~29,4~~49,5~~71,6~~90,7~~101,8~~101,9~~90,10~~71,11~~49,12~~29,13~~14,14~~5,15~~1,
Num permutations = 720
Swaps~~Times
0~~1,
1~~5,
2~~14,
3~~29,
4~~49,
5~~71,
6~~90,
7~~101,
8~~101,
9~~90,
10~~71,
11~~49,
12~~29,
13~~14,
14~~5,
15~~1,
Adding up the Times:
1 + 5 + 14 + 29 + +49 + 71 + 90 + 101 + 101 + 90 + 71 + 49 + +29 + 14 + 5 + 1 = 720 = 6!
To get Average, first multiply the num swaps and frequency and add them all to get the numerator.
Numerator = ((0+15)* 1 + (1+14)*5 + (2+13)*14 + (3+12)*29 + (4+11)*49 + (5+10)*71 + (6+9)*90 + (7+8)*101)
Numerator = ( 15*(1 + 5 + 14 + 29 + 49 + 71 + 90 + 101) )
Numerator = ( 15* ((1 + 5 + 14 + 29 + +49 + 71 + 90 + 101 + 101 + 90 + 71 + 49 + +29 + 14 + 5 + 1))/2 )
Numerator = ( 15* ((6!))/2)

Denominator = n! = 6!

Average = Numerator / Denominator
Average = ( 15* ((6!))/2)/6!
        = 15/2
Observation: This is the same as (Max number of swaps / 2) = (15/2)

Yet another observation:
Max number of swaps = n * (n - 1) / 2

What are these numbers:
1
1 + 1
1 + 2 + 2 + 1
1 + 3 + 5 + 6 + 5 + 3 + 1
1 + 4 + 9 + 15 + 20 + 22 + 20 + 15 + 9 + 4 + 1
1 + 5 + 14 + 29 + +49 + 71 + 90 + 101 + 101 + 90 + 71 + 49 + +29 + 14 + 5 + 1
If you Google this, you will be arriving at http://oeis.org/A008302 which is the Triangle of Mahonian numbers.
I saw some numbers, but until I summed them up, I did not realize they were adding up to n!

There was a bit of a detour too where I found out that the maximum coefficient of the Mahonian numbers is a
part of the http://oeis.org/A000140 which is Kendall-Mann numbers used in inversions!!!

Really great to know about the oeis.org - On-Line Encyclopedia of Integer Sequences!
Many thanks to Praveen for showing me the problem and for reviewing this blog enty. 
One more spoiler: here's the source code.

CP3: chapter 2 problems progress

1D Array manipulation
UVa 10038 - Jolly Jumpers
UVa 11340 - Newspaper
C++ STL Algorithm
UVa 10107 - What is the Median?
C++ STL Stack
UVa 514 - Rails
C++ STL Map
UVa 11286 - Conformity
UVa 11572 - Unique Snowflakes
C++ STL priority_queue (Java PriorityQueue)
UVa 10954 - Add All
C++ STL queue and deque (JavaQueue and Deque)
UVa 110344 - Ferry Loading IV

CP3: Chapter 1 problems progress

Section 1.3.3:

Solved Super easy problems: 
UVa 00272 - TEX quotes
UVa 11172 - Relational operators
UVa 11498 - Nlogonia
UVa 11727 - Cost Cutting
Solved Easy problems:
UVa 11942 - Lumberjack sequencing
UVa 11799 - Horror Dash
UVa 11559 - Event Planning (2)
Solved Medium problems:
UVa 00119 - Greedy gift givers
Section 1.4:
UVa 401 - Palindromes
10945 - Mother bear

Book: Competitive Programming 3 (CP3)

Got the book "Competitive Programming 3" from lulu.com yesterday. Here's the supporting site for the book. The ebook is not going to be available until next year :( which is not a good thing for me. I like to search for content and the ebook would have been really good. I have the first edition of the ebook (bought it in place of buying the 2nd edition by mistake.) The first edition of the ebook is available for free from the supporting site.

This took about 23 days from the order date to reach India. Check the home page before you place the order because lulu could be offering some discounts. I did not check and probably lost saving 5%.

Lots of learning ahead.

Bought 2 more copies for my friends :-). Because of this book, I have solved 108 UVa problems now (5-Dec-2013)

Thoughts on UVA: 10137: The trip

The trip is a very interesting problem, but the fact for me is that I haven't been able to solve it even after a long time. I have collected all the test cases available in the board and all except 1 test case fails and I have no idea how to solve it. Here's the failing test case:

15
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
The expected answer is: $0.02, while my solution says $0.01. 
To me, it looks like there is some key piece in the problem statement that is missing for me to correctly figure out the answer. I also felt that arriving at my current solution was also not very straight forward. I believe that clearing up the problem statement will help people to understand it better and solve it. The problem's success rate is average probably because of this reason.
My learnings:
1. Program to use money like the way it is being by people. Do not go for floats and doubles. That will help in avoiding magic like floor, ceiling. I got this hint from Prof.Skiena's programming challenges videos. The original link seems to be dead :(
2. The way to compute average is very key to be able to get to a solution and to be able to explain it to others. What is a solution if it cannot be understood by others? What is a solution if it cannot be explained to others?

UVA: 11942: Lumberjack Sequencing and 11461: Square numbers

Got both problems Accepted.

11942: Lumberjack Sequencing - tried binary search and found it to be tedious to program and difficult to get right. Switched to linear search and it simplified the number of cases to be handled.

11461: Square numbers - interesting thing here is that we need to remember the length of the beards as we proceed. I was thinking of comparing diff(i - 1, i) with diff(i, i + 1), but again, need to remember the history. So, I kept the implementation simple by remembering the last diff and the current.

Small problems can teach us quite a bit.

Thanks to Alluri for solving the problems ahead of me and recommending them to me.

CodeChef March challenge 2013 problems

Solved Approximately (APPROX) and Tourist Translations (TOTR). APPROX could have been solved a bit more mathematically and TOTR could have been more efficient.
A question that an algorist has to ask: Can I do better?

Competitive programming skillset links

This link is on the dot. Must know if you really want to make progress. I was planning to construct one, now, I can just reuse.

I landed up there from uHunt training series.

This is their programming site.

BTW, I have their book: Competitive Programming 2.

UVA 10035 - Primary Arithmetic : Accepted

UVA 10035 - Primary Arithmetic accepted :) sweet :) but, it was on the 7th attempt.

Tip: if you are printing the output, add the '\n' after every output.

I tried solving it in two ways: 

1. Taking the numbers into char arrays:

The char array solution was difficult to code because I reversed each array, started to iterate until the array with min length, then traverse until the end of the longer array to get to the final answer. I made a number of mistakes here:

* Instead of iterating over revNum1, I iterated of num1

* The minLen was using the length of the larger array (mainly due to copy paste)

* I had to construct quite a few testcases to assure myself of the correctness

2. Taking the numbers as numbers:

This was simpler to code and I knew that I had the correct answer without crossing my fingers unlike the previous option. Keeping the implementation simpler assures you of the 'Accepted' state and you know that a 'WA' in this case means that something is wrong in the output format and not your code :-)

Also I could reuse the logic from my earlier solution to 10018 - Reverse and Add.

UVA 469 Wetlands of Florida Accepted

Solved yet another UVA problem: Wetlands of Florida. Feels good. One odd thing in this problem was handling the input. In the solution, I initially went with the recursive DFS which failed on my test case containing a 99x99 'W' wetlands map. I changed to follow one of the good implementations of Chefhack by msasha. Some implementations are so very user friendly than machine friendly.

Many thanks to the codechef CHEFHACK editorial to list this problem.

Email excerpt from the online judge: "Your submission with number 11309634 for the problem 469 - Wetlands of Florida has succeeded with verdict Accepted."