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]

## Positive or Negative

Solutions The linear solution is simple: just count the frequencies of both negative and positive integers. However, the optimal solution is more interesting: leveraging the sorted nature of the array, we can exploit binary search. Here’s where a crucial detail comes into play: 0 is neither positive nor negative. Consequently, searching for 0 presents us with an opportunity to swiftly determine the count of positive and negative integers. In essence, we need to recall two fundamental concepts regarding binary searches: [Read More]