#sorted sequence

Solutions This problem has two main solutions. The first fully exploits the structure of the constraints, the second is more general. Tradeoffs of both: we remove all the duplicates. In a different context this could be forbidden and then we would have to use extra space or another logic; we don’t really change the score table. Instead, in a real game it’s very likely that we need to update the current scores (e. [Read More]

Solutions We can see, intuitively, that the number of people a person \(p\) has bribed corresponds to the number of people on her right with value less than \(p\). For instance: 1 1 2 3 5 4 In this case, \(5\) has bribed \(4\) and took her position. Another example: 1 2 1 5 3 4 We have three bribes: \(2\) has bribed \(1\) \(5\) has bribed \(4\) \(5\) has bribed \(3\) This problem is equivalent to calculating the number of inversions of the array, that is the number of elements that are out of the natural order of a sequence. [Read More]