CIEL8STR - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Let S[a…b] denote the substring from a-th character to b-th character of S.

One of the solutions for this problem is to use the fact that 1000 is multiple of 8. Let consider the number of the integers **S[i**…digit] mod 8 = 0 for all i. This number can be calculated as following:

  • count := 0.
  • If S[digit] mod 8 = 0 and S[digit] ≠ 0, count := count + 1.
  • If S[digit-1…digit] mod 8 = 0 and S[digit-1] ≠ 0, count := count + 1.
  • If S[digit-2…digit] mod 8 = 0, count := count + the number of non-zero digits in S[1…digit-2].

Therefore, at first, calculate the number of non-zero digits in S[1…i], for all i, then this problem can be solved with O(|S|) time.
This problem also can be solved by using DP (Dynamic Programming). Let dp[digit][num] = the number of the integers **S[i**…digit] mod 8 = num for all i. Then dp[digit+1][aft] = (sum of dp[digit][bef]) + a, where (10 * aft + S[digit+1]) mod 8 = bef, and if aft = S[digit+1] ≠ 0, a = 1, otherwise a=0. Note that this algorithm will work for finding the number of the numbers multiple of 7, for example.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2

I have understood both setter and tester solutions. They both use the fact that 1000 is multiple of 8. But still I cannot figure out why and how this is working …any help will be appreciated . Thanks .

3

just take any no

let it is abcd=1000a+100b+10c+d

even this fact is used for the finding division condition for every no

just like for three
xyz=100x+10y+z=99x+9y+(x+y+z);

we know that 99,9 are divisible for 3 , one thing need to be taken care of is if x+y+z is divisible by 3

and we all know this fact the any no whose sum of digits are divisible by 3 , is divisible by 3
and in this manner you can find condition for any no

1 Like
4

I haven’t understood how the DP is used here.I have understood the setter solution.They Good used a simple and basic approach and used the fact that 1000 is multiple of 8.again why use DP??

5

Thanks man !!! I got it :slight_smile: