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 > 1$ can be represented as the sum of $2$'s and $3$'s.↵
↵
<spoiler summary="Proof">↵
↵
We will use induction.↵
↵
$2$ can be represented as $2$. $3$ can be represented as $3$. Now I will show that if we can represent $x$ and $x+1$, we can represent $x+2$ and $x+3$. We can use the fact that $x + 2 = (x) + 2$, and $x + 3 = (x+1) + 2$. To represent $x + 2$, we can take the representation of $x$ and append $2$. The same thing can be done with $x + 3$. QED.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Alternate Proof">↵
↵
We can use the Chicken McNugget Theorem. (Yes). It states that for a pair of coprime positive integers $m, n$, the largest number that cannot be represented as $am + bn$ for non-negative integers $a, b$ is $mn - m - n$. Applying the formula with $m = 2$ and $n = 3$, we get $2 \cdot 3 - 2 - 3 = 6 - 5 = 1$. Therefore, any integer greater than $1$ can be expressed. Read more: https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem↵
↵
</spoiler>↵
↵
↵
## 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.↵
↵
## [problem:1624E]↵
↵
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 $> 3$ can also be generated this way. Submission: [submission:313317958]↵
↵
## [problem:1616D]↵
↵
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). ↵
↵
<spoiler summary="Proof">↵
Let's say we have a subarray of length $k > 3$ with a negative sum. We can split this subarray into two subarrays: one of length $2$, the other of length $k - 2$. Since the sum of all the elements is negative, then at least one of these two subarrays has a negative sum. ↵
</spoiler>↵
↵
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: [submission:316394601]↵
↵
## Conclusion↵
↵
If there are other tasks, please post them in the comments. My dream would that this traick gets added to USACO Guide.
↵
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 > 1$ can be represented as the sum of $2$'s and $3$'s.↵
↵
<spoiler summary="Proof">↵
↵
We will use induction.↵
↵
$2$ can be represented as $2$. $3$ can be represented as $3$. Now I will show that if we can represent $x$ and $x+1$, we can represent $x+2$ and $x+3$. We can use the fact that $x + 2 = (x) + 2$, and $x + 3 = (x+1) + 2$. To represent $x + 2$, we can take the representation of $x$ and append $2$. The same thing can be done with $x + 3$. QED.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Alternate Proof">↵
↵
We can use the Chicken McNugget Theorem. (Yes). It states that for a pair of coprime positive integers $m, n$, the largest number that cannot be represented as $am + bn$ for non-negative integers $a, b$ is $mn - m - n$. Applying the formula with $m = 2$ and $n = 3$, we get $2 \cdot 3 - 2 - 3 = 6 - 5 = 1$. Therefore, any integer greater than $1$ can be expressed. Read more: https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem↵
↵
</spoiler>↵
↵
↵
## 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.↵
↵
## [problem:1624E]↵
↵
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 $> 3$ can also be generated this way. Submission: [submission:313317958]↵
↵
## [problem:1616D]↵
↵
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). ↵
↵
<spoiler summary="Proof">↵
Let's say we have a subarray of length $k > 3$ with a negative sum. We can split this subarray into two subarrays: one of length $2$, the other of length $k - 2$. Since the sum of all the elements is negative, then at least one of these two subarrays has a negative sum. ↵
</spoiler>↵
↵
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: [submission:316394601]↵
↵
## Conclusion↵
↵
If there are other tasks, please post them in the comments. My dream would that this tr
