MSV - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Shubhankar Bhagwat
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

EASY

PREREQUISITES:

Math, Array manipulation, Number theory

PROBLEM:

Given an array A[1\sim N], the star value of an index i is the number of indices j such that j<i and A[j] is divisible by A[i]. Find the largest value among all star values of 1,2,\dots,N.

QUICK EXPLANATION:

  • Since we only want to find the maximum star value, we only consider the last occurrences of each number, i.e. if A[i]=A[j] and i<j then we don’t need to compute the star value of i.
  • For each A[i], we iterate through its multiples k\cdot A[i], count the number of occurrences of this number in A[1\sim (i-1)], and add them together.
  • Let the maximum number be maxA\le 10^6, then time complexity is O(maxA+\frac{maxA}{2}+\frac{maxA}{3}+\dots+\frac{maxA}{maxA})=O(maxA\cdot\log maxA).

EXPLANATION:

Subtask 1

Here N\le 1000, so we can directly compute the star values of every index i, by iterating through all j<i and checking if each A[j] is a multiple of A[i]. The time complexity is O(N^2).

Subtask 2

The first observation is: if i<j and A[i]=A[j], then the star value of i can’t be larger than the star value of j. Since we only want the maximum star value, there is no need to compute the star value of i.

We scan the array A backwards (i.e. from A[N] to A[1]) to find out which A[i]’ s are themselves’ last occurrences. We keep a table C where C[j]=1 if we’ve already found j in the sub-array A[(i+1)\sim N], and C[j]=0 if not. If C[A[i]]=0, then A[i] is indeed its last occurrence in the array A, and we need to find its star value. Otherwise it’s not its last occurrence and we don’t need to find its star value. Then we mark C[A[i]] as 1.

We can also use pseudocode to describe this procedure:

initially C[i] = 0, for every i.
for i = N downto 1
    if C[A[i]] == 0 then A[i] is its last occurrence
    else A[i] is not its last occurrence
    C[A[i]] = 1

Now we want to compute the star values of the indices i that we marked as “last occurrence”. Let’s scan the array A forwards (i.e. from A[1] to A[N]). Suppose we’re at index i and we want to compute the star value of i. We also maintain an array B[\cdot], where B[j] denotes the number of occurrences of j in the sub-array A[1\sim (i-1)]. Let’s say the maximum value in the array is maxA, then maxA\le 10^6. Let t_i=\lfloor \frac{maxA}{A[i]}\rfloor, we enumerate all t_i multiples of A[i] and sum up their B values. (That is, we compute B[A[i]]+B[2A[i]]+B[3A[i]]+\dots+B[t_iA[i]].) This value is the star value of index i.

The above process can also be described in pseudocode:

for i=1 to N
    if A[i] is the last occurrence of itself in A
        t = maxA / A[i]
        //compute Star-Value[i]
        for j = 1 to t
            Star-Value[i] += B[j * A[i]]
        B[A[i]] += 1 // maintain B

We analyse the time complexity of this algorithm. For every number 1\le a\le maxA, if it’s in the sequence, then we take O(\frac{maxA}{a}) time to compute the star value of its last occurrence. Note that we do nothing on the earlier occurrences of a, therefore even if a appears t(t>1) times in A, we only spend O(\frac{maxA}{a}) time on this number a, rather than O(t\cdot\frac{maxA}{a}) time. Therefore, the time complexity is at most O\left(\sum_{a=1}^{maxA}\frac{maxA}{a}\right)=O\left(maxA+\frac{maxA}{2}+\frac{maxA}{3}+\dots+\frac{maxA}{maxA}\right)=O(maxA\cdot \log maxA). (See Harmonic series.)

ALTERNATE EXPLANATION:

There is an O(n\sqrt{maxA}) solution that runs fast in practice, and computes the star values of every index i.

  • We scan the array A from left to right.
  • We maintain a table s[a] (for a=1,2,\dots,maxA) denoting the number of elements scanned that is the multiple of a.
    • In other words, suppose we just scanned A[i]. Then s[A[i+1]] should be the star value of index i+1.
  • After scanning A[i], we should “add” A[i] into the table s. To be precise, we iterate over all divisors a of A[i], and increase s[a] by 1.

Since every A[i] has O(\sqrt{maxA}) divisors, the total time complexity is O(n\sqrt{maxA}).

Here are some details for people who don’t know how to enumerate the O(\sqrt{A}) divisors of number A quickly.

Iterating divisors

Let’s say we have an integer A and we want to iterate through its divisors. A crucial observation is that: if d is a divisor of A, then A/d is also its divisor, and \min(d,A/d)\le\sqrt{A}. Therefore, for each i\le\sqrt{A}, if A\bmod i=0, we know both i and A/i is a divisor of A. For every divisor d of A,

  • If d\le\sqrt{A}, then d is clearly enumerated in this way;
  • If d>\sqrt{A}, then d is also enumerated by the divisor A/d since A/d<\sqrt{A}.

Hence, A only has O(\sqrt{A}) divisors, and we can find them in O(\sqrt{A}) time.

Hope that the following pseudocode helps you understand it better.

EnumerateDivisors(int A)
  for (i = 1; ; i++)
    if (i * i > A) then break; //only enumerate sqrt(A) numbers
    if (A % i == 0) then
      output i
      output A / i

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) x.size() 
 
ll power(ll x,ll y,ll p) 
{ 
    ll res = 1;      
 
    x = x % p;  
 
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
  
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 
const ll M=1e6+6;
ll LAST[M];
ll A[M];
vector<ll>ad[M];
int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;
	cin>>t;
	while(t--)
	{	
		// cout<<t<<endl;
		ll mx=0,answer=0;
		cin >> n;
		vector<ll>V;
		set<ll>U;
		for(i=1;i<=n;i++)
		{
			cin >> A[i];
			LAST[A[i]]=i;
			U.insert(A[i]);
			mx=max(mx,A[i]);
			ad[A[i]].pb(i);
		}
	 
		for(set<ll>::iterator it=U.begin();it!=U.end();it++)
			V.pb(*it);
		for(i=0;i<V.size();i++)
		{
			ll count_multiples=0;
			for(j=V[i];j<=mx;j+=V[i])
			{
				// cout<<"wge"<<j<<" "<<t<<endl;
				count_multiples+=(lower_bound(all(ad[j]),LAST[V[i]])-ad[j].begin());
			}
			answer=max(answer,count_multiples);
		}
		cout<<answer<<endl;
 
		for(i=1;i<=n;i++)
			ad[A[i]].clear();
	}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}

#define sz 100200
int n, a[sz], cnt[1002000], ans = 0;
bool vis[1002000], good[sz];

void doit() {
  ans = 0;
  memset(good, 0, sizeof good);
  memset(vis, 0, sizeof vis);
  memset(cnt, 0, sizeof cnt);
  gi(n); for (int i = 1; i <= n; i++) gi(a[i]);
  for (int i = n; i; i--) {
    good[i] = !vis[a[i]]; vis[a[i]] = 1;
  }
  for (int i = 1; i <= n; i++) {
    if (good[i]) {
      int star = 0;
      for (int j = a[i]; j <= 1000000; j += a[i])
        star += cnt[j];
      ans = max(ans, star);
    }
    cnt[a[i]]++;
  }
  printf("%d\n", ans);
}

int main() {int t; gi(t); while (t--) doit(); return 0;}
Tester's Alternate Solution
#include <bits/stdc++.h>
using namespace std;

void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}

int a, s[1002000], n, ans, i, j;

void doit() {
  gi(n); ans = 0;
  for (i = 1; i <= n; i++) {
    gi(a);
    ans = max(ans, s[a]);
    for (j = 1; j * j <= a; j++)
      if (a % j == 0) {
        s[j]++;
        if (j * j != a) s[a / j]++;
      }
  }
  cout << ans << endl;
  memset(s, 0, sizeof s);
}

int main() {int t; gi(t); while (t--) doit(); return 0;}
8 Likes

Slightly more readable solution:
https://www.codechef.com/viewsolution/26936376

3 Likes

Got the solution acc. to above
https://www.codechef.com/viewsolution/27380425

Very simple solution. Just calculate all the factors of elements from the left using a hash table and check how many times the number at i is a factor of elements at position j(<i).
This can be done in sqrt(a[i])

Here’s the solution

https://www.codechef.com/viewsolution/27265630

2 Likes

we can also use sieve to get the factors of all numbers less than 10^6
and then when we iterate through the numbers we keep changing the count of all the factors of a number by maintaining an array of size 10^6(don’t use map as maps are slower) and then simply check the value of each number in the count array and take the maximum of all

https://www.codechef.com/viewsolution/27132150

Can anyone explain solution in a simple way? more like HC Verma’s physics :slight_smile:

7 Likes

Let me explain you the solution with an example
n=7
8 1 28 4 2 6 7
Step 1- create an array arr of size of 10^6+1 because ai goes upto 10^6.And initialise a variable ans with min value
Step 2 -for each i going from 0 to n-1 First check if ans<arr[i] if yes than ans=arr[i].after that calculate factors of a[i] and increment the arr[factor]++
Step3-The index of arr with max value will be the answer…
lets explain with an example
8 1 28 4 2 6 7
for i=0 a[0]=8 ans=INT_MIN so it will become 0 as explained in step 2 factors are 1,2,4 will be incremented by 1
for i=1 a[1]=1 ans=0 it will be updated as ans=1 because(arr[1]=1 as updated in i=0) and now factor of 1 is 1 it will be updated as 2 but but it won’t matter as you will see in further steps
for i=2 a[2]=28 ans=1 it will remain as it is factors are 1,2,4,7 so all will be updated .
The quesion arises how to take care of that i<j…
The most crucial part is when we calculate the factor and if some factor is previous to that value then it wont matter like if we have 2 8 4 and i=2 factor of 8 are 2 and 4 so we will update both arr[2] and arr[4] but as we are progressing from left to right arr[2] wouldnot matter
codelink
https://www.codechef.com/viewsolution/27389085

2 Likes

Short and concise python code.
It can be made more efficient by terminating program when star become greater than (N-i+1)…
(https://www.codechef.com/viewsolution/27054771)

1 Like

Why I am getting TLE in O(n.sqrt(maxA)) approach in Python.

https://www.codechef.com/viewsolution/27169662

My approach was rather different. Divide the values into blocks with an equal range, by square-root decomposition. Store the index in the original array with each value in each block. Values in each block need to be compared with others in the same block to see if they are equal, and usually with only some of the other blocks to see if they divide into the values there. With zero-indexing of the blocks, for i > 1 values in block ‘i’ are checked to see if they divide into values in blocks m * i <= j < m* (i+1), for each ‘m’ until there are no more blocks.

Further points to note are that (a) if any value has already been divided by another number to its right. or (b) its index is less than maximum star value so far, its star value need not be checked as it is not a candidate for maximum star value.

With this approach I got 100 points in 0.06 seconds. My solution is at https://www.codechef.com/viewsolution/27271708

During testing I found that with a single test case with 100000 values randomly distributed between 1 and 1000000 the method took about 6 seconds, excluding time for reading and writing data. If most of the numbers were in few of the lower blocks but with a large maximum value, the method would be even slower. So I guess I was lucky that the test cases were not designed to catch this method out.

3 Likes

Explanation of alternate solution in a very easy to understand language :slight_smile:

Lets say that the element under consideration is

A[i]

Using factorization we will find all the distinct factors of all the elements before A[i] namely A[0], A[1], … ,A[i-1]

Lets keep an array named count[100005] that will keep count of number of times a factor has appeared.

Now we have all the factors of all the elements before A[i] and if A[i] would have been a factor of elements before A[i] then it would have been reflected in the count array that we are maintaining to count how many times a factor occurs.

Now we simply need to find the maximum value in the array count.

Please comment if I am missing something.

Exactly, but this should not work for a testcase with 10e5 elements with each one being 10e6. It should be a timeout based on the constraints right?

https://www.codechef.com/viewsolution/27391997
Mine got an AC somehow

@r_64 / @admin / @harrykp / @all : Why @harrykp 's solution(https://www.codechef.com/viewsolution/27054771) got 100pts on AC why not the following different types of my solution :frowning:

  1. https://www.codechef.com/viewsolution/27403611
  2. https://www.codechef.com/viewsolution/27402102
  3. https://www.codechef.com/viewsolution/27401885
  4. https://www.codechef.com/viewsolution/27401685

@admin will you please help on this is there anything wrong with compiler or is my solution wrong if my solution wrong what about the editorial?

Please help on this, solution can be appreciated :slight_smile:

The following is my 10 lines of code C++14 dynamic-programming solution.

https://www.codechef.com/viewsolution/26989154

The array int dp[10^{6}+1] is used to store the count of divisors 1 \le d \le 10^{6} for all previous subsequene items A_{j}, 1 \le j <i, in the i-th iteration. Initially, dp[d] = 0 for all d. The maximum star value can be computed iteratively as \max \limits_{i=1}^{n} dp[A_{i}]

2 Likes

Brother…you get TLE hence your approach is OK…you just need to optimise it.
I review your code https://www.codechef.com/viewsolution/27403611
You are calling max function in loop 2 everytime even it is not needed…Max should be called after execution of loop 2.
I think for test cases in which loop 2 runs frequently it generates TLE…
you can re submit your code again …Of course it will not give you point…
But you can check.
If the condition remains same…Update me and then @admin will take care of it.

Hope your code runs

https://www.codechef.com/viewsolution/27404789 Same TLE :frowning_face:

Try 2 loop inside if h[i]==0…
i knew it is a hit and trial.
Honestly, i couldn’t get the main reason …why your code isn’t running successfully.
Hope,expertise will look into this matter.

Three more test cases has been added and this solution is giving TLE for those 3 test cases.

1 Like

Yes…, My bad :sweat_smile:

Why is it happening? I think the constraints are still the same.