Polycarp and Div 3
Contest: Codeforces Round 496 (Div. 3)
Difficulty rating: 1500
Tags: dp, greedy, number theory

Polycarp likes numbers that are divisible by 3.

He has a huge number $$$s$$$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $$$3$$$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $$$m$$$ such cuts, there will be $$$m+1$$$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $$$3$$$.

For example, if the original number is $$$s=3121$$$, then Polycarp can cut it into three parts with two cuts: $$$3|1|21$$$. As a result, he will get two numbers that are divisible by $$$3$$$.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $$$3$$$ that Polycarp can obtain?

Input format:
The first line of the input contains a positive integer $$$s$$$. The number of digits of the number $$$s$$$ is between $$$1$$$ and $$$2\cdot10^5$$$, inclusive. The first (leftmost) digit is not equal to 0.

Output format:
Print the maximum number of numbers divisible by $$$3$$$ that Polycarp can get by making vertical cuts in the given number $$$s$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $$$3$$$.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $$$33$$$ digits 0. Each of the $$$33$$$ digits 0 forms a number that is divisible by $$$3$$$.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $$$0$$$, $$$9$$$, $$$201$$$ and $$$81$$$ are divisible by $$$3$$$.

Example input:
3121

Example output:
2

Example input:
6

Example output:
1

Editorial:
There are multiple approaches to solve this problem. We will use dynamic programming approach.
Let's calculate values of the array $$$z[0 \dots n]$$$, where $$$z[i]$$$ is the answer for prefix of the length $$$i$$$. Obviously, $$$z[0] := 0$$$, since for the empty string (the prefix of the length $$$0$$$) the answer is $$$0$$$.
For $$$i>0$$$ you can find $$$z[i]$$$ in the following way.
Let's look in the last digit of the prefix of length $$$i$$$. It has index $$$i-1$$$. Either it doesn't belong to segment divisible by $$$3$$$, or it belongs.
If it doesn't belongs, it means we can't use the last digit, so $$$z[i] = z[i-1]$$$. If it belongs we need to find shortest $$$s[j \dots i-1]$$$ that is divisible by $$$3$$$ and try to update $$$z[i]$$$ with the value $$$z[j]+1$$$. It means that we "bite off" the shortest divisible by $$$3$$$ suffix and reduce the problem to a previous.
A number is divisible by $$$3$$$ if and only if sum of its digits is divisible by $$$3$$$. So the task is to find the shortest suffix of $$$s[0 \dots i-1]$$$ with sum of digits divisible by $$$3$$$. If such suffix is $$$s[j \dots i-1]$$$ then $$$s[0 \dots j-1]$$$ and $$$s[0 \dots i-1]$$$ have the same remainder of sum of digits modulo $$$3$$$.
Let's maintain $$$fin[0 \dots 2]$$$ — array of the length $$$3$$$, where $$$fin[r]$$$ is the length of the longest processed prefix with sum of digits equal to $$$r$$$ modulo $$$3$$$. Use $$$fin[r]=-1$$$ if there is no such prefix. It is easy to see that $$$j=fin[r]$$$ where $$$r$$$ is the sum of digits on the $$$i$$$-th prefix modulo $$$3$$$.
So to find the maximal $$$j \le i-1$$$ that substring $$$s[j \dots i-1]$$$ is divisible by $$$3$$$, just check that $$$fin[r] \ne -1$$$ and use $$$j=fin[r]$$$, where $$$r$$$ is the sum of digits on the $$$i$$$-th prefix modulo $$$3$$$.
It means that to handle case that the last digit belongs to divisible by $$$3$$$ segment, you should try to update $$$z[i]$$$ with value $$$z[fin[r]] + 1$$$. In other words, just do if (fin[r] != -1) z[i] = max(z[i], z[fin[r]] + 1).
Sequentially calculating the values of $$$z [0 \dots n] $$$, we obtain a linear $$$O(n)$$$ solution.