UVa 11495

From Algorithmist
Jump to: navigation, search

11495 - Bubbles and Buckets[edit]

Summary[edit]

This is the standard problem of counting the number of inversions in a string of length n\leq 100000. In a sequence A, the pair (i,j) is an inversion of A if i<j and A_{i}>A_{j}.

Explanation[edit]

Given the big string length, a brute-force O(n^{2}) solution won't pass. Check UVa 10810 and UVa 10327 for possible solutions. First player wins if the number of inversions is odd, while the second does so if the number is even.

Gotchas[edit]

As explained in UVa 10810, worst case number of inversions possible = {\frac  {n(n-1)}{2}}. Given the big size of n, a 32-bit integer holding the inversions count won't suffice.

Notes[edit]

How can we exploit the fact of having the string alphabet known beforehand?

Input[edit]

5 1 5 3 4 2
5 5 1 3 4 2
5 1 2 3 4 5
6 3 5 2 1 4 6
5 5 4 3 2 1
6 6 5 4 3 2 1
0

Output[edit]

Marcelo
Carlos
Carlos
Carlos
Carlos
Marcelo