PROBLEM LINK:
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;}
