#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]

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]