I saw this question in one of the Hackerearth hiring challenges which ended yesterday. Can someone please share there approach if was able to solve it completely. Any help will be appreciated.

Link to image: https://i.postimg.cc/jS82XGnb/AR.jpg

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

I saw this question in one of the Hackerearth hiring challenges which ended yesterday. Can someone please share there approach if was able to solve it completely. Any help will be appreciated.

Link to image: https://i.postimg.cc/jS82XGnb/AR.jpg

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 15:37:10 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

This contest was over so here we go:- precomputaion:- store smallest prime factor for each number from one to 1000000 let call this sm(x)

1) first solve a(x) for all x 1 to 1000000.

how?--> using above sm(x) and using totient function logic

2) Using the sieve logic calculate b(x) for each x hint if(i divide x then add a[i] to b[x])

3) again using the logic of sieve calculate c[x] using b[x] hint let t= b[x] divide t by sm[t] until t=1. and calculate number of iteration.

4) for d(x) just use the prefix sum

Yes sir , I tried but it was getting tle in Java

I did the same using stringbuilder to append answer paseed

Thanks a lot for sharing your approach. I understood now.

Actually were you able to score full marks in this question? Because I tried simply printing the input in Java but still was getting TLE for 9/10 test cases. Any idea why?

I myself tried first time in java, I was getting tle too, even having logic of n logn,but I used StringBuilder Class, and append all answer to string and print all at once, and this reduced time from 4s to 0.6s.

Use stringBuilder to store answer. Got accepted

If u notice B(x) = x,so using A and B is useless, then C(x) is sum of exponent of each prime in factorisation of x, and D(x) is prefix sum of C(x).

I see :)