I have always been fascinated by the top quality editorials written by the likes of @vijju123 and @ssjgz so I thought I’d try my hand at writing an in-depth editorial / tutorial about a problem I’d solved ( though it might be simple)
This post is mostly intended for those starting out . Feel free to look at the headings and skip directly to the sections that interest you.
Problem Link
https://www.codechef.com/OCT19A/problems/MSV
Problem Statement
You are given a sequence \ A_1 , A_2 .... A_N and for each valid \ i , the star value of element \ A_i is the number of indices \ j \lt i such that \ A_j is divisible by \ Ai .
Understanding the sample test case
Let us take a look at the sample test case provided :
1
7
8 1 28 4 2 6 7
Let us loop through all \ i and try to find the indices \ j \lt i where \ A_j \% A_i == 0
Let us look at the first index \ i = 1 where \ arr[1] = 8 , there are no \ j \lt i here as this is the first element so it’s star value is \ \underline{0}
Now \ i = 2 and \ arr[2] = 1 , there is one index j such that \ j < i 
\ j = 1 , is \ arr[1] = 8 divisible by 1 , yes
so star value for this index is \underline{1}
Now \ i = 3 and \ arr[3] = 28 , there are 2 indices \ j , \ j < i that satisfy \ j < i :
\ j = 1 , is \ arr[1] = 8 divisible by 28 , no
\ j = 2 , is \ arr[2] = 1 divisible by 28 , no
so star value for this index is \underline{0}
Now \ i = 4 , \ arr[4] = 4 , there are 3 indices \ j that satisfy \ j < i :
\ j = 1 , is \ arr[1] = 8 divisible by 4 , yes
\ j = 2 , is \ arr[2] = 1 divisible by 4 , no
\ j = 3 , is \ arr[3] = 28 divisible by 4 , yes
so star value is \underline{2}
Now \ i = 5 , \ arr[5] = 2 , there are 4 indices \ j that satisfy \ j < i :
\ j = 1 , is \ arr[1] = 8 divisible by 2 , yes
\ j = 2 , is \ arr[2] = 1 divisible by 2 , no
\ j = 3 , is \ arr[3] = 28 divisible by 2 , yes
\ j = 4 , is \ arr[4] = 4 divisible by 2 , yes
so star value is \underline{3}
Now \ i = 6 , \ arr[6] = 6 , there are 5 indices \ j that satisfy \ j < i :
\ j = 1 , is \ arr[1] = 8 divisible by 6 , no
\ j = 2 , is \ arr[2] = 1 divisible by 6 , no
\ j = 3 , is \ arr[3] = 28 divisible by 6 , no
\ j = 4 , is \ arr[4] = 4 divisible by 6 , no
\ j = 5 , is \ arr[5] = 2 divisible by 6 , no
so star value is \underline{0}
Now \ i = 7 , \ arr[7] = 7 , there are 6 indices \ j that satisfy \ j < i :
\ j = 1 , is \ arr[1] = 8 divisible by 7 , no
\ j = 2 , is \ arr[2] = 1 divisible by 7 , no
\ j = 3 , is \ arr[3] = 28 divisible by 7 , yes
\ j = 4 , is \ arr[4] = 4 divisible by 7 , no
\ j = 5 , is \ arr[5] = 2 divisible by 7 , no
\ j = 6 , is \ arr[6] = 6 divisible by 7 , no
so star value is \underline{1}
Initial Observations
We see that for every index \ i , there are \ i-1 indices before it so we have that many \ j to look at. Now looking at the constraints , an O(\ n^2 ) solution seems to definitely tle so the expected solution has to have something to do with factors of each element
Brute force
Even though brute force will definitely give tle , I like to code it to get a feel for the problem and also to have something to compare my actual algorithm with
#include <iostream>
using namespace std;
int main() {
int t ;
cin >> t ;
while(t--)
{
int n ;
cin >> n ;
long long int arr[n+1] ;
for(int i=1 ; i<=n ; i++)
cin >> arr[i] ;
int star = 0; //This will compute star value for element at each index
long long int max = -1 ; //This will store max store value
for(int i=1 ; i<=n ; i++) //Processing array element by element
{
star =0 ; //Re-initialising each time :)
for(int j=1 ; j<=i-1 ; j++) // We know there are i-1 possibilities for j from 1.....i-1
{
if(arr[j]%arr[i]==0)
{
star++;
}
}
if(max < star)
max = star ;
}
cout << max << endl;
}
return 0;
}
As expected , it gets partial AC : Here
Optimisations
Now we need to understand that for every \ i , we are finding all \ j such that \ j < i and we are checking if \ A_j mod A_i == 0 . When can this be true ? Only when \ A_i is a factor of \ A_j .
Let us go back to our example
1
7
8 1 28 4 2 6 7
Let us have an array \ count which keeps track of how many times we’ve looked at a particular factor
Here , what are the factors of \ arr[1] = 8 ?
Yep , the factors are \ 1 , 2 , 4 , 8
\ count[1] = 1
\ count[2] = 1
\ count[4] = 1
\ count[8] = 1
We always know that the star value of the first element will be \bold{0} as there are no indices \ j < i if \ i =1
Now let’s look at the second element , \ i = 2 , \ arr[2] = 1 , for this element to compute the star value , we need to look at the value in the count array for that particular element , we see that 1 has appeared once before as a factor of elements in range \ [ 1 , i-1] so star value for this element is \bold{1}
After we compute the star value for this element , we need to update the count array with the current element we are seeing so only one is a factor of 1
\ count[1] = 2
\ count[2] = 1
\ count[4] = 1
\ count[8] = 1
Let’s look at \ i = 3 , arr[3] = 28
for computing the star value of this element , we see it’s count array value which is 0 , so
star value for this element is \bold{0}
Factors of 28 are \ 1 , 2 , 4, 7 , 14 , 28
so
\ count[1] = 3
\ count[2] = 2
\ count[4] = 2
\ count[7] = 1
\ count[8] = 1
\ count[14] = 1
\ count[28] = 1
Now \ i = 4 , arr[4] = 4
Star value = \ count[4] = \bold{2}
Factors of 4 are \ 1 , 2 , 4
\ count[1] = 4
\ count[2] = 3
\ count[4] = 3
\ count[7] = 1
\ count[8] = 1
\ count[14] = 1
\ count[28] = 1
Now for \ i = 5 , arr[5] = 2
Star value = \bold{3} which is \ count[2] and so on , try to complete the rest of the tracing
and see the maximum star value
Summary
The main idea that follows is that to compute the star value of a particular element , we need to look at how many times this element occurs as a factor in the range \ [1 , index-1] because in this question for every \ i we find \ j such that \ j < i and we check if \ A_j \% A_i == 0
All \ j < i is basically \ j = [1 , 2 .... i-1] . For any \ A_i the star value is the count of elements in the range \ [1, ... i-1] which are divisible by \ A_i which reduces the problem to just finding count of factors as when we are at index \ i , we have already looked at \ i-1 elements
Count of factors in \sqrt{n} :
For any \ n if ,
\ a \times b = n
Then ,
\ b = n / a
Let us take \ n = 10 , \sqrt{10} \approx 3
\ 1 \times 10 = 10
\ 2 \times 5 = 10
\ 5 \times 2 = 10
\ 10 \times 1 = 10
As we see , it repeats after a certain point .
(and also observe that \sqrt{n} \times \sqrt{n} )
Basically to enumerate all factors we , Run a loop \ i => 1 .... \sqrt{n}
if \ n \% i == 0 , then \ i is a factor of \ n , so print \ i , what else do we know ?
\ n /i is also a factor so we print \ n/i if \ n/i != i , now for those wondering why the condition is present , take the case of perfect square like \ 25 , when \ i = 5 , \ n/i also is 5 and we do not want duplicates
You made it
Link to AC Submission : Here
I know that this is definitely not the best editorial you’ve seen but please do let me know how you found it , any corrections or clarifications and whether I should do more of these , keep in mind I’m very much a beginner
Thank You
You really explained very well. Explained the naive approach as well as the optimized one. And the test case explaination .
