Codeforces Round #336 Editorial

Правка en5, от ed1d1a8d, 2015-12-23 22:26:06

608A - Saitama Destroys Hotel

Author: ed1d1a8d

The minimum amount of time required is the maximum value of ti + fi and s, where t_i and f_i are the time and the floor of the passenger respectively.

The initial observation that should be made for this problem is that only the latest passenger on each floor matters. So, we can ignore all passengers that aren't the latest passenger on each floor.

Now, assume there is only a passenger on floor s. Call this passenger a. The time taken for this passenger is clearly ta + fa (the time taken to wait for the passenger summed to the time taken for the elevator to reach the bottom).

Now, add in one passenger on a floor lower than s. Call this new passenger b. There are 2 possibilities for this passenger. Either the elevator reaches the passenger's floor after the passenger's time of arrival or the elevator reaches the passenger's floor before the passenger's time of arrival. For the first case, no time is added to the solution, and the solution remains ta + fa. For the second case, the passenger on floor s doesn't matter, and the time taken is tb + fb for the new passenger.

The only thing left is to determine whether the elevator reaches the new passenger before ti of the new passenger. It does so if ta + (fa - fb) > tb. Clearly this is equivalent to whether ta + fa > tb + fb. Thus, the solution is max of max(ta + fa, tb + fb).

A similar line of reasoning can be applied to the rest of the passengers. Thus, the solution is the maximum value of ti + fi and s.

608B - Hamming Distance Sum

Author: ed1d1a8d

We are trying to find . Swapping the sums, we see that this is equivalent to .

Summing up the answer in the naive fashion will give an O(n2) solution. However, notice that we can actually find without going through each individual character. Rather, all we need is a frequency count of different characters. To obtain this frequency count, we can simply build prefix count arrays of all characters on b. Let's call this prefix count array F, where F[x][c] gives the number of occurrences of the character c in the prefix [0, x) of b. We can then write . as . This gives us a linear solution.

Time Complexity — O(|a| + |b|), Memory Complexity — O(|b|)

607A - Chain Reaction

Author: Chilli

We can solve this problem using dynamic programming. Let dp[x] be the minimum number of objects destroyed in the range [0, x] given that position x is unaffected by an explosion. We can compute dp[x] using the following recurrence:

Now, if we can place an object to the right of all objects with any power level, we can destroy some suffix of the (sorted list of) objects. The answer is thus the minimum number of objects destroyed given that we destroy some suffix of the objects first. This can be easily evaluated as

Time Complexity — O(max(ai)), Memory Complexity — O(max(ai))

607B - Zuma

Author: Amor727

We use dp on contiguous ranges to calculate the answer. Let D[i][j] denote the number of seconds it takes to collapse some range [i, j]. Let us work out a transition for this definition. Consider the left-most marble. This marble will either be destroyed individually or as part of a non-singular range. In the first case, we destroy the left-most marble and reduce to the subproblem [i + 1, j]. In the second case, notice that the left-most marble will match up with some marble to its right. We can iterate through every marble with the same color as the left-most (let k be the index of this matching marble) and reduce to two subproblems [i + 1, k - 1] and [k + 1, j]. We can reduce to the subproblem [i + 1, k - 1] because we can just remove marbles i and k with the last removal of [i + 1, k - 1]. We must also make a special case for when the first two elements in a range are equal and consider the subproblem [i + 2, j].

Here is a formalization of the dp:

Why is this dp correct? Notice that the recursive version of our dp will come across the optimal solution in its search. Moreover, every path in the recursive search tree corresponds to some valid sequence of deletions. Since our dp only searches across valid deletions and will at some point come across the optimal sequence of deletions, the answer it produces will be optimal.

Time Complexity — O(n3), Space Complexity — O(n2)

Теги codeforces, round, 336, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский ed1d1a8d 2015-12-26 09:53:59 131
en17 Английский ed1d1a8d 2015-12-26 09:22:59 381 Tiny change: 'xplosion. The minimum number of We can co' -
en16 Английский ed1d1a8d 2015-12-24 01:04:48 22 Tiny change: 'limits_{c=\texttt{a}}^{\texttt{z}} |a[j]-c|' -
en15 Английский ed1d1a8d 2015-12-24 01:02:41 4 Tiny change: 'le to get get both ' -> 'le to get both '
en14 Английский ed1d1a8d 2015-12-23 23:03:52 0 (published)
en13 Английский ed1d1a8d 2015-12-23 23:03:41 476 (saved to drafts)
en12 Английский ed1d1a8d 2015-12-23 22:49:21 80
en11 Английский ed1d1a8d 2015-12-23 22:34:11 33
en10 Английский ed1d1a8d 2015-12-23 22:32:45 14 Tiny change: ':** [user:tonynater,2015-12-2' -
en9 Английский ed1d1a8d 2015-12-23 22:30:39 0 (published)
en8 Английский ed1d1a8d 2015-12-23 22:30:07 1232
en7 Английский ed1d1a8d 2015-12-23 22:28:57 2544
en6 Английский ed1d1a8d 2015-12-23 22:27:10 2331
en5 Английский ed1d1a8d 2015-12-23 22:26:06 1843
en4 Английский ed1d1a8d 2015-12-23 22:23:34 907
en3 Английский ed1d1a8d 2015-12-23 22:22:14 1548
en2 Английский ed1d1a8d 2015-12-23 22:19:52 1617 Tiny change: '[problem:608A]' -
en1 Английский ed1d1a8d 2015-12-23 22:16:35 45 Initial revision (saved to drafts)