Day 27 | Solving Div3 F as a beginner | C++

Today we will learn to solve the Div3 Round 820's F as beginners. We will learn the technique and then go ahead and solve it.

There are a few concepts that we need to know before we attempt the problem

Modular Mathematics

You know that % sign finds remainder, right? The correct term for this is the modulus operator.

Sometimes it's not a very wise decision to do the following - (A + B) % M

Reason - Let's say we are storing in 64-bit integer capacity and A = LLONG_MAX, B = 10

A+B will overflow, and we will get a wrong answer Just try by yourself

Set A = LLONG_MAX, B = 10, and M = LLONG_MAX,

The output should be 10

What we can do is follow these

(A + B) % M = (A%M + B%M) % M

(A x B) % M = (A%M x B%M) % M

(A - B) % M = (A%M - B%M + M) % M

Prefix Arrays

Suppose you have an array and have to answer queries like what is the sum in index range l to r, will you run a loop from l to r? This will make each query run in O(N) time and complete the program in O(Q*N) time, which will not be good for large values of Q and N

What we can do is use an array trick called prefix arrays

Consider

S[i] = A[0] + A[1] + ... + A[i] // that is sum from index 0 to i

Now we want to find the sum of the range L, R

Ans = A[L] + A[L+1] + ... + A[R]

We can write this as (by adding and subtracting extra elements from index 0 to L-1)

Ans = A[0] + A[1] + ... + A[R] - A[0] - A[1] - ... - A[L-1]

If we notice we can write it as

Ans = S[R] - S[L-1]

Thus if we store prefix sums, we can answer these queries in O(1) time

Let's solve this problem here for a little practice

#include<iostream>
#include<climits>

using namespace std;

const int N = 2e5 + 10;
long long pref[N];
int arr[N];

int main(){
    int n,q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)cin >> arr[i]; 
    for(int i = 1; i <= n; i++)pref[i] = pref[i-1] + arr[i];
    while(q--){
        int a,b;
        cin >> a >> b;
        cout << pref[b] - pref[a-1] << "\n";
    } 
}

Mathematical Properties of 3 and 9-

1. A number X is divisible by 3 (or 9) if the sum of its digits is divisible by 3 (or 9)

2. A number X modulo 3 (or 9) [remainder after division by 3 (or 9)] is equal to the sum of its digit modulo 3 (or 9)

Let's start from here

[v(L1,L1+w-1) x v(l1,r1) + v(L2, L2+w-1) ] % 9 = ki

using modulo math

[v(L1,L1+w-1) % 9 x v(l1,r1)%9 + v(L2, L2+w-1)%9 ] % 9 = ki

So we don't care about the actual value of v but only modulo 9 value

So we need to find a way to calculate v(start, end) % 9

v(start, end) % 9 will be the sum of digits from start to end modulo 9

We solved finding sum in range using prefix arrays.

We can store it like this

    string s;
    cin >> s;
    for(char& i: s)i-='0'; //string is char array, using it like int array 
    pref[0] = s[0] % 9;
    for(int i = 1; i < s.size(); i++)
        pref[i] = (pref[i-1] + s[i]) % 9;

We can query it like this

int getSumMod9(int l, int r){
    int ans = pref[r];
    if(l > 0)ans -= pref[l-1];
    ans = (ans + 9) % 9;
    return ans;
}

Now Notice that W is fixed, thus there will be limited values L1 and L2.

Let's solve this equation now

[v(L1,L1+w-1) % 9 x v(l1,r1)%9 + v(L2, L2+w-1)%9 ] % 9 = ki

v(L2, L2+w-1) % 9 = ki - [v(L1, L1-w-1) * v(li,ri)]

For each query, there are two unknowns v(L1, L1-w-1)%9 and v(L2, L2-w-1)%9

But if we assume the value of one (since values are modulo 9, they will be something between 0-8)

I tried for all values of v(L1, L1-w-1) since it was easier according to the equation.

Once we have values of both v(L1, L1-w-1)%9 and v(L2, L2-w-1)%9,

Then we can find the smallest L1 and L2 which satisfies these values

To make it faster we store indices for all modulo values in advance like this

 for(int i = 0; i + w - 1 < s.size(); i++){
        int l = i, r = i + w - 1;
        int val = getSumMod9(l,r);
        mp[val].push_back(i);
    }

Then we can use these values to find answers as discussed above like this for queries

int l,r,k;
cin >> l >> r >> k;
int val_l_r = getSumMod9(l-1,r-1); //Because l,r in query is 1-indexed
pair<int,int> ans = {INT_MAX, INT_MAX};
for(int L1 = 0; L1 < 9; L1++){
    if(mp.find(L1) == mp.end())continue;
    int left_product = ( val_l_r * L1 ) % 9;
    int L2 = (k%9 - left_product + 9) % 9;
    if(L1 == L2){
        if(mp[L1].size() > 1)
            ans = min(ans, {mp[L1][0] + 1,mp[L1][1] + 1});
    }else if(mp.find(L2) != mp.end()){
        ans = min(ans, {mp[L1][0] + 1,mp[L2][0]+1});
    }
}
if(ans.first == INT_MAX)cout << "-1 -1\n";
else cout << ans.first << " " << ans.second << "\n";

You can find all these steps combined and solve the problem here - Submission

Please like and share my posts if they are helpful.