Problem Description: You have a dice with 6 faces, mapping to integer in 1..6. You roll the dice, and sum up them along the process. However, you will reset the sum to 0, when the sum has exceeded N. Find the expected number of rolls you h…

Problem Description: Happiness is a value defined upon a permutation, where it is given by the number of values with at least one value higher than itself that is adjacent. Given Q queries, output number of size n permutation with at least…

Problem Description: There are N items, the i'th item costs C[i], and we have a coupon that can reduce its price by D[i]. However, for every coupon i to be effective, coupon X[i] must be used, i.e., i'th item bought. You have B units of mo…

Problem Description: Solve f(x) = x * x * x + A * x * x + B * x + C, given A, B, and C. Output the solutions in increasing order.Constraints: -1e18 -1e9 It is guaranteed that there are exactly 3 distinct solutionsSolution: pekempey showed …

Problem Description: Given string S, find the minimum length of its running length encoding.Constraints: 1 ≤ len(S) ≤ 8000Solution: dp[i]: answer for S[0...i] dp[j] = min(dp[i] + cost(i, j) for i in 0...j) kmp[i]: maximum length of common …

Problem Description: Given N numbers as C[0...N], L, and H, find the number of values in range [L, H] that is multiple of exactly one value in C.Constraints: 1 ≤ N ≤ 10 1 ≤ C[i] ≤ 1e9 1 ≤ L ≤ H ≤ 1e9Solution: Solve for (L' = 1, H' = H) and…

Problem Description: You are given a directed weighted graph with N nodes and M edges. Q queries follow: OP = 1: Output the shortest path from node 1 to node V. OP = 2: Read C values, the C[i]'th edge should have its weight incremented by …

Problem Description: You are given an array A[] of N values. For each subset that has gcd greater than 1, its contribution is gcd * size_of_subset. Output the sum of contributions for every such subset, modulo 1e9 + 7.Constraints: 1 ≤ N ≤ …

Problem Description: You are given a string S. You are requested to split it into some substrings, and suppose you decompose it into k substring as , then must hold for each . You are interested in knowing the number of ways to decompose t…

Problem Description: Initially you are at coordinate (0, 0, 0). At each second, you have equal probability to move yourself with vector (-a, 0, 0), (a, 0, 0), (0, -b, 0), (0, b, 0), (0, 0, -c), (0, 0, c). Given t, a, b, c, d, e, and let p …

Problem Description: There is a set of N numbers. You would like to split the set into K non-empty subsets, so that the sum of contribution of each subset is minimal. Contribution of a subset can be computed as the absolute difference betw…

Problem Description: You are given an array A with length N. You have a weird "sorting" algorithm, the output is non-deterministic, but we know that it must be some arrangement of the input array, and contains no more than K inversions. Fi…

Problem Description: Given Q queries of X's, compute f(X), modulo 998244353.Constraints: 2≤n≤50 1≤q≤50 0≤ai,bi≤i - 1 0≤xi≤998244352Solution: Compute each query independently, the only variant is n (relevantly small), so we can apply DP.Cod…

Problem Description: 0/1 Knapsack problem. Test cases are generated at complete randomness.Constraints: 2 ≤ N ≤ 5000 v[i], w[i] is uniformly distributed in range [1, 1e12] 1 ≤ W ≤ 1e12 * NSolution: Branch and Bound. Referenced kimiyuki's b…

Problem Description: Initially, you are given an array of length N. Q operations follow: OP 1: Add C to every element in X..Y OP 2: Multiply by W on every element in X..Y OP 3: Output the sum of elements in X..Y, modulo 1e9 + 7Constraints:…

Problem Description: You are on an infinitely large grid. Initially you are at coordinate (0, 0). You would move towards of the four directions (URDL) each unit of time, and stop at the first integer coordinate that had not yet been visite…

Problem Description: You have a graph with N vertices, M edges. You are then given Q queries, each denoted by three indexes of nodes, A, B, and C. For every such query, you need to output whether it is possible to visit node A, B, and C, i…

Problem Description: Three colors of beads are available. Count the number of different circular necklace that could be formed. Two necklaces are identical iff after some rotation or flip, each position has the same color of bead.Constrain…

Problem Description: There are N switches and N technicians. Each technician has a list of valves, and if he were hired, he would flip the switch of each of them in his list. It is known that for any technician i, it is impossible to repla…

Problem Description: There are T standalone test cases in this problem. In the beginning, there are A units of bacteria. For any moment t with x units of bacteria, we know that moment t + 1 would have x**x units of bacteria. Given A, B, C,…

Problem Description: f(x) = 1, if x = 0 B ** f(x - 1), otherwise Given B, I, and N, find the last N digits of f(I).Constraints: Solution: We want to find . For any , we can observe that in , we can always find some such that . We will recu…

Problem Description: You have a for loop that looks like this: for (value_type i = A; i != B; i += C) ; , where value_type is K-bits unsigned integer data type. You want to know whether the loop will reach an end, and if it will, the numbe…

Problem Description: Given N, M, find the last non-zero digit in N! / (N - M)!.Constraints: 0 ≤ M ≤ N ≤ 2e7Solution: We can find a and k such that in O(lg x) time, given that e is 2 or 5 (because they are prime, we can apply Wilson's theor…