- ~~arc103_b: Use powers of 2, clever way to show why it works~~ - arc102_c: Consider each t seperately, then iterate over number of elements chosen from pairs summing to t, using math - arc095_c: Think through problem conditions carefully. Don't try all 12! permutations but 11!! paired permutations - arc096_d: Caterpillar graph - arc081_fd: Find invariant, parity, look at 2x2 squares - arc075_d*: Math - ~~arc068_c: Observation: only put intervals in after d > length~~ - ~~arc088_c: Greedily pick end elements, use ordered set data structure~~ - arc080_c: D&C, use RMQ to speed up runtime for unbalanced splits - arc091_d*: Nimbers - arc082_d: Looks like DS but actually sweep through timestamps and update function --- - arc079_d: *It is well-known that in this type of graph, there is exactly one cycle in the graph, and from each vertex on the cycle a tree may "grow".* - agc022_c: Looks like num theory but actually graph - agc024_d: Consider diameter of graph - agc032_c: Lots of cases - ~~agc036_c: If M < N, then only M elements can be odd~~ - agc015_d: Look at first different bit, then look at all elements that don't have it set and all that do - agc019_c*: Math, cases, careful analysis - agc035_c: Make sure output format is correct, tricky case when N is even, watch out for bitwise operator precedence --- - hitachi2020_c: Trees are bipartite graphs - yahoo_procon2019_qual_d: Straightforward - m_solutions2019_c: Math - ~~exawizards2019_d: Consider decreasing subsequence of permutation~~ - nikkei2019_2_qual_c: Consider unusual N-2 condition - yahoo_procon2019_qual_f: Tricky observation, then straightforward DP - ~~caddi2018_e: Looks like greedy, a little bit more complicated~~ - ~~tenka1_2018_e: Almost identical to a USACO problem~~ - diverta2019_e: Look at prefix XORs, tricky DP which looks like O(N^2) but can be optimized to O(N) because it visits a lot of redundant states - tokiomarine2020_d: SQRT / MITM - exawizards2019_e: Instead of computing the whole DP table, consider only the edges because the answers of the middle are 1/2 while the answers for the edges are 0 and 1 - ~~apc001_e: Simple tree DP, root the tree at a node with more than two verticies~~ - tenka1_2019_d: Constant sum, so greatest side less than sum/2, write things down - m_solutions2019_e: Adjust common difference to be 1, which is an easy case - nikkei2019_2_qual_e: Use math to derive inequality when the partition is not possible - ~~codefestival_2016_qualc_d: Every pair of consecutive columns is independent, so DP on each pair, then add everything up~~ - code_festival_2017_qualc_d: Hashing, keep track of first occurrence of hash - mujin_pc_2017_b: Constructive algorithm, complete one row first - nikkei2019_qual_e: Sort edges by weight, kind of like MST - ddcc2020_qual_e: If first half is one color, then second half is other. Then binary search where it changes - diverta2019_2_e: Consider the case when D = 1 first, then generalize - codefestival_2016_qualB_e: Make sure you read the problem correctly, solution is pretty straightforward - code_festival_2017_quala_d: 45 degree rotation transformation - codefestival_2016_final_f: SCCs, keep track of size of SCC containing vertex 1 - hitachi2020_d: First use math to get a greedy sorting, then note that only O(logT) stores used at most with b > 0, so DP is actually O(NlogT) - acl1_e: Read problem carefully, math - dwacon6th_prelims_d*: Looks a bit like graph but then you think it's not, but then it actually turns out to be graph --- - abc177_f: Try all possible starting points, but use segment tree to speed it up - abc163_e: Greedy observation: Add elements in decreasing order to the ends, then easy DP - abc158_f: Use segment tree to calculate range of robots that robot i activates, then DP - abc145_f: DP, at least two different ways to formulate it - ~~abc139_f: First pick a direction, then pick engines, lots of corner cases, or look at subarrays of angle up to pi~~ - abc140_f: Think of it as a binary tree, assigning the multiset values to the leaves, then greedy with connected components. - ~~abc132_f: SQRT, then DP~~ - abc138_f: Look at most significant bit, can show X, Y have the same MSB, then DP on other bits with no carry - abc130_f: Binary search when x, y are decreasing, increasing, then the answer is at an endpoint - abc163_f: Complementary counting - ~~abc133_f: Euler tour~~ - abc137_f: Fermat's Little Theorem, consider 1−(x−j)^(p−1), which is only 1 when x = j - abc149_f: Count number of ways for each vertex to have two or more subtrees painted black - ~~abc144_f: Easy O(M^2) DP, for each node, pick optimal edge to block, read problem carefully for small details!~~ - abc147_f: Observation - show this is equivalent to counting unique S, then observe that for a fixed k, the sum of the i are in a range - abc156_f: Math, consider cases when condition is equal or greater - abc135_f: String matching, consider infinite repitition of s - abc143_f: Find formula for max K for each number of operations - abc141_f: XOR basis - abc180_f: DP, should be straightforward, use degree at most 2 condition - abc172_f: N<=300 does not mean DP, use a+b=(a⊕b)+2×(a&b) - abc136_f: For each point, count how many rectangles it is in using BIT - abc155_f*: Consider parity between bombs i and i+1, then consider graph where l_i and r_i are connected - arc092_b: Consider each bit separately, common strategy for XOR problems - abc168_f: Look for unusual conditions - abc160_f: Consider simpler case first of computing for one k, then reuse DP between k - ~~abc127_f: Can use either ordered_set or two sets to find median, with two sets, move elements over until sets are same size~~ - abc127_e: Look at each pair seperately - abc128_f: Don't iterate through A or B, but rather A-B - abc150_f: Either consider each bit seperately, or show that a_{i+k}⊕a_{i+1+k} = b_i⊕b_{i+1} which is similar to + instead of ⊕ - arc104_c: Bounds tell you it's DP - arc104_d*: Looks like simple DP but actually trickier, to count sets of average m, think of it as a lever with fulcrum at m and up to K weights at each of 1, 2, ... N - ~~agc048_c: Consider distance between consecutive penguins, each difference in the B array corresponds to an interval in the A array~~ - m_solutions2020_f: Lots of cases, can use symmetry, rotation, to shorten implementation - soundhound2018_summer_qual_e: Set a leaf to x, then propogate it through the graph, not binary/tenary search - ~~aising2020_e: Greedy, pick best camel for each position~~ - tenka1_2019_d: *The necessary and sufficient condition for the triangle to existis the largest ofR; G; Bbeing less thanS=2.* - m_solutions2020_e: For each area, don't try adding both the x and y railroads - panasonic2020_e: Exhaustive search - arc107_d: Consider decompositions using 1 and ones without using 1 and derive formula - abc182_f: N <= 50 actually has no significance, an O(N) DP solution exists - ~~arc110_d: Express using generating functions, write out the infinite terms~~ - arc109_d: Consider moving the centroid around to derive a formula - abc181_f: Obviously binary search, construct a graph - agc050_b: DP, find correct state and transitions - agc049_c: Consider what input looks like when answer is 0 - agc050_c: Formulate the optimal strategy so it is easy to DP with it - ~~agc049_d: First use structure of convex sequence and fix index of minimum, then a bit like knapsack DP where transitions correspond to adding 1, 2, 3 ... to a suffix or prefix of the sequence, so it's adding 1, 3, 6, ... to the sum, reuse DP between different indexes of the minimum~~ - agc050_d: Try DP, can choose a large state because N is small - arc107_e: Do some test cases to find a pattern for large N - ~~arc110_f: Difficult constructive algorithm, do some test cases to find a construction that works~~ - arc105_e: Consider what the graph looks like at the end of the game, then look at parity to see who wins - arc108_f: First consider the diameter which is pretty obvious, then look at the case where it is colored two different colors; then you only have to consider distances to the two endpoints - arc111_d: First direct the edges that are easy to direct, basically c_u < c_v, so the edge must go from v to u; then the problem reduces down to creating strongly connected components, which you can do using a DFS tree - arc111_e: Answer is basically the sum of some floors - acl_f*: https://codeforces.com/blog/entry/83071 - abc189_f: Write out the equations and use some math to solve them - abc191_f: Use property that only divisors of elements can be answers, so for each element, try to gcd it with its divisors - arc112_d: Build a new graph and the answer is just to connect all the rows or all the columns - ~~agc052_b: It's a tree so consider paths and/or subtrees, also try rooting the tree, then add an imanginary node to clean things up, and as always do a lot of test cases~~ - ~~arc114_c: Obviously DP, but a 2D DP makes things complicated because you have to keep track of a large state, so split it up for each number from 1 to M so you only have to track if the number appeared or not~~ - ~~arc086_c: Looks like DP and use probabilities to simplify transitions, optimize the 2D DP by greedily merging vectors small-to-large to reuse values~~ - ~~agc037_e: Do some small test cases to find the greedy approach, lots of corner cases so make lots of test cases for that too~~ - arc073_d: First write out 2D DP which is pretty obvious, then consider the transition very carefully and optimize it with a segment tree - ~~arc112_e: Again write out a DP, this time a 3D DP, then figure out how to remove one of the parameters to get a 2D DP~~ - arc106_f: Find a formula, you can designate one hole in each part as special, then connect non-special holes with special holes - arc115_d: First solve the easy case where it is a tree with math, then you can use some more math to generalize for a connected graph, don't be limited into only thinking about DP and those kinds of algorithms - ~~arc115_e: DP and data structures, can be solved with cartesian trees but solving with segment trees is a lot harder~~ - abc196_f: Write out the mathematical equation and manipulate it so it's an FFT convolution - ~~arc116_e: Make sure you read the problem very carefully, especially if it seems too easy or you're stuck!~~ - ~~arc117_d: Immediately reminds us of centroids/diameters, but don't get confused because this a diameters problem, make sure you read the conditions in the problem carefully as well~~ - ~~arc123_d: Do some test cases and there's an obvious greedy strategy; However, reading it closely, it's actually asking for the absolute value, so we should try all of the shifts; You can binary search or two-pointers, but the easiest way is to put all the shifts into an array and sort them, then go through the one by one~~ - ~~arc129_d: Don't forget 0ll vs 0!~~