path: root/atcoder.md

- ~~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!~~