Match Editorial

Match summary

Almost 1000 contestants from all around the world, with 6 targets among them, celebrated Valentine’s Day by taking part in this SRM. In Division 1 the match started off silently, as coders were greeted by a long (and less friendly than usual) easy problem. As time passed, however, solutions did start to roll in. Coders then moved on to an easy medium that barely slowed them down -- but the hard was another story. Even though a great number of contestants compiled and tested their solutions, only 9 of them were able to pass the examples and submit. In an impressive performance, ACRush was on top of the pack almost from start to finish and amazed those in attendance with an incredible score on the 1000, going into the challenge phase with a commanding lead over the second placeploh. The thorough examples on all the problems led to a relatively dull challenge phase, but zhuzeyuan managed to pull in second place with the help of three successful challenges. As the dust settled, the top 3 remained unchanged, with two yellows, Loner and tsjoker rounding up the top five. All in all, 7 coders were able to solve all tasks.

It was not an easy night in Division II either. Most coders were able to submit the easy very quickly but were stumbled by the medium. The challenge phase was quite eventful and a lot of easy submissions were brought down. In the end it turned out that newcomers dominated this division and the win went to TOXA, followed by klopyrev and phosphor00. Five coders managed to solve all three questions correctly.

The Problems

Value	250
Submission Rate	468 / 489 (95.71%)
Success Rate	269 / 468 (57.48%)
High Score	power_lh for 249.48 points (1 mins 18 secs)
Average Score	217.77 (for 269 correct submissions)

This problem asked for nothing more than just implementing the algorithm described in the statement. This is actually known as the Martingale system. First of all, the value of the bet for the following round should be kept in a variable. Then you have to loop through all rounds, one at a time. For each round, you need to compare the value of the bet to the current sum and see if it is possible to bet this round. If not (the value of the bet is larger), then stop and return the current sum. This was the step that some coders omitted and that led to a bunch of challenges. Otherwise, check the corresponding character from the input string outcome. If it is a ‘W’, denoting a winning round, add the value of the variable to the current sum, and then reset it to 1. Otherwise the ‘L’ character is encountered, so you should subtract the value of the current bet from the sum. Finally, we return the sum after all rounds are played. See klopyrev’s solution for a nice implementation.

Value	500
Submission Rate	85 / 489 (17.38%)
Success Rate	53 / 85 (62.35%)
High Score	fhoward for 369.73 points (18 mins 16 secs)
Average Score	227.11 (for 53 correct submissions)

Value	250
Submission Rate	295 / 410 (71.95%)
Success Rate	242 / 295 (82.03%)
High Score	ACRush for 229.47 points (8 mins 39 secs)
Average Score	141.50 (for 242 correct submissions)

This problem asked to simulate little Billy’s strange method of traveling by bus. However, the implementation was anything but easy and required a lot of work and attention from the contestants and the average score received was low.

The first step in solving the problem is parsing the input and keeping each of the bus routes in a list. Then, the question boils down to the following subproblem: given a station A, where Billy is in at the current moment in time, find the next time a bus passes through this station. To handle this, loop through all buses that pass through station A, and for each bus figure out the next time it arrives at A. This can be done by simulating the bus route and stopping when it reaches A at a moment greater than the current time. See JongMan’s nice implementation as an example. As an alternative, you can use some simple arithmetic: if the first time a bus passes through station A is t0, then the bus passes through A at all times t equal to t0 modulo P, where P is the time it takes the bus to perform one whole cycle (that is, t % P must be t0), like in lovro’s solution.

I find it somehow easier to use the concept of states here. At any point in his trip, little Billy’s state s is determined by the location he is in, v, and the current time, t. From each state there is a single follow-up state. There are two cases to consider, depending on the number of buses leaving location v at time t. If there are no such buses, the follow-up state is (v, t+1). Otherwise, you need to consider only the bus that appears first in the input, and the follow-up state will be (u, t + abs(v-u)), assuming the station following v on the bus route is u. Now you have to simply work your way through this state space and stop either when the location is 0 or the time exceeds the limit given in the statement. You need to return the value of the time in the former case, and -1 in the latter. The fastest submission by ACRush follows this approach.

Value	1000
Submission Rate	42 / 489 (8.59%)
Success Rate	22 / 42 (52.38%)
High Score	TOXA for 881.28 points (10 mins 43 secs)
Average Score	607.61 (for 22 correct submissions)

This was a nice dynamic programming exercise for Division II coders. If you need a start with this very important technique see Dumitru’s tutorial.

The first step in all dynamic programming problems is to define a state space. This is usually the toughest part of a DP solution, but practice makes it much easier and reveals many similarities between problems. In this case, as in BusTrip, a state is defined by the station where Billy is, and the current time. We need to find the minimum cost of reaching each state. Then let best[t][v] be the minimum cost of being in station v at the moment of time t. There are two alternatives to consider: either Billy has been waiting for at least one minute, in which case the cost will be best[t-1][v] (since the cost best[t-1][v] is optimal for being at station v at time t-1 and there is no point to consider a way to be in that state with a higher cost), or he has just arrived there in a bus coming from a station u. Assuming the time it takes the bus to travel from u to v is t0, and the cost of the ticket for this bus is c, this alternative’s cost will be best[t-t0][u] + c, since at time t-t0 Billy was in station u (with an optimal cost!) and then took the bus with a cost c. Of course, we have to loop through all buses that arrive at station v at time t, and then pick the alternative with the minimum cost. After deciding on the recurrence we still need to identify the initial conditions. Billy starts at station 0 at time 0, so we initialize best[0][0] to 0 and best[0][s] to a very large value (signifying infinity, impossibility) for all other stations s. Notice that to calculate the optimal cost of being in a station at some moment of time, we need the optimal costs of being in all stations at previous times so we can fill up the table best in increasing order of times. See rwaliany’s solution for an implementation of the DP solution, or, for a memoised version, check this solution by areniis.

As a sidenote, this approach can be made to run in the time complexity O(T*N + B), with B denoting the number of buses, by keeping a hashtable containing for each state a list of the buses that arrive there. You can also sort the buses in increasing order of arrival times, using either a comparison sort, yielding the time complexity O(T*N + B log B), or a linear sort (like radix sort, and keeping the time complexity as in the hashtable version). A solution that used the idea of sorting the buses was submitted by ghostyo.

There was also a way out for coders who were unfamiliar with dynamic programming as well. The number of buses was rather small, and a decent backtracking solution would be able to solve the task within the time limit. See klopyrev’s solution for such an example.

Value	450
Submission Rate	251 / 410 (61.22%)
Success Rate	205 / 251 (81.67%)
High Score	Spieler for 430.79 points (6 mins 3 secs)
Average Score	330.81 (for 205 correct submissions)

Making up for the tougher easy this medium was an easy task for Division I coders. It required basic knowledge of probability theory and dynamic programming or memoisation.

The thing to note here is that before playing one round, the player’s state is influenced by the sum he currently has, the remaining number of rounds, and the value of the bet for the round -- which, as described in the problem statement, is a power of 2. That being said, let pwin[s][r][b] be the probability that the player reaches his goal if he currently has s dollars, there are r rounds left and the stake is 2^b (corresponding to losing the last b rounds). The solution to the problem would then be pwin[initSum][rounds][0]. If s is greater or equal to goalSum, this probability is 1 (the player has already reached his goal); if the current stake is greater than the sum s, or there are no rounds left, it is 0.

Otherwise, the player will play this round, and there are two possible outcomes. If he wins the bet with probability p, then the next state will be described by the sum s + 2^b, r-1 rounds left, and the stake 1, so b = 0. If he loses the bet, with probability 1-p, his sum decreases to s - 2^b, there are r-1 rounds left and the value of the stake is doubled, so b is incremented. In other words the recurrence is given by:

pwin[s][r][b] = p * pwin[s + 2^b][r-1][0] + (1 – p) * pwin[s - 2^b][r-1][b+1]

This recurrence can easily be implemented with a memoised function, as in ctgPi’s solution. Try to implement an iterative dynamic programming solution if you haven’t already, as an exercise, or see fuwenjie’s solution for an example.

Value	1000
Submission Rate	11 / 410 (2.68%)
Success Rate	9 / 11 (81.82%)
High Score	ACRush for 942.31 points (7 mins 6 secs)
Average Score	585.41 (for 9 correct submissions)

This was a tough problem and required not only figuring out the correct algorithm but an efficient implementation as well.

After getting familiar with the question, it sounds like a greedy approach will work, since intuitively it would be better if lower seeded players were eliminated as soon as possible. However, as some contestants have noticed, none of the greedy approaches were enough by themselves and would end up failing some of the examples.

Let’s start by noting that if one player can defeat a player, any other lower-seeded player can defeat him. Derived from this is the observation that if a player can win the tournament than any other lower-seeded player can win it as well. To see this, imagine the whole evolution of the tournament in a tree structure, with the leaves being the players taking part in the competition and the internal nodes signifying matches played during the course of the tournament. Now consider the paths to the final round (that is, the root of the tree) of two players seeded u and v, with v < u, in a tournament won by u. These are nothing more than paths from the two leaves to the root in this tree. Now swap u and v on these paths – in other words let v meet the opponents u met in the tournament, and vice-versa. Obviously, since u could win all matches in its path, v can win them as well if only the opponents remained the same. The only round in which the opponent could be different is where these two paths meet. Let this round be denoted by m. The matter of concern is that v would get a stronger opponent in m due to the positioning of u in its previous path. Now, if u is not eliminated earlier than v in its new path, but is eliminated in the same round as v, which we'll call round r -- and remember u is weaker than v, so if the player met in round r can defeat v then it can also defeat u -- the rest of this path from r to m would remain the same. Otherwise, u is eliminated earlier by a player that v could defeat, and the player that would reach round r is defeatable by v. If this player can be eliminated at some point from r to m, the path remains the same from that point on. Ultimately, the opponent v would get in round m is either the same opponent as before or a player that it could defeat. In either case, v can progress to the next round and continue its way to winning the championship.

The first version of our solution could be to loop through all players in decreasing order of their seed and check if they can win the tournament. When we find a player that is able to do so, we stop and return his seed. The problem with this approach is that it would be too slow for a large number of players. However, using what was proven above, we realize that we can use binary search instead of the linear loop.

The need to design an algorithm to check if a player with seed u can win comes directly from the above. For this part, a greedy algorithm can be succesfully employed. One such algorithm generates the tournament tree in a top-down manner. First decide on an opponent for u to meet in the final: let this opponent be the lower seeded player, v, that u can defeat. Now move on to the semifinal round and decide the two opponents u and v should get, which are the strongest two, other than u and v, that u and v can defeat. Proceed in a similar manner for all the rounds, all the way to the first round. If at some point it is impossible to find an opponent for a player, you can conclude that u can’t win the tournament. The reason to choose the strongest opponent for a player is that the tree generated in this way is more relaxed, and easier to fill up later. A more rigorous explanation comes from the observation proved above.

However, a naive implementation of the above algorithm would have the time complexity of O(N²), which would be too slow for larger test cases. One can use advanced data structures like segment trees, interval trees (explained by misof here, in the write-up for the problem FloatingMedian), balanced binary trees (check tsjoker’s solution) or even a modified version of the union-find data structure, using only path compression (like in ploh’s solution), to achieve a complexity of O(N log N). It is possible to implement the algorithm in a linear complexity. For this, note that for a list of players, sorted in increasing order of their seeds, the opponents for the current round can be assigned in an increasing order of seeds as well. The C++ implementation is given below:

bool canWinLinear(int seed) {
    // initialize all elements of used to false here
    int P = 0;
    lst[P++] = seed;
    used[seed] = true;
    for (int i = 0; i < rounds; ++i, P <<= 1) {
        int pos = 0, opponent = 1;
        for (int j = 0; j < P; ++j) {
            // strongest[i] = the strongest opponent that i could beat
            opponent = max(opponent, strongest[lst[j]]);
            while (opponent < N && used[opponent]) opponent++;
            if (opponent >= N) return false;
            newLst[pos++] = opponent;
            used[opponent] = true;
        }
        // merge the lists lst and newLst and copy to lst here
    }
    return true;
}