cp-notes/tips.txt at main · Dwin2/cp-notes · GitHub

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
Tips for solving problems


General:

1. Sort the input in some fashion
- Patterns may show up
- Base solution on fact that input is sorted
- Greedy solution (possible ?)

2. Analyze changes
- What is changing in the answer?
- What is causing the change?
- Can we generalize a cause and effect?

3. Try small cases
- N <= 20
- Look for patterns

4. Look for special properties in problem
- Constraints for all variables

5. See if something happens until an index k
- Binary search for k

6. What is suboptimal?
- Repetition
- Overlap

7. What do you need in each step of the algorithm?
- If you only need last index i for which some property holds true, consider using a stack
- Group information together by same index or ... then precalculate (possible ?)

8. Simplify problem
- Dimensions !
- What is unnecessary and necessary?
- Mod everything, substract everything, ...
- Only keep relative order (coordinate compression)

9. Loop in reverse order ?

10. Ans = Total - rest ?
- Calculate total and rest instead of ans

11. Equivalent conditions

12. Game theory thinking
- Who wins and when?
- What is optimal strategy? (mirroring, use some x each time, make sure condition y satisfied each time)
- Reduce bigger cases to smaller cases where winner is certain
- Force other player to make some move

13. Choices
- If there's room for choice in problem, make reasonable predictable ones
- Always set it to X

14. Construction problems
- How does checker work?
- Always a pattern, construction must be 100% predictable

15. Check for lower and upper bound on answer
- Is everything between lower and upper bound possible?

16. Simplification of Problem
- What doesn't matter in the problem?
- What is always fixed?
- Eliminate that and look at subproblem
- What matters in the problems?
- How many elements matter? O(sqrt N) O(log N) ?

Strings:

1. Take advantage of only 26 letters
- O(26N) ...

2. Hashing/String algorithms

Math:

1. Rearrange equations
- Avoid division which causes precision errors
- Group similar information together

2. Number of subarrays = # of left end * # of right end

3. Take advantage of relatively small number of primes/perfect squares/etc. less than <= N

4. For any problems with factors/gcd/lcm, always consider prime factorization


Graph Theory:

1. Connect all nodes to 0