Akshit312's blog

Help needed with a ques asked in Hackerearth hiring challenge
By Akshit312, 4 years ago, In English

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

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Use stringBuilder to store answer. Got accepted

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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).

→ Reply