ABCDEFGHIJKLMNOPQRSTUVWXYZAAAB
1
ProblemStatusDifficultyTopicsTakeawaysAnalysisHow I can come with the solution(Only if you read
editorial)
2
3
https://atcoder.jp/contests/abc262/tasks/abc262_eDifficuly in coding up
the solution		GraphIf you are given a condition that seems hard,
you can deduct a condition from it using some
equation and then try to work on it.
This could be much easier to solve sometimes. 		We converted the conditon of even
number of edges between blue and red
vertices to that the sum of degrees of red
vertices be even using S = 2*R + D.
4
https://leetcode.com/problems/new-21-game/DoneLeetcode mediumDP, ProbabilityIn dp problems we can reduce one for loop
somtimes if we are going to a new state from
a fixed amount of different states and they
contribute to it in a simiiar way.
We can maintain a running product or sum
and update it accordingly.		Instead of having a extra loop for transitions,
we maintained a running sum and
calculated probability using that.
5
https://atcoder.jp/contests/abc262/tasks/abc262_dDoneHardDpdrWe used a dp to maintain the the prefix,
number of elements and remainder.
6
https://atcoder.jp/contests/abc262/tasks/abc262_fNot DoneHardAdhocIf in a question, you are given a choice for two operations.
->If the given problem is too hard solve an easier one

We can try the problem by just doing one operation only.

7
https://codeforces.com/problemset/problem/478/DDone*2000DpIn dp problems sometimes we can store another dimension
which is very large in a another small dimension and
we can retrieve it using two dimensions together.		In this problem instead of forming
dp[r][g] we did dp[h][r] and retrieved g from
h and r.
8
https://codeforces.com/gym/100685/problem/JDoneInteractiveIn interactive problems we could use a function that we
would have and just call it.		Here we made a function that compare
values in a merge step.
9
https://codeforces.com/problemset/problem/1552/FDone2200DpIn problems where path is changing i.e you cannot just
apply dp as the substates are changing think about
whether there is something about the paths which is
constant and try to apply dp to the subproblems.
Observation is key		In this problem we observe that whenever
we are past a certain all the portals
behind us are closed. This leads to the
observation that we can apply dp to the
states.		I will have to notice certain properties of the paths,
maybe it doesn;t change at all, maybe it revverses
or maybe it follows the certain properties like it does
in this case i.e the path is always same. All
the portals are open.
10
https://codeforces.com/contest/118/problem/EDone2000GraphIn problems where we need to construct something, we
need ot make observations. Like what properties does
the edges needt to have to confirm the properties.
Doesn some of the edges need to be tree edges or
backward edges? Observation is key.		In this problem we drew a DFS tree.
We made a observation that if this graph
has a bridge we won;t be able to do it.
Now we looked at the edges. We observed
that the downward edges shoudl
point in that direction and backward edges
upward no we can go from source to
anywhere and from anywhere to source
11
https://www.codechef.com/AUG221D/problems/HLEQNDoneMathsWhen we need ot find x and y that satisfy something
it is a good idea to separate x and y on LHS and RHS
and see if you could do another problem which is much
easier wrt to time complexity		We converted 2*x + 2*y + x*y = K to
x = (K+4)/(y+2) -2. All we need to do now
is find y+2 such that K+4 is divisible
by y + 2 and see if its greater than 2.
12
https://codeforces.com/problemset/problem/484/BDone2200MathsWhen we think about maximising MOD. Just try to find the
closes element to k*x - 1(inclusive)
(if we are finding MOD of x).


When we need to find the lower bound we can use a
array istead of set if the values are small enough.

TIme complexities of harmonic numbers can be decieving.

We first constrructed a table for array.

We itterated through every aj and found
maximum value for every 2*j to M
where M is twice the maximum
element.		When we think about maximising MOD. Just try to find the
closes element to k*x - 1(inclusive)
(if we are finding MOD of x).
13
https://codeforces.com/contest/1719/problem/D1Not DOneDpDp should be constructed so as to have
smallest number of dimnesions possible.
Some time we don't have to everything
till i we can do it till i-1 and that's fine too.
14
https://codeforces.com/contest/1720/problem/D1DoneDpIn dp problems when you are pushing and you might need
to push from i + 1 to n-1 it coul be possible that maybe
you don't need to go till n-1. it is possible that we can
go till i+c and that is sufficient. This could be dependent
on the nature of input.		Here we went from i + 1 to i + 256. As
input is bound to be less than or equal to
200. When we will apply xor to number
greater than i + 256 we will be guranteed
that we cant get a lower xor score.		Try to see how pattern in the input can make our
bounds smaller.
15
https://leetcode.com/problems/minimum-number-of-refueling-stops/
(Solution 1)		DoneDpIn some question some times we could change the dp instead
of what the problem statement is because of some
input constraints.
We could have a second dimension as answer and check
the given condition after calculation dp.		Here we used dp[i][j] as the maximum
distance we can travel from station i
an dstopping at j stations.
Afterwards we caculated ans as the minimum
value of j for which dp[n-1][j] >= 0.
We only make transitions if it is possible
to do so.
16
https://leetcode.com/problems/minimum-number-of-refueling-stops/
(Solution 2)		DonePriority queueIn some problems we don;t need to make a greedy choice at that
spot. We can make a choc retroactively.		Here we keep going until we run out of fuel and
we fuel when we relly need to from the biggest
fuel pump possible which we stor in a priority
queue.		We first made a observation that we should just keep
goin gand refuel if we can;t get to the next station,
the problem with this was we might need to refuel at
earlier positions. The solution for this we go as far as
we can. We don't really need to be able to using a car.

When we ae not able to get further we select the one
with maximum fuel and keep going.

We don't need to make a choice right now. regarding fueling up
We can retroactively decideafterwards.
17
https://leetcode.com/problems/k-inverse-pairs-array/DoneDpSimiliar to 4, The key to seeing this type of patterns is
to realize that you are using a for loop for some iterations
and the iterations are just getting add or multiply by a constant
amount. You can maintain a prefix sum which will do this.		We reduced a cumulative sum dp to reduce one
for loop.		Just think about how you can use a for loop, the key to seeing it is that we are
just adding certain amount of indices using a for loop which could be done
using prefixSum.
18
https://atcoder.jp/contests/abc265/tasks/abc265_e
(Solution 1)		DoneDpIn some it might seem like there are a lot of possible state, but
it can be that a lot of states are repeaing which is not intuitive
but you don't know the exact states and constructing a
traditional dp array might not work. In these type of questions
one can use map as a dp.		It turned out a lot states are repeating and
there are only O(n^2) states at any given point
we used a map as a dp instead of traditional
dp as the dp array will be humungus and a lot
of states are kinda useless.		It could seem that there are a lof states. Try to analyse exactly the number
of unique staes in the question. Now if the dimension for the dp array is
going huge and a lot of states will neverbe reached you can think
about using a map.
19
https://atcoder.jp/contests/abc265/tasks/abc265_e
(Solution 2)		DoneDpWhen it seems like the dimensions of a dp will go out of
bounds think about how you can represent the state where you
want transitions from using other variables which will result in lower
bounds. We used this idea in problem 7(Different options)
We used dp[n][x][y] ans the numebr of ways
to do n transitions such there are x first steps,
y second steps and n - (x+y) third steps. Now
we calculate ou current position and make the
transitions.		When the dimension bounds are going out of line think about
how you can represent in another dimension which will reduce the bounds .
This happens when we are doing different type of transitions whcih can take
us to a different place.
20
https://leetcode.com/problems/regions-cut-by-slashes/DoneLeetcode mediumGraphWhen you tried this question it seemed really hard to determine
the number of connected components because it was quite hard
to deal with '/' and '\'. We ended up partitioning the graph into
4 parts and that made it really easy to move across.
We partitioned the graph into 4 parts and
found the number ofconnected components.		When it seems hard to traverse a graph think about how you can manipulate
the graph such that it becomes easier. Here instead of taking a box as a vertex.
We partitioned the box into 4 parts and then applied dfs.
21
https://codeforces.com/contest/1716/problem/CDone20001) The problem that involves time. You need to think that to reach
a destination the time required will be the time required to do the
maximum of all the things
If you need to reach a destination which has a hurdle at distance x,
the time taken will be max(distance/speed, hurdle opening time
+ distance left/speed)
2) To calculate max(a[i] +x) for a lot of x, you can just calculate
max(a[i]) and then add x while answering.		We used answer = max(prefCurTime+2*sufLength,
forwardSufAnswer + sufLength,
backwardsSufAnswer)		When a problem involves time. You need to think that to reach
a destination the time required will be the time required to do the
maximum of all the things
22
https://codeforces.com/problemset/problem/182/DDone1400Strings1) When you think about checking every thing think about the
constraints that question imposes		Here we only need to check for prefixes whose
length divide the length of the string
23
https://codeforces.com/contest/1716/problem/DDone2000DpThis is similiar to multi knapsack problem. In multi knapp sack problem
>Instead of deciding how many times we need that thing whicl will
lead to logn transitions we can just give a option to do it again
Instead of going from dp[3]->dp[5], dp[7], dp[9], dp[11]
We can add dp[3] to dp[5] and when we from dp[5] to dp[7] we have
already added dp[3] to dp[5] so this already gets accounted.
Here instead of deciding how many times we take
a particular item we decide how big of a jump we
should make using a value. A cool question		Next time when you have to add a thing to multiples of numbers consider doing
that to the same layer and the rest of it will take care of it itself.
24
https://codeforces.com/contest/1717/problem/ADoneIn the questions where we have to satisfy some inequality think about
the only cases where this will be true. Most of the times there will be
special cases like that.		Here the only possible numbers are (x, x), (x, 2x)
(x, 3x).
25
https://leetcode.com/problems/race-car/DoneLeetcode harddp/BFSWhen it seem like it is hard to find a topological order, think BFS.
26
https://codeforces.com/contest/1728/problem/DDone1800Game theory, dpdp[i][j] = mini(maxi(dp[i+1][j-1], dp[i+2][j]) + s[i], maxi(dp[i][j-2], dp[i+1][j-1])+ s[j]);
In ou rinitial approach it was not obvious an dvery likely wrong the idea that the string
from maxi(dp[i+1][j-1], dp[i+2][j-1] would be the one that bob makes sure alice gets.
ALice's string doesn;t nevessaily correlate with bob.		We used dp[[i][j] as the dp regarding who wins if the
configuration was s[i...j] Now we use that approach
and deal with the cases where there is a draw
carefully.
27
https://codeforces.com/contest/1728/problem/CDone1400greedyOne observation you can make is that you wont need to make the step more than 2
times.
Second observation is if two arrays are equal you won;t need to o anything
Third observation is you can see the largest number and know instantly if there
is a number that is equal to it, if not you apply the function to the number.
28
https://codeforces.com/contest/1729/problem/EDone1800InteractiveIn problems which involve some probabilities or say two paths of equal probalbilities
or say "the answe ris atleast" try to come with a solution that won't work always but
will fail very very rarely.		Here we asked if there is a edge between 1 and i
about 25 times and we will fail with probability
2^-25 which is really low.
29
https://cses.fi/problemset/task/1195 (Solution using 2 djkstras) DoneGraphIn questions where we can play around with one edge(say {u, v} while computing
distances. It is useful to calulate to calculate distance for every u(from source to zero)
and from every v to target. To calculate distance for every v to target. We can run BFS
or Djikstra for the reversed graph and start from target.

Now we can consider every edge and play around.		We computed distance to every vertex u for the
source
Then we computed distance for every vertex to n
Then for every edge (u, v) we minimised
(dist1[u] + dist2[v] + w(u, v)/2)
30
https://www.codechef.com/submit/REMONEFailing 1 test caseIn problems where a number is added to a subaarray, rember that the difference
between adjacent elements doesn't change.		Here we used it to find a missing element
31
https://codeforces.com/contest/1730/problem/BDoneTernary SearchHint 1: When there is a problem in which we have to optimise a meeting point think
ternary search.
Hint 2: If there is a problem in which a bitonic function(increases then decreases or
decreases then increases) is involved think ternry search
Hint 3: When the problem implies some kind of precision checking think binary and
ternary search
Here we just ternary searched on the optimal position
32
https://codeforces.com/contest/1473/problem/DDoneSegement TreeWhen there are some queries and you can somehow merge 2 halves, think segment
tree.		We form a segement tree where each node consists the maxium
value 0 will atain, minimum value 0 will attain and the final value
FOr a given node answer would be maximum - minimum + 1/
33
https://codeforces.com/contest/1473/problem/D (Sol 2)DOnedpWhen you are asked to qury(L, R) it could be that we can do it using queries(0, L-1)
and (R + 1, n-1). If that;s the case think dp.
When the value increases or decreases by 1. The number of unique values it takes
are max - min + 1		We used two dps and merged it using
int lowerLimit = min(left.first, right.first + value[L-1]);
int upperLimit = max(left.second, right.second + value[L-1]);
and the answer is
upperLimit - lowerLimit + 1
34
https://codeforces.com/contest/319/problem/B (Sol 1)DoneStack1) When there is a simulation in which some elements are getting deleted or
array is changing length, it is a good idea to use stack or two stacks to simulate the
process. In this case we are not really simulating the process but a stack could be
helpful
2) In this question we need to find the next greater element on the left as that will
be the one that will kill us or the one that kill it. It doesn;t really matter as by the time
we will reach there someone will be there to kill us
3) When we need the next greater element or stuff like that stack is a good idea.		We set the time for initial place to -1. Now for the ith element we
look at the top of the stack. If it is greater we know this is it
we set the timer to 0 and push it to the stack
If the element is smaller we need to find the next greater element
and the time to reach there, now we will pop until we reach there
and calculate the time required to reach there which is
max(timeToReach, time[S.top()])
The reason we can pop the element is because we know that
this will kill no element on the right
You need to observe that we will get killed by the time we reach next greater element
on the left. When a question involves something liek next greater or previous grater element stack is a good idea.
35
https://codeforces.com/contest/319/problem/B (Sol 2)DoneSet, Simulation1) When there is a simulation, think about how you could do it fast
36
https://codeforces.com/contest/1738/problem/CDoneSetIn questions that involve games, you need to realise what is going on.
Ask these questions:
1) Does everyone want to just maximise things for themeselves?
2) Or is the goal to make sure that the other guy doesn;'t achieve anything
You will need to use different dp for both cases		We used dp[i][j] and oddDp[i][j] to calculate if alice can get sum
even and odd.
37
https://codeforces.com/contest/1739/problem/DTime Limit ExceededTrees, Binary SearchHere it was really hard to decide at which spot you want to cut a tree. When we have
a hard time moving forward, we shoudl think the problem in a opposite ro backward way
We can calculate how uch cuts do we need to get a tree with height atmost H. Now we
binary search for minium height with at most k operations.
Note that height possible is monotonous with number of operations so as number
of operations increases height decreases
Binary search often works when we are asked teh minimum health equired and stuff
so be aware
38
https://codeforces.com/problemset/problem/363/DDoneBinay SearchWhen it seems hard to move forward in minimise and maximise problems it is
often a good idea to do bianry Search for the answer		Here we binary searched for the maximum number of bikes
39
https://codeforces.com/contest/1737/problem/CDoneAdhocWhen a question involves a chess board please open one on chess.com and do
some experimentation
In questions like these we shoudl always do a lot of experiments and write down
observations
When we want to find a number that has occured just once and other has
occured twice use xor
Be very careful of corner cases in these questions
If the problem involves chess think color
40
https://codeforces.com/contest/1741/problem/EDoneDpIn some problems when you are required to remove the for loop in dp problems.
It could be helpful to do both forward and from back ward transitions at the same
time.		We were using a for loop to check if if(A[j] == j - i - 1) for every j
instead of that for ever i we checked if
dp[i-A[i]-1] is true
41
https://cses.fi/problemset/task/1137DoneTrees, Segment TreeIn a tree when you are asked for a subtree query, you can use segment trees(overkill if
they ask for no updates). Now L and R for the segment tree can be calculated usign the
start and end time while using dfs. Keep in mind ot not use vector in a map as it is very
slow
Array for the segment tree can be caluclated usign preProcess order and preprocess
order can done using start time or just do it within dfs.
42
https://cses.fi/problemset/task/1653/DoneDpSometimes in order to reduce a for loop we can store 2 objects in our dp answerHere we used pair<ll, ll> in our dp. dp.first stored the minimum
number of elevator rides for our bitmask. dp.second stored the
minimum weight possible.
43
https://codeforces.com/contest/1749/problem/BDoneIn problems that involve adding up some powers to adjacent elements.
Think about the end state a lot. What happens when its all said and done.
Here there would be a element at the end whose Bi won't be added.
So we just take the sum and maximse teh bi for minimal time.
44
https://codeforces.com/contest/1754/problem/C1DoneWhen pproblems involve subsegments. Think about how you can form one without affecting
others. you need to see to first observe when you can't make a segment.		We saw that odd lengthd won't be able to from such segments.
Now wiih even lengths every lengths os 2 will have a answer
45
https://codeforces.com/contest/1753/problem/CDoneThis is very hard to come up with. But it really helps tot visualiz the end state.
Suppose number of zeroes is k
WHat happens? We end up with k zeroes in the first k positions
If a transition happens outside of the first k positions it doesn"t help us. So what is important
that has happened so far. Number of zeroes in the first k positions. From here you
can easily make transitions.		Let p=2⋅(g−k)⋅(g−k)n⋅(n−1). Then dp[k]=1+dp[k]⋅(1−p)+dp[k+1]⋅p.
46
https://cses.fi/problemset/task/1143/DoneA very instructive problem. When we need to find a first number that is greater than a
particular number, my idea was to do a recursive function but we will need a maxium
of every segment quickly.		To achieve this we used segment trees, RMQ would work if there
were no updates.
47
https://codeforces.com/contest/1740/problem/CDoneSOmetimes it can be dangerous to make assumptions and draw geometry in a
symmetric way so try to consider all cases. And think of the extremeties when
mmakign figures while trying to solve geometry problems.
48
https://codeforces.com/problemset/problem/546/DDoneNow dp[i] be the number of rolls it takes to take us from i to i -1 difference.
dp[i] = 1 + (n-i)/n(dp[i] + dp[i+1])

49
https://codeforces.com/contest/340/problem/DDoneYou will have to realise that the answer will be the Longest Increasing Subsequence.
The way to see it would be that for indices i1, i2, i3 , i4, i5..... Ai1, Ai2, Ai3....
will for a independent set if for d and e d < e and Ad < Ae. Hence proved.
50
https://cses.fi/problemset/task/1081DoneWhen the output has some limit, we can just bruteforce the answerHere we just checked that whether a number can be gcd by
brute force.
51
https://codeforces.com/contest/1747/problem/CDoneIn the problems that involve games, You need to start with the final state. Think
about what the final state will look like and think about the moves leading up to it.		In this problem we observed that whenever there is a 0 on the
array the side wins. SO the guy who gets to 0 first will win,
Alice will choose the minimum number on teh right side of the
array. If it is smaller than A[1], she wins else she losses.
52
https://cses.fi/problemset/task/1651DoneWhenever we update a range like add some number to the range. ALways think about
what we will do in the equivalent difference array. It can be much easier. As when we do some
thing to the range it difference stays the same except the left end and right end which could
be updated in constant time.		We create a difference array. Like [2,3, 5, 7, 9]. The difference array would be [2, 1, 2, 2, 2]
When we want to add 3 to [1, 3] it would be [2, 5, 2, -1, 2]. And to get a particular number we
just find the sum [0, i] to get the value at index i.
53
https://codeforces.com/contest/1750/problem/DDoneNumber TheoryIn this question it felt liek time colpexity woudl be huge if you use inclusion exlclusion
but it turns out that number of primes would never be more than 89
Remeber that 2*3*5....9 terms > 1e9. And As A[i] will reduce by a one of the primes
every time the quotient will not taske value more than 1 more than 9 times
54
https://codeforces.com/contest/1750/problem/CDoneConstructive AlgorithmsIn these type of questuion it is really important to note what is the invariant
Here it is not obviuious at all
What is happening is everytime we do the operation (11111111) is getting xxored to A^B.
I don't think I could figure this out
So if xor of the arrays is not 0000000 or 1111111 we could achieve the goal. As (111111) will
only change the signs. So we first check if B is complemnt of A or is same.
Now we just make evry A to 0 and check if B is (00000) or (111111) . If it is the latter,
we could just do th3ese 3 operation(1, 1), (1, n),, (2, n)		When things complimentasry things are flipping in 2 AArrays check what is
happening to the xor, product, sum oif the combuined array.
Maybe they remain constant, maybe they are getting changed by a fised constant.
Finding the invariant is key in these type of questions.
55
https://codeforces.com/problemset/problem/41/EDonethe n-vertex triangle-free graph with the maximum number of edges is a complete
bipartite graph in which the numbers of vertices on each side of the bipartition
are as equal as possible.
Our algorithm which involved always selecting the one with smallest number of edge
also worked by luck.
56
https://cses.fi/problemset/task/1688/DoneThis question involves euler tour. The key property of euler tour is it always goe sthe
smalles distance from one node to other but it will also visit some other subarrays.
To find LCA we found teh finimum height in the required interval.
57
https://codeforces.com/contest/1225/problem/DNot able to debugNumber TheoryThis was a beautiful question. We ere having a problem deealing with the prime factors that are
already in the power of k,
For ai.aj to be x^k, for every prime p the number of times it divides ai and aj should be divisible
by k.
To deal with the above thign we coudl just take modulo of every priem factor. Just beautiful.		Next time you have a problkem dealing with extra prime factors think about whether
taking a gcd or modulo will help.
58
https://cses.fi/problemset/task/1130Donedp., treesWhen you are asked to consider every edge separately in a dp on trees question. You can have
soem kind of prefix sum of all the edges. Then do soemthing for the particular edge and add the
remaining.		Here we considered every edge separately to calculate dp1[u]. We did
dp1[u] = max(dp1[u], dp2[v] + 1 + dp2[u] - max(dp2[v], dp1[v]))
59
https://cses.fi/problemset/task/1132/Donedp, treesA very instructive problem. It is a common technique to calculate two dp arrays for some dp on
trees problems. Usually one array is responsible for calculating results within the subtree rooted
at i/ The other dp array calculates result outside of the subtree rooted at i.
One key idea is when we have to consider every vertex. Maybe we need maximum of
all the other vertexes oir sum of all the other vertices.
We can use ideas like second maximum and total sum.
We caclulated the biggest path of subtree at root i and other than at root i and took the
maximum.
60
https://codeforces.com/problemset/problem/193/ADonegraph, constructionThe key abservation is that the answer could be onyl 1 and 2. Note that we can choose a square on the
corner which will have at most 2 neighbours and disconnect it.
Now we just ran dfs fr every cell cand checked it converting it to . makes the graph
disconnected.		In questions where it involves disconnecting graph or in aalmost any question
as yourself if there is a upper limit for the answer. Also ask yourself if there is
a upper limit until which you would loop.
61
https://codeforces.com/contest/1748/problem/BDoneThe key observation is that we don't need to iterate for a length more than 100 for any i. This is
because every character can appear maximum 10 times as there are 10 distinct number

Whenever there are altin alphabets or digits involved thik about the maximum amount of times
you will need to iterate. Think about whether the answer is capped.		This is trivial
62
https://cses.fi/problemset/task/1139DoneRange QueriesIn some range queries problems where we are not asked to updatte values. It could be a good
idea to process them in some order liek Mo's algorithm.		Here we process queries from right to left sorted with respect to left index. We update a array B such
B[i] = 1 and if that element has already occured. we set its previous value to 0/
TO answer a query we use segment tree and calculate sum(1, 0, n-1, l, r)		The reason this works is we will never have to process a query towards right
so we will never miss anything.
SO you will need to realise is when something exists only once then having the
leftmost index is enough.
63
https://codeforces.com/problemset/problem/197/ADoneGamesIn games problems where it seems very difficult to calculate different states, think about how you
could use symmetry arguments.
In this problem we placed a circle a the center. Now for eveyr move of B there is a mirror image
of a move of A.
Think about whether you could create a position where for every move of some player
you will surely have move.
This isn't entirely obvious if you don't have a circle at the center but once you have it. For every move of B there is a move of A.
Note that if moves first there isn't always a move for B as there might not be enough space
but if there is move possibility for B there will always be one for A.
64
ake DoneIn problems think about how much you can take greedily.
1) If a%b == 1 it implies that gcd(a, b) = 1
2) if gcd(a, b) == 1 then a%b will either be 1 or remainder will be coprime with n
3)If we divide a by this remainder than a/rem%b = 1.
65
https://codeforces.com/contest/472/problem/DDoneGraphWhen you have the length of al possible paths. If you take the kth minimal path, if it does not the connect
corresponding vertices in the graph created till now it must be a edge of a minimum spanning tree.
66
https://codeforces.com/problemset/problem/1543/CDoneProbabilityYou should think of expected value as a dfs tree in a lot of questions. You can bruteforce through it if
it is finite. If it is infiite you can form some recursive relation and find the value mathematically.
67
https://codeforces.com/contest/1543/problem/D1DoneInteractiveIn interactive problems iif you have more queries than you can have think about how you will
merge them		Here initial we come up wth this 0^0^1^1^2^2^3^3
The idea was to reverse the effect of the previous query
Now we just merge them (0^0) ^ (0^1) ^ (1^2) ^ (2^3) ^ (3^4)
68
https://codeforces.com/contest/1766/problem/DDoneNumber TheoryThere are no more than log2(n) prime divisors of a number n. If we know one prime divisor for every
number from 1 to n we can know ever prime divisor of a numbe in log2(n).
69
https://codeforces.com/contest/1762/problem/DDoneInteractiveIn problems where you are asked to output two values and any of them could be correct.
Think about how you could start with 2 numbers, take every number onces and eliminate one of them
70
Problem - F - CodeforcesDoneTreeWhen you are required to visit some vertices in a tree, you can eliminate
all the leaves that you are not going to visit. Need ot be careful here.
Method 2: We can just determine if a vertex is important. To do this we need to know if we have a important
vertec in a subtree. This can be done using set or colors.
71
Problem - C - CodeforcesDoneConstructive
In questions that involve binary string to think about prefix and suffix. try to make observationswith regards to
consecutive 1 or 0s in suffix/prefix.
72
Problem - D - CodeforcesDoneConstructiveWhen you are makign exchanges between stuff to make things balanced. You might try a greedy approach
where if things are unbalanced you just balance them in a greedy way.
There will always be a spot for which you have 1-0 if you still have a different count of ones,
because you have target — 1 and target + 1 count of 1s. That is all.
Therefore it doesn't matter what order you choose to do the place swaps.
73
Problem - C - CodeforcesDoneConstructiveIn problems that involve change a range to a ceratin number. Think of extrema principle i.e. focus the
biggest and smallest element. 		Here it was obsevrde that we can always change a array greater than 3 su ch the every element is a
number.
Cases with n = 2 and n = 3 were done using brute force.
74
Problem - B - CodeforcesDoneConstructiveWe could think of a invariant here after every step.
Invariant: The difference between the largest and ith largest number never increase after every step.
Now during the last round if we don't have exactly n%k flowers left, all our effort would be in vain.
This would happen when the difference between largest n%k + 1 the number doesn;t decrease ever.
This will happen if they all are equal.
Note that this won;t if the largest number is less than rounds as it will be reduced to zero before and we
would be able to get n%k ones
75
Problem - 1554B - CodeforcesDoneBitmasks1) When you are supposed ot maximise a expression, think about that is the maximum value it can take,
what is teh minimimum value it can take. Be very fluid with the values of ai and aj.		In this question teh first observation is the value would be bigger for heavier i and j. Maximum value
this function can take is when i = n-1 and j =n. Now for osme another i to contirbute to the answer,
the maximum mvalue it can take shoudl eb greater than the minimum value that comes when
i is n-1 and j is n.
minimum value = n-1*n - 2kn
maximum value = i*n
Now i*n > (n-1)*n - 2kn
=> i > n - 2*k -- 1		Just make observations that when teh functiontakes the maximum value
And note how will i and j contribute. Will they need to follow some precondition?
76
https://codeforces.com/contest/1731/problem/DDoneBinary Search1) When you have to find for a lot of queries if a submatrix or a subarray is less than a value(valeu can't
change) you can do this.
Make a array A such that A[i][j] = 1 if grid[i][j] >= x and A[i][j] = 0 elsewhere.
Now do a prefix sum.
Now for any query, see if the sum of the submatrix or subarray is equal to the size
if YES none of the value is greater
77
https://codeforces.com/contest/1783/problem/BDoneConstructive1) Whenever you use a 2D problem try to solve 1D version of it
If the give problem is too hard solve a simpler one		Here in the 1D case answer is 1 n^2, 2, n^2-1, 3 n^2-3
Now to conver the answer to 2D just do a snake path, this way you will always consider all the 1D
cases. And you will have no need to consider up and below cases
78
https://codeforces.com/problemset/problem/1637/DDoneMaths, dpWhenever you are given a expression always try to simplfy it into a easier/manageable one
79
https://codeforces.com/contest/1768/problem/DDonedo tghi
80
https://codeforces.com/problemset/problem/1603/BDoneMathsIn questions that involve finding n for x and y.
Do this:
1) First write some equations
2) Brute force n for different x and y.(Don't just write the first n. Write all see) Always look for the last
and first n. These are usually the most important.
3) After seeing n try to identify a pattern. Make hypothesis and check it out /
81
https://codeforces.com/contest/1782/problem/DDoneMathsIn this question we were trying to reduce the value of x somehow. We were able to come up the idea
that we can the value of x that satisfies for square condition for A[i] and then try it for every number
A better idea is to check for all pairs which x wil be such that both are perfect squares
Now we can use all those x and check. Thius reduces the complexity immensely
82
https://www.codechef.com/problems/FTOL?tab=statementDoneDpIf you have to find a longest increasing subsequence of pairs given you can use the array in any order
You should sort the array accoridng to x and then find LIS w.r.t to second coordiinate
TO avoid sam x values sort with increasing y when x are equal
83
https://codeforces.com/problemset/problem/1770/CDoneMathsThis problem can be proken down to: In the new array which has x added to each term, each of number
should not be divisible by a prime number more than once
Now for every prime number we can check the remainder of all the values of A[i]. I all of them is more than
1, this can be done for everyprime number.
Not that we have to only check till prime number n/2. After that it won't be possible. If you put n values
into more than n/2 boxes one of them is boudn to have less than 2.

Following problems coludl also be solved.
1) FInd the requried x
2) FOr a gven , find x that maximizes the number of intgers it divides.
84
https://www.codechef.com/problems/MININVDoneMaths1) In some L and R question it could be that R or L could be one of teh extremes.
Here it could b observed by looking at any range and notcing that increasing it upto R will only benefit us
85
https://codeforces.com/contest/1629/problem/DDoneTreesWhen you are asked whether you can construct a solution or minimum something
One approach could be to think like this
Suppose I did find such a solution, what would it look like? What characteristics i twould have?
Can we toy around such a solution so that it remains optimal?
This usually applies on YES, NO questions		Here we did find such a solution, all teh subtrees will have value x and the value fo it would be the
value of the entire tree. Now we coan always combine 3 subtrees, its xor will remain same
So we can have either 2 or 3 subtrees.
86
https://codeforces.com/contest/1366/problem/DDoneNumber TheoryWhen you are asked for gcd of two number be 1.
1) TO soem arithmetic
2) Realise that every prime factor of a number can;t divide another number
87
https://codeforces.com/contest/233/problem/BDoneMathsIn this question, suppose that we did find x, what would it look like? What characrteristics would it have?
Here x will be small than sqrt(n). This imples that sum of digits woudl be less than 81.
So now we just iterate over all sum of digits and do some maths
88
https://www.codechef.com/problems/CANDIES3DoneMathsA straightforward way will clearly not work
For a given price we can a calculate how many members will be able to buy exactly i candies.
Answer would be sum of i*pi*Ck.
To do this we will need to have a frequency array and its prefix sum
For every m we will do n/m operations
89
https://atcoder.jp/contests/arc154/tasks/arc154_bDoneConstructionImaging a process backwards or in reverse operations help. Instead of turning A to B, mayeb turn B to A.
In question where we are aksed to minimize number of operations involved. Maybe find a sequence
which can stay same and other elements will change
90
https://codeforces.com/contest/1777/problem/DDoneMaths1) IF you fnd the sum of somethign across all states. You can possibly find teh expected value and
multiply it by all states. The idea comes from the fact the fact the expected value fo any node is 1/2
before time du.
2) The expected value of xor of k values if 1/2(k > 0). I k == 0, that value is 0.
91
https://codeforces.com/problemset/problem/1765/NDoneConstructionThink about what the solution will look like? What charatceristics it would have.
Ideally we would like to have 1 as our first digit
It woudl have the smallest of the first k + 1 numbers.
To do this we coudl check for each 1 to 9 whether it has it.
After that it is just some implementation and rcursion
92
https://codeforces.com/contest/1343/problem/EDoneConstructionn, graphsWhat would the optimal path look like?
It will have some x such that we go from a-> x, then from x -> b, then from b->x and then from x->c
Total cost: dist(a, x) + 2*dist(b, x) + dist(c, x)
Total edges used: dist(a, x) + dist(b, x) + dist(c, x)
Now we can iterate for every x and use prefix sums
93
https://codeforces.com/contest/1792/problem/DDoneHashing, TrieIn this question we will have to repeatedly check whether there is a permutation which is of the form
_ _ _ 1 _ _ 2 _ _ etc. Now to do this we can do pre computation for a permutation starting from 1 to n
Have 0 instead of _ and store them in a set or trie.

And we can just always look for it.
94
https://codeforces.com/contest/1312/problem/EDonedpSuppose we get the answer, now w
95
https://codeforces.com/contest/1787/problem/CDoneMathsWhen you have to maximise some parts of array to add up to something, think about extreme cases
and Dp
96
https://atcoder.jp/contests/arc145/tasks/arc145_aDoneConstructionThink about what you cannot change. When you are required to replace with some string
There are soem indexes which you cannot change, Look out hard fo rthem.
97
https://codeforces.com/contest/1778/problem/D
(Solution 1)		DoneDp, MathsLet k
be the number of indices where the characters between two strings are different and f(x)
be the expected number of moves to make two strings equal given that the strings have x
differences. We have to find the value of f(k)
We came up with three equations
f(0) = 0
f(n) = 1 + f(n-1)
f(1) = 1 + (n-1)/n f(2)
f(x) = 1 + (x/n)*f(x-1) + (n-x)/n*f(x+1)

Now we can represent f(i) = ai + bi*f(i+1)
From here we can find a relationship between ai+1, bi+1 and ai, bi

Simililarly we can do with ci and di such that f(i) = ci + di*f(i-1)

And eliminate f(i-1)

We will get f(i) in terma of ai, bi, ci, and di
98
https://codeforces.com/contest/1778/problem/D
(Solution 2)		DoneDp, Markov chainsIt can be shown that f(1) = 2^n - 1
Let's suppose that we keep doing the process. Now in steady state each state is repeated in 1/pi steps.
Here pi = 1/2^n. Now that state with zero difference wil repeat on average 2^n steps.
Now to from 0 to 1 difference we will get in 1 step always. SO to go from 1 to 0 it will take on average
2^n - 1 steps.
Now we have f(0) = 0. f(1) = 2^n - 1. We have a relation between f(i), f(i-1), f(i-2) we can do this
99
https://codeforces.com/contest/1778/problem/D
(Solution 3)		DoneDp/Now dp[i] be the number of rolls it takes to take us from i to i -1 difference.
dp[i] = 1 + (n-i)/n(dp[i] + dp[i+1])

Whenever we are supposed to reduce some stuff from i. Try to also come with
stuff that how many steps will it take us to go from i to i-1 and then do the
sum
100
https://codeforces.com/contest/1787/problem/EDoneConstructiveWhen you have to split things into some number of subsequences, think about to split them
into maximum or minimum number of subsequences and then split or combine them
Now subsequences and subarrays of size 1, 2 and 3 are really special so look out for them always.		The idea here is we split it into pairs of a and a^x as much as possible and the remaining one is also
a subsequence with xor 0 and we merge it into one of them.
Now here is why it works
The maximum amount of sussequences possible are number of values with bits as the highest bit of x
Now for every such value a^x will be smaller than them so we can always construct as many subsequences