Also we have x&(x-1) which is equal 0 only when x is a power of two(except x == 0).

The only flaw in the function is that it can't erase first digit of number. So we should feed it with numbers of different sums modulo 3. So sums of these strings are (a₁ + a₂ + sum, a₂ + sum, sum).

Let's notice that if the first digit is 0 modulo 3, then it won't be erased anyway and thus won't affect further number (if we can't make beautiful number of this string, then we won't be able to make it out of any further ones).

So now we only care if a₁ and a₂ are either 1 or 2.
1) If one of them is 1 modulo 3 and the other is 2 modulo 3, then by deleting both of them you will get sum of original number modulo 3.
2) If both of them are the same modulo 3, then check every possible reminder of original sum. If it was 0 modulo 3, then the answer existed anyway. If it was either 1 or 2, then by deleting one or both of this digits you can make sum 0 modulo 3, so the answer will exists, if it existed for original number.

I hope that this I made myself more clear.

Let dp(i,j) denotes the maximum number of digits we will keep from 1 to i, including i and the number they form modulo 3 = j (or you can say the length of longest subtring ends at i and modulo 3 = j).

I will show you how to compute dp(i,0), you can do the same thing with j=1,2 and the special case when s[i]='0'. Let x=s[i] % 3, then dp(i,0) = max(dp(k,y)) + 1 with k = 0..i-1, y + x = 0. To be more detailed, there are 3 cases:

• x=1: dp(i,0) = max(dp(k,2)) + 1 , however if there is no k that dp(k,2) > 0, which means there is no substring before i that modulo 3 = 2, dp(i,0) should equal to 0.

• x=2: dp(i,0) = max(dp(k,1)) + 1 , same as above, if there is no k that dp(k,1) > 0, dp(i,0) should equal to 0.

• x=0: dp(i,0) = max(dp(k,0)) + 1 , this always holds true because if there is no k that dp(k,0) > 0, we can make a new substring starts and also ends at i which has length 1 and modulo 3 = 0.

It's a little bit confusing when explain so you can look at my code here: 25856552

In my code, I add f[i] denotes the length of longest substring which modulo 3 = i and update it continuously. It replaces max(dp(k,y)) above to reduce complexity to O(length(S)). Since this problem required the number after erasing, we have to trace it after dynamic programming.

dp solution for problem C with comments...

One tip in competitive programming is to carefully read the problem statement.

"The first line contains one integer number n (2 ≤ n ≤ 2·105).

The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). All numbers ai are pairwise distinct."

Да, в третьем случае удаляем две цифры с одинаковым остатком по модулю 3, вариантов чуть больше, правда (11, 14, 17, 44, 47, 77, аналогично для 2, 5, 8).

You can find it here

It's done to avoid handling any leading zeros problems.

Well, integer division (as well as modulus) are complex operations, and it's better to get rid of them, if possible. For example, when you write something like (a / b + (a % b ? 1 : 0)), which means a divided by b rounded up, you can replace it with ((a + b — 1) / b), which uses only one division operation and works faster.

UPD: And as for more, you can store the array a as int array instead of long long, and int division is also faster than long long division.

25878153

a1%k==0