You have given me an idea. Thanks. Now i understand 
1 Like
@galencolin @anon49701446 help me in this i tried two approach -
-
Precompute divisiors of all number from 1 to 10^6 and do same thing as @anon49701446 said (GOT TLE)
-
Instead of precompute find out divisiors of each element at runtime and do same thing as @anon49701446 said (got 25 marks)
#include <bits/stdc++.h>
using namespace std;
vector<int>all_div[100001];
void alldivisors(){
for(int i=1;i<=100000;++i){
for(int j=i;j<=100000;j+=i)
all_div[j].push_back(i);
}
}
int main() {
alldivisors();
int n;
cin>>n;
int a[n];
int b[n]={0};
map<int,vector<int>>mp;
for(int i=0;i<n;i++){
cin>>a[i];
mp[a[i]].push_back(i);
}
for(int i=0;i<n;i++){
for(auto xt : all_div[a[i]]){
if(mp.find(xt)!=mp.end()){
for(auto xr : mp[xt]){
if(xr>i){
b[xr]++;
}
}
}
}
}
for(int i=0;i<n;i++)cout<<b[i]<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
int b[n]={0};
unordered_map<int,vector<int>>mp;
for(int i=0;i<n;i++){
cin>>a[i];
mp[a[i]].push_back(i);
}
for(int i=0;i<n;i++){
int val = a[i];
for(int j=1;j*j<=val;j++){
if(val%j==0){
if(mp.find(j)!=mp.end()){
for(auto xr : mp[j]){
if(xr>i){
b[xr]++;
}
}
}
if(j!=val/j and mp.find(val/j)!=mp.end()){
for(auto xr : mp[val/j]){
if(xr>i){
b[xr]++;
}
}
}
}
}
}
for(int i=0;i<n;i++)cout<<b[i]<<endl;
return 0;
}
- The first problem is that you’re only doing divisors up to 10^5
- Try a testcase with 5 \cdot 10^4 of 2 and 5 \cdot 10^4 of 1.
The solution by @anon49701446 will also fail for a case like that, unless they meant something else, because that makes it O(n^2) to update each index.
Let’s instead do the opposite of the opposite, and maintain the answer for all numbers at once. That is, we’ll know for each number as we go along, “if this array element were x, what would its answer be?”
Consider some element a_i. Any candidate a_j where i will contribute to its answer has to be a divisor of a_i. So let’s keep an array c of size 10^6 + 1, initially filled with 0. Then, sweep to the right, and when encountering an a_i, first take its answer which is c[a_i], then increment the value of c at all divisors of a_i, including itself. Any divisor of a_i to the right of it will now consider a_i as part of its answer.
Complexity is O(10^6\log{10^6} + n \cdot (10^6)^{\frac{1}{3}}) (first part is to find the divisors, second part is because each number x can have around x^\frac{1}{3} divisors).
Means I have to write this for finding divisiors of all elements in NlogN complexity right?
vector<int>all_div[1000001];
void alldivisors(){
for(int i=1;i<=1000000;++i){
for(int j=i;j<=1000000;j+=i)
all_div[j].push_back(i);
}
}
I called alldivisors function and do nothing for main code and it shows TLE …WTH
That code looks right
Uh… no clue why it TLE’s like that, that shouldn’t happen
I wrote this 
#include <bits/stdc++.h>
using namespace std;
vector<int>all_div[1000001];
void alldivisors(){
for(int i=1;i<=1000000;++i){
for(int j=i;j<=1000000;j+=i)
all_div[j].push_back(i);
}
}
int main() {
alldivisors();
int n;
cin>>n;
int a[n];
int b[n]={0};
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++)cout<<b[i]<<endl;
return 0;
}
and got TLE …
Try using fast i/o and '\n' instead of endl
Still TLE
U r from same university from which i shared the link…please tell the solution as contest is organized by u people 
No this is for @rishiikesavan he is from Madras Institute of Technology (same clg which host contest for 2nd year).
1 Like
Oh, sorry for the misunderstanding. I thought you replied to my comment. My bad, again.
1 Like
this code will take more than 1 sec…so most of the ide’s give TLE…
Try submitting in codechef ide itself and know the execution time
If u have better approach or more better AC solution then please tell
It’s concept is similar to October 2k19 long challenge question MSV, solving that first might get you AC.
Thank you very much AC in one go… I also solved in Long but i forgot
void increaseallfac(lli n , lli tot[]){
for(lli i=1;i*i<=n;i++){
if(n%i==0){
if(n/i == i)
tot[i]++;
else{
tot[i]++;
tot[n/i]++;
}
}
}
}
int main(){
fastIO
lli t=1;
//cin>>t;
while(t--){
lli x,n;
cin>>n;
lli a[n];
scanarr(a,n);
lli maxxx = *max_element(a,a+n);
lli tot[maxxx+1]={0};
lli maxi =0;
loop(i,n){
cout<<tot[a[i]]<<endl;
increaseallfac(a[i],tot);
}
}
return 0;
}
@galencolin Firstly i can’t understand your approach but after @ronythakur said this is similar like Oct - long i open my solution and understands what u said and what is the basic thought behind this … Thanks
As it turns out, your code is exactly what my approach was
1 Like
Yeah bro… Thanks I m stucked at this problem since a day … and the most funny part that i already solved in OCT long 
Hi, I’m the author of this problem(in the HackerRank contest, not on Codechef !) . The solution explained by galencolin is indeed the most optimal for this problem. I saw your TLE code and the reason I guess it’s too slow is that you store all the divisors for every integer in the given range. This isn’t necessary. Instead you can save for each integer, the largest prime which divides it and use it to factorize any number in O(log(n)). Then, you can generate all divisors of a number in approximately O(n^(1 / 3)). The worst possible input for this problem would be an array all filled with highly composite numbers(the worst being 720720 with 240 factors). Still, this approach would pass this test case under 0.5 seconds.
1 Like