This blog will describe an interesting trick I've seen in a few tasks.

This is my first time writing a tutorial blog so sorry if it makes no sense.

$$$2$$$ and $$$3$$$ can build anything you want.

This trick is based on this observation: any number $$$x \gt 1$$$ can be represented as the sum of $$$2$$$'s and $$$3$$$'s.

How do we use this??????

We can use this idea if we take something of some length from somewhere. Often, we can't just look at all the things we can take because it could be too slow. Instead, what if we limit ourselves to taking things of length $$$2$$$ or $$$3$$$?

I know this is very abstract and high-level, but these tasks will show what I mean.

1624E - Masha-forgetful

This is just a very direct application of this trick. Instead of worrying about every substring, we can only account for substrings of length $$$2$$$ or $$$3$$$, since any substring longer than that can be broken down into shorter substrings. So any solution generated with lengths $$$ \gt 3$$$ can also be generated this way. Submission: 313317958

1616D - Keep the Average High

Funnily enough, this problem was released less than 2 weeks before 1624E.

Firstly, let's subtract $$$x$$$ from all the numbers in the array. Now, the condition becomes $$$a_l + a_{l+1} + ... + a_r \ge 0$$$. Now, here's the genius part. Instead of worrying about every subarray, is it possible just to consider subarrays of length $$$2$$$ and $$$3$$$? It turns out, yes. If every subarray of length $$$2$$$ and every subarray of length $$$3$$$ have a non-negative sum, then every subarray has a non-negative sum. (Except for subarrays with one element).

From here, we can do a simple DP: $$$dp(i, j, k)$$$ is the maximum number of elements we can take from the first $$$i$$$ elements, $$$j$$$ tells us if we have taken $$$a_i$$$, and $$$k$$$ tells us if we have taken $$$a_{i-1}$$$. Submission: 316394601

Conclusion

If there are other tasks, please post them in the comments. My dream would that this trick gets added to USACO Guide.