Combothermal

ABC #132 Solutions

Jun 29th, 2019
761
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.10 KB | None | 0 0
  1. A: Count the number of times each letter appears in S. The answer is Yes if and only if there are exactly two letters that appear twice in S.
  2.  
  3. B: Simple brute force. Check each element except the first and the last to see if it satisfies the condition in the problem, and increment the answer if so.
  4.  
  5. C: Sort the data. The key observation is that a possible value for K must be greater than the N/2'th element in the array and less than or equal to the (N/2+1)'th element in the array. After sorting the data, therefore, the answer is simply data[N/2] - data[N/2 - 1], using zero-based indexing.
  6.  
  7. D: Given the input constraints, there may be a simpler solution to this problem using some form of DP. However, we will present a combinatorics-based solution with O(K) runtime.
  8.  
  9. Precompute the values of X! mod 10^9 + 7 for X from 0 to 4010 (as we'll see below, the largest value whose factorial we'll need to compute in our choose functions is about 4000). Then, we implement the choose function C(A, B) as A! * modInv(B!) * modInv((A-B)!), all modulo 10^9 + 7, where modInv(X) is the modulo inverse of X mod 10^9 + 7. We use modular inverses as an analogue to division so that this function computes the value of A choose B modulo 10^9 + 7.
  10.  
  11. We then iterate over each value of i. We need i groups of at least one blue ball, with every pair of groups separated by at least one red ball. We can also have some red balls to the left or the right of all groups of blue balls, but we don't need to have any red balls on the ends.
  12.  
  13. We start by assigning the required one blue ball to each of the i groups of blue balls and one red ball to each of the i-1 middle groups of red balls. Then, let B = K - i be the number of blue balls left to be assigned, and let R = N - K - i + 1 be the number of red balls left to be assigned. We now want to place B balls into i groups and R balls into i+1 groups. The key theorem we need to solve this problem is stars and bars, which tells us that we can place X objects into Y groups in (X+Y-1) choose (Y-1) different ways. We can thus compute the number of ways to place the remaining blue balls and the number of ways to place the remaining red balls and multiply them together to get our answer.
  14.  
  15. One special case to deal with is if R is less than zero, which will happen if we have too many groups of blue balls relative to the number of red balls. In this case, the answer is obviously zero.
  16.  
  17. E: Create a graph of 3*N vertices, where the first N vertices represent reaching a vertex before starting a ken-ken-pa, the second set of N vertices represent reaching a vertex after one of the three actions in a ken-ken-pa, and the third set of N vertices represent reaching a vertex after two actions in a ken-ken-pa. An edge from A to B in our original graph is then equivalent to three edges: one from A to B+N, one from A+N to B+2N, and one from A+2N to B.
  18.  
  19. The advantage of this approach is that once we read in the data, the solution itself is very easy to implement, as we now simply want to find one-third the distance from S to T (where the distance between two nodes is the number of edges we must traverse to reach one from the other). We can compute this using a standard BFS algorithm, which can also tell us whether T can be reached from S at all.
  20.  
  21. F: The basic idea is to use DP and square root decomposition. Let root be equal to ceil(sqrt(N)). We build two DP tables: a "small table", which stores the number of ways, at each possible number of steps, to create a valid sequence ending in each number up to root, and a "large table", which stores the number of ways, at each possible number of steps and for each possible X less than or equal to root, to create a sequence ending in a number Y such that X*Y <= N but X*(Y+1) > N. Obviously, the answer is the sum of the entries in both DP tables corresponding to K steps.
  22.  
  23. We now consider the transitions. Any entry X in the small table can transition to almost any other entry in the small table (we have to be a little careful because root * root may be slightly greater than N) and to any entry in the large table greater than or equal to X. Any entry X in the large table cannot transition to another entry in the large table but can transition to any entry less than or equal to X in the small table. We are thus essentially faced with operations involving adding to all values less than some X in the small table or to all values greater than some X in the large table, and we can address these using prefix and suffix sums. We also precompute the number of possible values Y that satisfy X*Y <= N but X*(Y+1) > N to help with our transitions to the large table. Note that we have to be a little careful to avoid counting the same values in both the small and large table.
  24.  
  25. Here are the links to my submissions:
  26. A: https://atcoder.jp/contests/abc132/submissions/6159161
  27. B: https://atcoder.jp/contests/abc132/submissions/6160180
  28. C: https://atcoder.jp/contests/abc132/submissions/6161217
  29. D: https://atcoder.jp/contests/abc132/submissions/6169475
  30. E: https://atcoder.jp/contests/abc132/submissions/6168835
  31. F: https://atcoder.jp/contests/abc132/submissions/6175373
Add Comment
Please, Sign In to add comment