ROCDIV - Editorial

Practice
ROC Finals

Author: Nachiket Kanore
Tester: Ajinkya Kharosekar
Editorialist: Ajinkya Kharosekar

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given an N-digit number X (without leading zeroes) Along with that a positive integer K is given.

Find the number of ways to cut X into two integers (non-empty) such that both of them are divisibly by K.

EXPLANATION:

Each valid part will be non-empty prefix and suffix of original number

So, consider all prefixes and suffixes and computer their value % k
For each i = [1,n-1] check if both values prefix[i] and suffix[i+1] are zero,
and increment count.

Solutions:

Setter's Solution
            #include <iostream>
            #include <cstdio>
            #include <cstdlib>
            #include <algorithm>
            #include <cmath>
            #include <vector>
            #include <cassert>
            #include <string>
            #include <cstring>
            
            #define int long long
            #define pb push_back
            #define ALL(x) (x).begin(),(x).end()
            #define sz(x) (int)(x.size())
            #define FOR(i,L,R) for(int i = (L); i <= (R); i++)
            using namespace std;
            
            template<class T> bool cmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
            template<class T> bool cmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
            
            const int N = 2e5 + 5, inf = 1e18;
            
            int power(int a, int b, int mod){
                int ret = 1;
                a %= mod;
                while(b > 0){
                    if(b % 2)
                        ret = ret * a % mod;
                    b /= 2;
                    a = a * a % mod;
                }
                return ret;
            }
            
            
            int32_t main() {
                ios::sync_with_stdio(0); cin.tie(0);
                
                int T;
                cin >> T;
                while (T--) {
                    string s;
                    int n, k;
                    cin >> n >> k;
                    cin >> s;	s = " " + s;
                    int ans = 0;
                    vector<int> suff(n+2);
                    int ten = 1;
            
                    for (int i = n; i; i--) {
                        int dig = s[i] - '0';
                        suff[i] = (dig * ten + suff[i+1]) % k;
                        ten = (ten * 10) % k;
                    }
            
                    int left = 0;
                    FOR (i,1,n-1) {
                        int dig = s[i] - '0';
                        left = (10 * left + dig) % k;
                        ans += left == 0 && suff[i+1] == 0;
                    }
                    cout << ans << '\n';
                }
            }
Tester's Solution
            #include <iostream>
            #include <cstdio>
            #include <cstdlib>
            #include <algorithm>
            #include <cmath>
            #include <vector>
            #include <cassert>
            #include <string>
            #include <cstring>
            
            #define int long long
            #define pb push_back
            #define ALL(x) (x).begin(),(x).end()
            #define sz(x) (int)(x.size())
            #define FOR(i,L,R) for(int i = (L); i <= (R); i++)
            using namespace std;
            
            template<class T> bool cmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
            template<class T> bool cmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
            
            const int N = 2e5 + 5, inf = 1e18;
            
            int power(int a, int b, int mod){
                int ret = 1;
                a %= mod;
                while(b > 0){
                    if(b % 2)
                        ret = ret * a % mod;
                    b /= 2;
                    a = a * a % mod;
                }
                return ret;
            }
            
            
            int32_t main() {
                ios::sync_with_stdio(0); cin.tie(0);
                
                int T;
                cin >> T;
                while (T--) {
                    string s;
                    int n, k;
                    cin >> n >> k;
                    cin >> s;	s = " " + s;
                    int ans = 0;
                    vector<int> suff(n+2);
                    int ten = 1;
            
                    for (int i = n; i; i--) {
                        int dig = s[i] - '0';
                        suff[i] = (dig * ten + suff[i+1]) % k;
                        ten = (ten * 10) % k;
                    }
            
                    int left = 0;
                    FOR (i,1,n-1) {
                        int dig = s[i] - '0';
                        left = (10 * left + dig) % k;
                        ans += left == 0 && suff[i+1] == 0;
                    }
                    cout << ans << '\n';
                }
            }
1 Like

thanks