0w1

SRM 630 Div2

SRM

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. …

SRM 673 Div2

SRM

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>…

SRM 679 Div2

SRM

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 …

SRM 687 Div2

SRM

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>…

SRM 700 Div2

SRM

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>…

SRM 701 Div2

SRM

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…

SRM 702 Div2

SRM

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…

SRM 710 Div2

SRM

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…

POJ 3678 Katu Puzzle

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 ≤ …

POJ 3537 Crosses and Crosses

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…

POJ 1740 A New Stone Game

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…

Yuki 301 サイコロで確率問題 (1)

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…

HR Permutation Happiness

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…

CFR 815 C. Karen and Supermarket

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…

Yuki 550 夏休みの思い出(1)

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 …

CFR 825 F. String Compression

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 …

Yuki 546 オンリー・ワン

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…

CFR 843 D. Dynamic Shortest Path

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 …

CFR 428 D. Winter is here

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 ≤ …

Yuki 599 回文かい

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…

Yuki 612 Move on grid

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 …

Yuki 615 集合に分けよう

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…

Yuki 616 へんなソート

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…

Yuki 623 fudan no modulus to tigau

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…

Yuki 626 Randomized 01 Knapsack

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…

SOJ 86. 一維陣列區間加值區間乘值區間查詢總和

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:…

ARC 039 C - 幼稚園児高橋君

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…

ARC 039 D - 旅行会社高橋君

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…

POJ 1286 Necklace of Beads

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…

POJ 2345 Central heating

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…