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]

New Year Chaos

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]