# UVa 11495

From Algorithmist

## 11495 - Bubbles and Buckets[edit]

## Summary[edit]

This is the standard problem of counting the number of inversions in a string of length . In a sequence , the pair is an inversion of if and .

## Explanation[edit]

Given the big string length, a brute-force 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 = . Given the big size of , 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