summaryrefslogtreecommitdiff
path: root/codeforces.md
blob: 210879fe3b0b326788d4f25e442295c0864b4904 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
- ~~1420C2: Pick all local mins and maxes, greedy observation~~

- 1408D: Coordinates < 1e6, so try all moves up to 1e6

- 1370D: Minimize the maximum! Binary search the answer

- ~~1359D: Use the fact that max value is only 30~~

- 1363E: Greedy, choose smallest node on path up to root

- 1384B2: Consider all positions that are safe no matter the tide

- 1359E: Easy to see from the sample test case

- 1365F: Find an invariant

- 1168C: Think about properties of the original problem, don't always try to simplfy it in one direction

- 1424M: Straightforward, build graph, toposort

- 1422D: Too many edges in graph, so only keep ones between consecutive edges, then simple shortest path

- ~~1158A: Casework, watch out for long long~~

- ~~1158B: Do a lot of small cases~~

- ~~1158C: D&C~~

- ~~1149A: Easy to see from sample cases~~

- ~~1149B: DP, but reuse states between transitions~~

- 1110E: Look at differences

- 1117E: Basically you're asking a unique triple of characters for every position and you can just see where they map to

- 1039A: Do lots of test cases

- 936C: Find strategy that works by doing a lot of test cases

- 1270E: Parity

- 1196F: Since K<=400, many different methods such as only considering K smallest edges, or doing shortest path from each node but stopping after finding closest K

- 925C: Consider each bit at a time

- 1098B: Only a limited number of possible answer tables, pick one that works best for each row

- 1231E: Complete search each substring of t

- 906B: Many methods, one is to "shift each even row cyclically on two symbols in the right, and then shift each even column cyclically on one symbol upwards", do lots of cases

- 1437E: Consider case where k=0, look at array b[i]=a[i]−i, LIS

- ~~1370E: Can remove indexes where s[i]=t[i], then similar to balanced parenthesis~~

- 1423J: Generating functions, answer is (n/2-n/4+1)(n/4+1)

- 1358E: Observe that if k is a solution, so is 2k, so there exists k>n/2, let s[i] be prefix sums of a, then s is also prefix sums of s[1], x-a[1], x-a[2], ... x-a[n]-k

- 1166E: Consider what happens when going from day i to i+1

- 1003E: Several ways to build the tree, one way is to attach each new vertex to the "lowest free vertex"

- 1004D: BFS from cell with 0, when you run out of a number, that means you have hit a wall

- 1107G: Use fact that there are only n different (d[i]-d[i-1])^2 or D&C

- 962E: Greedy

- 923D: Note that B and C are interchangable, then some casework

- 1276C: If each element occurs less than or equal to a times in an array, then they can form a a*b rectangle

- 1296F: Set all edges on the path to at least g, then check for contradictions

- 1285E: Sweep line

- 1148E: Sequences of differences are like a balanced parenthesis string

- 1157G: Observation that array is basically determined by first row

- 1333D: Store indexes of matches to speed up algorithm

- 1282D: First find length, get rid of one query by noting that last character is already determined by everything before it

- 802H: Find a construction that works for large primes, many possible approaches

- 773C: To check a single m, use greedy, then note that only m and m+1 can be solutions, so binary search

- 772C: Represent it as a graph

- ~~804C: Use unusal condition to prove greedy algorithm, watch out for bounds, lots of corner cases such as n=1~~

- 723E: Euler cycle, look at each connected component separately

- 901B: For integers, GCD worst case is Fibonacci numbers, so use similar strategy for polynomials, choosing signs so that the coefficients are in the right range

- 713B: Binary search, observation to find the first rectangle with 4 binary searches, then second with an addition 4 binary searches

- 1034B: Bipartite graph matching, casework, use smaller cases to solve large boards

- 1427E: GCD, write a number coprime to x

- 858F: Do a DFS, greedy construction

- 815B: Do some examples to find the pattern

- ~~774H: Consider longest contiguous strings in decreasing order~~

- 715B: Slow, Dijkstra-like algorithm, use binary search to speed up choosing edge weights

- 784F: Answer is always 1, since we can root the tree somewhere so that its subtrees each have less than k teams

- 593C: Magic function (1-abs(x)) + abs(1-abs(x))

- 453C: Update path during DFS

- 549A: Subtract N-i from a[i], then solution is easy to see

- 550E: Casework, show that only two cases lead to no solution

- 354E: Digit DP, current digit, carry

- 670F: First find length, then construct strings for various cases

- 610D: Obvious sweep line

- 612E: Look at permutation graph

- ~~584E: Greedy, consider positions from 1 to n~~

- 570D: Convert tree to a segment, then two binary searches to get nodes at a height, represent condition as a bitmask

- 432E: Greedy construction works

- 350E: Put in all edges, then take some out

- ~~1142A: Brute force, make sure all cases are checked~~

- 1142B: Array can be transformed into a graph, then to get answers, go from right to left and keep track of minimum

- 1142C: Transform (x, y) to (x, y-x^2), turns parabolas into lines, then convex hull

- 323B: Do some examples for small n

- 888G: Modify MST algorithm by using a trie

- 573C: Decompose tree into main line, y-letters, and lines

- 272E: First color everything one color, then fix wrong vertices

- 271E: Show that (x, y) can be transformed to (1, 1+k*d), where d is the maximal odd divisor of y-x

- 134C: Greedy, priority queue

- ~~549B: Consider when all guesses are nonzero, then no one should go, so for any zero, that person should go, and recurse~~

- 487C: Look at small cases, 4 is special

- 424D: Classic subarrays strategy

- 277B: Put m points on a convex function, and put n-m points on a concave function

- 460D: Casework, all cases except k=3 are easy, find a construction for k=3

- ~~306D: Use a very large side length and increase it by a very small amount, add a little bit to the last vertex to make everything work out~~

- 196C: Sort by angle

- 42C: Show that greedy works, watch out for corner cases

- 42D: *AB+CD=AC+BD should hold for every quadruple of distinct vertices A, B, C, D*

- 86B: Color the plane nine colors, then use that to determine the color of each figure

- 97B: Sort, then D&C, make sure points on two halves have a point inside their rectangle

- ~~633E: Use RMQ and binary search to compute potential for each l or something like Kadane's algorithm (harder part), then sort potentials and use math to get the answer, can do it without using nCr libraries, see code (easy part)~~

- 633F: Tricky tree DP

- 1152E: Create a graph out of the array, then find an Euler tour

- ~~1446A: Observation that if there is no item with weight between W/2 and W, then when we add items in, it should at some point have a sum between W/2 and W~~

- ~~1446B: DP, set all states to zero initially so you can start a substring anywhere~~

- ~~1446C: clz(0) gives runtime error~~

- ~~1446D: Simple idea, but tricky details~~

- 755E: Try constructing small K

- 621D: Basically a math problem, lots of corner cases

- ~~733E: Do the sample cases, tricky indices, use segment tree to speed it up~~

- 1163E: Iterate through every x, XOR basis since every element of the permutation should be an XOR of a subset of S

- 1374F: First consider a permutation and look for an invariant - the number of inversions, then use greedy algorithm, similar to bubble sort

- 835E: Interactive, look at parity then binary search

- 1174F: D&C, use HLD or centroid decomp for path queries

- 1182D: Check a limited number of important nodes

- ~~1438D: First make pairs, then XOR first element with each pair to make them all the first element~~

- 26E: Consider small N and W, split into cases

- 1428E: Greedy, consider cuts one by one, using heap to choose the best one

- 1272F: Simple DP, i, j, balance

- 141E: MST so adapt a MST algorithm, add all S edges, then Kruskal's to add M edges

- 1098C: Sum is n+(sum of paths from each node to root), greedily construct array of number of vertices at each level

- 1385F: Greedy strategy, hard implementation

- 1385G: Convert to a graph problem, then greedily solve each CC

- 1089M: Do some cases to find a construction that works

- 209C: Greedy, DFS

- ~~911F: Look at the diameter, do some cases~~

- 922F: Consider primes greater than n/2 and the divisibility graph

- ~~525D: Look at 2x2 squares and fix ones that have 3 empty squares, instead of doing complicated DS stuff~~

- 1028E: We have a1=b1+x1a2, so substitute continuously and solve for xi, then fix some ai=bi

- ~~798D: Find a solution that uses exactly n/2+1 elements, sort and look at pairs~~

- ~~297C: First consider 0,1,..n, then split it into 3 intervals~~

- 1137D: Tortoise and hare like algorithm, number of friends is misleading, write and solve equations

- 329C: Try random permutations, because there is a large chance that it works

- 1054E: Find algorithm to move to the state with all ones in a square and all zeros in a square with 2s moves

- ~~883J: Demolish buildings as late as possible, then apply priority queue trick~~

- 534E: Keep track of counts from each starting position, and transition from i to i+1 in constant time

- 417E: Find solution for 1D case, then cartesian product for 2D case

- 359E: Do some test cases to see that you first want to turn lights on so you can move around, then DFS to turn lights off

- 193C: Write it as a set of equations in 16 variables for each of the possible cases, then reduce number of variables by 2 because aaaa and bbbb are useless and divide by two for symmetry. Then solve with Gaussian elimination

- 1452E: Look at centers of intervals and sort. The first author is optimal for a prefix, and the second for a suffix. Or use segment tree with slower complexity. Or slow solution with pragmas.

- ~~1415E: Consider optimal perm for fixed partition or optimal partition for fixed perm, then split into cases of negative or positive, watch out for unsigned sizes and overflow~~

- 1451E1: Use a+b = (a⊕b) + 2(a&b), then pick three i, j, k and query their XORs and ANDs to get a system of three equations, then solve to get their values, use remaining queries to get other values, and use observation that aj⊕ak = (ai⊕aj) ⊕ (ai⊕ak) to reduce XOR queries by 1

- 1451E2: Find XOR of first element with everything else, then use property that all elements lie in range [0, n) to optimize the number of queries with casework

- 1453E: Can either binary search and simulate, or do some test cases to see that the path looks like an preorder traversal, and sort the children of each vertex to get the optimal preorder traversal

- 1220E: Break up graph into cycles that contain s, and pick the best subtree of the cycles

- 1234F: Reduce problem to finding pair of bitmasks that do not intersect and have highest combined number of ones, use bitmask DP

- 1208E: Obvious DS problem, use sets

- 1184B2: First build bipartite graph of bases and spaceships, then run maximum matching when building either 0 or s dummy bases 

- 1181D: Sort all queries, then go up row by row and use ordered_set to get ith element in the current row

- 1252L: Hard part is N road proposals, so one road is not constructed; So, solve easier version of N-1 road proposals first with matching on a bipartite graph; Now break up original graph into a cycle and everything outside the cycle, so first run max flow on the second set, then the first.

- 1443E: Use condition that permutation number at most 1e10, so only last 15 elements can change

- 1182E: Deal with the weird c^{2x-6} by writing the recurrence in terms of c^x f(x)

- ~~1190C: Do some test cases to find the optimal strategy~~

- 1450C1: Look at each square's (i+j) % 3 and try all three different ways

- 1450C2: Similar idea, split into six cases and pick two to flip

- 1450F: First cut array into segments, then make additional cuts so that a solution is possible

- 1455E: Approach from reverse direction: assume we have an optimal solution, then move the square around and show that in at least one direction we cannot increase the distance, so an optimal solution shares one vertex with an existing point and has side length equal to one of the x or y distances between a pair of the original points

- 1450E: Bipartite graph but don't look at cycles since that creates a condition that is harder than the orignial problem; Non-obvious way of writing the condition as inequalities, which then is obvious to use shortest paths

- 1461E: Use property that one of the bounds is only 1e6, look at x different residues mod x

- 1444C: Use properties of bipartite graphs and use parity to simplify stuff

- ~~1442C: Try to adapt standard shortest paths algorithm for this problem, split into the case where you can reach it under 18 steps and over 18 steps since a different thing accounts for most of the distance in these two cases~~

- ~~1436E: Can't binary search because answers are not contiguous, but you can try every answer quickly; This requires querying the MEX of a subarray, which you can use a segment tree or MO's algorithm, but remember that you don't have to construct the segment tree beforehand and do queries but actually use a normal segment tree and modify it while doing queries~~

- ~~1428F: Think through it very clearly before starting to code, be careful when doing too much casework or too many steps~~

- 1423H: Use segment tree to solve dynamic connectivity offline, then traverse segment tree

- 868F: The slow DP can be optimized using divide and conquer since it is monotonic

- 1043F: Observe that the solution will contain at most 7 elements, so DP for each possible number of elements

- 1463E: Compress chains to super-nodes, then toposort, implementation may be a little hard

- 1408E: Looks like a hypergraph, which can be represented as a bipartite graph; Then note that problem becomes removing cycles from the graph, which is equivalent as turning it into a tree, so use MST

- ~~1468M: Square root idea, separate sets into small sets and large ones, then use special properties of them, make sure to clear stuff between test cases~~

- ~~1473E: 3 parameters, so make 2 of them booleans; then note that you don't have to remember a lot of information because the best solution has certain properties~~

- 1467E: First root the tree anywhere and use the fact that doing at most two subtree queries on this tree will give you subtree info about the tree rooted anywhere else

- 1469E: Each substring forbids one possible answer string, then set first few characters to 0 so that there are O(n) candidate answer strings, so now we can loop through all length k substrings and mark the candidate answer strings that are forbidden

- 1470C: 1000 queries, so do sqrt decomposition to get the answer

- 1469F: Represent it as an array of counts instead of a tree, note that it is optimal to attach chains at the middle vertex and to take the longest chains, prove that greedy algorithm can give the best answer

- ~~1474E: Do some small n to find the pattern, need to be very clear about the pattern when implementing, can use small n as well to debug~~

- 1062E: Remove the node on the very left or right and compute LCA of remaining nodes by finding the LCA of the leftmost and rightmost remaining nodes, implementation takes a while

- ~~1479A: Straightforward binary search with some casework~~

- ~~1479B1: Use a clever greedy strategy since a simple one doesn't work~~

- ~~1479B2: Similar to B1~~

- ~~1479C: Start with simple cases such as (1, 2^k) and figure out a good way to construct this with few nodes, then extend it to other cases~~

- ~~1485F: First find slow 2D DP, then optimize transitions ~~

- 1476E: Create a graph and connect each node to nodes that must go after, then toposort

- 1481E: Find a good DP state, then transition based on if the current index is the leftmost index of a color or not

- 1485E: Rephrase problem as finding chains of edges and picking the best partners greedily, which is easy to do with DP

- 1485D: Use property that lcm of all integers from 1 to 16 is less than 1e6, then find a clever construction based on this

- ~~1477A: Easy observation that we can take the gcd of all differences~~

- ~~1477B: Read the problem carefully and look at it backwards so the condition is easier to use~~

- 1477C: Pick the furthest point every time or use the property that every triangle contains at most one obtuse angle, so cycle around the points so that no triangle has an obtuse angle

- ~~1470D: Do a lot of test cases including the sample cases, there's a simple greedy algorithm~~

- 1474D: First consider the problem without the swapping condition, and notice the easy solution, then to solve the original problem, you can scan through the array and use a data structure like a set to keep track of all the posibilities; or you can use prefix sums like the solution which is easier to implement

- ~~1499E: DP, remember to subtract away the cases where one substring is empty, easy to derive formula for that by looking at some small cases~~

- ~~1499F: Obviously DP, so find a good 2D state; the transition is pretty slow, so optimize the merge so that it doesn't always take the worst case time complexity~~

- 1479D: Easy 3D DP, but optimize it by instead of storing the IQ as part of the state, process the edges in order of IQ so the state is 2D

- ~~1495D: First fix x and y, then find a way to count the number of trees with DP by looking at each layer of the tree~~

- ~~1494D: Many different possible approaches, a top-down D&C works well here, don't forget to try top-down if bottom-up doesn't work well~~

- 1497E2: First look at prime factorizations and note that we can define a bitmask so that two numbers multiply to a perfect square if their bitmasks are the same; then optimize the O(n^2) DP by precomputing the optimal extension using two pointers

- 1495C: Find a nice construction and do lots of examples

- 1494E: Do some examples to find the patterns to construct a solution

- ~~1483D: Instead of trying every combination of edge and query, use a shortest path algorithm to do all of them at the same time by setting queries to negative edges~~

- 1492E: One clever way to get a O(mn) solution is to try making 0, 1, 2 changes to the first array, and this will bound the time complexity of the solution with a high constant factor; also, a randomized algorithm can work too since the test cases are not very strong

- ~~1486F: Root the tree first, then use math to count the number of intersections in the various cases~~

- ~~1493F: The key idea is to use DP although it is an interactive problem, and it's possible to solve it with randomization as well~~

- ~~1493E: First solve easier versions of the problem, and do lots of test cases~~

- ~~1437F: Obviously we want to sort the array first, then do DP or use math since the sequence of happy fisherman is increasing~~

- ~~1420E: Find a transformation so the problem is easier to tackle, then carefully look at the state and try to find something that multiple states share to reduce the number of states from something exponential to polynomial~~

- 1439C: The key observation is that the second type of query is only over log(N) different segments, you can use segment tree binary search to find them, and the first query can be answered using lazy propogation, mostly implementation

- ~~1430F: Make the number of bullets the value since it has a large range and use number of reloads as the state instead of the reverse which is more obvious but a lot slower~~

- ~~1400G: The property that the maximum number of edges is 20 really stands out, and you can also get that all connected components are of size at most 20 so you can do bitmask DP on them~~

- ~~1389F: Two different approaches, a greedy method that is short but hard to come up with, and a DP approach that uses segment trees since the transitions are range adds and queries~~

- ~~1500C: Observe that doing extra moves doesn't have a negative impact, also you can think about the problem from the reverse direction~~

- ~~1372E: Do lots of test cases to find a greedy strategy, then use a D&C like DP to try all these cases~~

- ~~1394D: First you can orient the obvious edges that go from a lower node to a higher node, then tree DP on the remaining ones~~

- 1461F: Most of the cases are trivial to solve, except for the most general case which is possible to do with DP using the obvious state but transistions are a bit hard to come up with

- 1312G: Hard part is coming up with the DP transition, but it turns out you can use a segment tree on the path from the root to the current vertex

- ~~1503C: First we can approach the simpler problem of figuring out if a solution even exists which is not too hard to do, but you need to also use the condition that the cards are in the range 1 to 2N; The main idea now is that each number {1...N} is paired with a number {N+1...2N}, and the smart idea is to to look at all the cards in sorted order by the smaller number, noting that the problem becomes decomposing this array into two decreasing subarrays~~

- ~~1458A: Write a lot of test cases to find the trick~~

- ~~1458B: Obviously DP, so find a state that works and implement it!~~

- ~~1458C: You can think of the board as a set of points in a 3D space, then see what the transitions do those points~~

- ~~1464A: Do some test cases and it's pretty obvious what the solution should be~~

- ~~1464B: DP is too slow, so make a greedy observation~~

- ~~1464C: First try small N and note a pattern, so the problem reduces to finding a sign assignment for the first N-2 numbers, which is not too hard to do with a greedy algorithm~~

- ~~1442A: Pretty easy after trying a few test cases to find the greedy strategy~~

- ~~1442B: Simulate it with some test cases and the solution is pretty clear~~

- ~~1442D: Obvious but slow DP that doesn't use the property that the arrays are sorted, but this is quite tricky to use; One way is to show that the optimal solution must only have one array which partially uses a prefix and all the others either use all or nothing by contradiction; So the problem becomes iterating over which array this is and doing knapsack on the remaining ones which is still too slow but can be optimized with a D&C idea similar to a segment tree; Very hard to come up on your own unless you've seen it before; Also unlike most DP problems you're transitioning over the current row, not from one row to the next so you have to be careful about that~~

- ~~1498F: It looks like a Nim game so we want to adapt the standard algorithm; We want to focus on what each move does to the entire tree instead of focusing on individual verticies; If one person tries to use a mirroring strategy, you can see that it makes the even depth nodes useless, which is the important observation; This also ensures that moving a node to an even depth basically makes it useless so you can now focus on the odd depth nodes as a Nim game, and this is easy to generalize to K>1 and multiple roots~~

- ~~1513F: It's not too hard to come up with an approach using a 2D segment tree, but it's too slow and you should instead think of it as an interval problem which is a lot easier to optimize to use a regular segment tree~~

- ~~1508A: Unusual condition of 150% greater length is something to investigate, since you don't need to find the shortest possible string~~

- ~~1508B: Work out the answer for some small N and there's an obvious pattern~~

- ~~1508C: Don't be afraid of XOR and it's not too hard to reduce it to a pure graph problem; Since there are so many edges, focus instead on unused vertices instead and then you can apply a standard MST algorithm~~

- ~~1120C: Don't implement algorithms that are most likely going to be too slow, like using sets and hashing in this problem! KMP does work with small modifications and is much faster!~~

- ~~1120A: Hard implementation, first problem may not always be the easiest~~

- ~~1513E: Do a lot of examples and use some math, try to implement it quickly and accurately~~

- ~~1120D: One way is to do it with tree DP, but a much more cooler method is to do an Euler tour and construct a new graph where the nodes are the leaves and the edges are between the last leaf not covered by the current node and the last leaf covered by it, which you might think of doing since the weights are on the nodes but we want them on the edges; Now it just becomes a simple MST proble~~

- ~~1103A: Just find a way that works~~

- ~~1103B: Easy binary search solution, but just be careful with implementation of binary search and the very tight bound on number of questions~~

- ~~1103C: A ton of weird conditions that are hard to use; You can start by immediately throwing out the path case since that's super easy to solve and you can assume it doesn't hold, then make a ton of observations~~

- ~~1201D: Lots of special cases, try to write very clean code and reuse functions so it doesn't get too complicated~~

- ~~1241D: Idea is obvious, implementation may be a little bit tricky to get the right indices but it's not too bad~~

- ~~1086A: Simple idea, find an easy-to-code implementation~~

- ~~1086B: Do the sample cases!~~

- ~~1086C: Tricky implementation with lots of casework, so start immediately and try to do it fast~~

- 1086D: Obviously a segment tree problem, you just have to formulate it in a way that can be solved with a segment tree, then do some casework

- ~~1348F: Make sure you understand the question well, it's pretty easy to get one arrangement using a greedy algorithm, then think through all the cases on how you could generate a second arrangement; maybe try lots of examples~~

- ~~1147D: It might be possible to solve this with a complete search implementation, but there's a much smarter graph solution since the use of m instead of n could be a hint~~

- ~~1166F: First think of a way to solve it in O(M) time per query, then try to speed it up by using sets and union-find, which should be pretty obvious~~

- ~~1067A: Not too hard to solve with DP, so get started thinking it through clearly immediately and start implementing it~~

- ~~1067B: An easy problem, just make sure you get the implementation right!~~

- 1517E: Be careful when reducing down problems and make sure you keep important parts of the problem statement; For example, you can't just consider if only one of the letters is greater than half the sum since then you lose the condition about the other letter; do lots of test case!

- ~~1067C: Do a lot of cases to try to find a construction that works~~

- 1516E: Start by thinking about the problem backwards, then think about how we can count this, then consider overcounting

- ~~1515A: Easy idea, implement it quickly~~

- ~~1515B: Make several test cases to test your solution~~

- ~~1515C: Don't overthink it~~

- ~~1515D: Again, don't overthink the problem and try to implement it quickly~~

- ~~1515E: Don't hesitate to implement an idea and try not to waste so much time thinking of better solutions~~

- ~~1515F: There's a simple greedy solution but it's not obvious why it works; write out some equations and try to use them to get a proof~~

- ~~1527E: Obviously a DP problem, first try the D&C optimization, then try to speed that up; one way is to split into blocks and save a lot of stuff to avoid recomputations~~

- ~~1601C: Kind of a weird sweep line problem since it goes down to up, so you have to really think about the problem in a different way~~

- ~~1606E: Think about how to use math to calculate the DP transition~~

- ~~1579G: Two different ways to solve, either using DP or binary search plus a bitset optimization; The binary search method seems too slow but you can optimize it with a bitset~~

- ~~1603C: Multiple ways to think about the DP, try to avoid maps since they're slow but you can optimize it to work~~

- ~~1537F: Don't overthink it, try to use simple ideas like finding a spanning tree~~

- ~~1560F2: It's just brute force, get started coding and don't stop~~

- ~~1593G: Very deceptively simple, the solution seems so easy that it wouldn't work but try implementing it anyways since it's so short~~

- ~~1580A: Think about how to improve the brute force solution~~

- ~~1580C: It's quite obvious that it's a square root decomposition problem, start implementing it right away~~

- ~~1598F: A quite standard problem~~

- ~~1583E: Pretty obvious actually, try to implement it quickly~~

- ~~1582F2: There's an easy O(N^3) DP but it has a lot of redundant states that you can speed up to O(N^2 log N) or O(N^2) with precomputation~~

- ~~1584E: The implementation is a bit tricky to get the indices right so work it out on paper first~~

- ~~1578L: Either binary search or calculate the answer directly, but the second option is way easier to debug~~

- ~~1612G: Do some math, try to find a simple form for the value you want to compute for the array so it's easier to work with~~

- ~~1618G: Model it as a graph and process the edges in a way that's nice~~

- ~~1614D2: Time limit is very high so implement a "slow" solution and it passes~~

- ~~1614D1: Same as above~~

- ~~1536E: Try some small cases and notice that there's an obvious (kind of stupid) pattern~~

- ~~1626E: I hate this problem~~

- ~~1628A: A greedy algorithm but need to think through the logic clearly, however, get started implementing immediately to solve it fast~~

- ~~1628B: Do a lot of test cases!~~

- ~~1620G: I hate this problem too~~

- ~~1635E: An easy graph problem, but make sure you read it correctly because I thought of a solution that solves the wrong problem~~

- ~~1630C: Focus on the tricky edge cases~~

- ~~1535E: Read the problem carefully and think about what classical problems that it's similar to and try to adapt that algorithm to work here~~