Easy. DoubleLetterProblem Description: You are given a string S. Each time you can choose two consecutive letters that are identical, and remove them. After removal, both sides are connected, i.e., the result still remains to be a string. …
Easy. BearSongProblem Description: Given an array with N elements, count number of elements that appeared exactly once.Constraints: 1 ≤ N ≤ 50 1 ≤ A[i] ≤ 1000Solution: FunctionalCode: class BearSong { public: int countRareNotes(std::vector<int></int>…
Easy. ListeningSongsProblem Description: There are two playlists. A playlist consists of some songs, each described by the units of time it takes. You have listen to at least T songs from each playlist. Given that you have at most minutes …
Easy. Quorum:Problem Description: You are given N elements. Find the sum of the minimum K elements.Constraints: 1 ≤ K ≤ N ≤ 50Solution: Sort and greedy.Code: class Quorum { public: int count(std::vector<int> arr, int k) { std::sort(arr.begin(),</int>…
Easy. Xylophone:Code: class Xylophone { public: int countKeys(std::vector<int> keys) { std::set<int> bag; for (int v : keys) bag.emplace(v % 7); return bag.size(); } }; Medium. XMarksTheSpot:Problem Description: You are given a 2D board. There are t</int></int>…
Easy. SquareFreeString:Problem Description: Given a string, determine whether there is a substring that is squared (e.g., ww).Constraints: s.size ≤ 50Solution: O(s.size ** 4)Code: class SquareFreeString { public: std::string isSquareFree(s…
Easy. TestTaking:Problem Description: There are q false/true questions, in which you guessed g are true, and there are a that are really true. Output the maximum number of questions you might get correct.Constraints: 1 ≤ Q ≤ 50Solution: As…
Easy. MagicSubset:Problem Description: There are N stones with some weight. The first stone is magical, and if you choose it, each stone will have its weight multiplied by -1. Output the maximum weight sum you can obtain.Constraints: 1 ≤ N…
Problem Description: Given some constraints formed with two variables, and operator of OR, AND, or XOR, you are to find whether there exists a solution to satisfy all the constraints.Constraints: 1 ≤ N ≤ 1000 (number of variables) 1 ≤ M ≤ …
Problem Description: Two players take turn in playing a game on a 1 x N board. When it is a player's turn, he puts a marker on a grid that had no marker. If after a movement there are 3 consecutive markers on the board, the player who made…
Problem Description: There are N piles of stones, each with no more than 100 stones. Two players play this game, when it is one's turn, one should: Select a non-empty pile, remove at least one stone, then take arbitrary number of stones fr…
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…