SRM 594

Last Thursday's SRM was a rather unusual round, I don't know yet whether I made an improvement in my coding skills or both 250 and 500 problems were easier than usual and 1000 was harder than usual, with big constraints and xor operations, so will write the ones I managed to solve.

LittleElephantAndBallsAgain - 250

Given a string composed of 'R', 'G' or 'B', the problem asks for the minimum number of border removals to make the string with only one kind of character. As I'm in a dynamic programming moment, I ended up with a dp solution, stating the minimum value of a left removal or a right removal, as my code follows, but there's ways easier to code solution. Imagine that the string is composed of only non sequential characters ("RGBRGB") the obvious answer is (|string.length| - 1). Using a string ("RGBBBRG") as an example, i'ts clear that the best option is to remove both the prefix "RG" and the suffix "RG" to make a string containing only 'B' characters. With this in mind, it's clear that the best answer will be always (|string.length| - |length of the longest sub string with equal characters|).

My solution complexity: O(n^2)
Best solution complexity: O(n)

LittleElephantAndIntervalsDiv2 - 500

Given a sequence of |M| white balls and |N| intervals of the sequence to be painted of black of white, the problem asks the return the number of different sequences after |N| paints. With low constraints (N < 10 and M < 100), a complete search was clearly feasible. But with and clever idea, you can see that there's a finite number of balls to be painted, counting the number of balls that can be painted, we know that for them, there are 2 possible outcomes, paint black or white, resulting as (2^(|balls possibly painted|)).

My solution complexity: O(2^n)

Best solution complexity: O(n * log(n))