algoskipper's blog

DE Shaw OA questoin- Mix Music
By algoskipper, history, 2 days ago, In English

DE Shaw latest OA question,
Question

constraint are n=10^5 so cant go for N^2 and k<=10^9

Given an array of music type and int k
We have to return cost of mixing all types of music

mix(a,b)=k/(gcd(lcm(a,b),k))
eg: 4 5 6 , k=12
Mixing of 4,6 costs k/(gcd(lcm(4,6),k)
So ans will be mix(4,4),mix(5,5),mix(6,6),mix(4,5),mix(5,4),mix(4,6),mix(6,4),mix(5,6),mix(6,5)

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's hope you aren't asking this in the middle of the test.

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

    definetly no, this is question from july test

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

      What are the constraints on the type of music ?

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

        a[i]>=0&&<=10^9

        → Reply
»
2 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

sorry my previous comment was wrong as i misread the problem
mix(a, b) = k / gcd(lcm(a, b), k) we can rewrite it as
= (k * lcm(lcm(a, b), k) / (lcm(a, b) * k)
= lcm(a, b, k) / lcm(a, b)
= k * gcd(a, b) / gcd(gcd(a, b), k)
= lcm(gcd(a, b), k)
now assuming a[i] <= 1e5 you can calculate for x how many times it appears as gcd.
Then contribution of x will lcm(x, k) * cnt[x]
link to comment

→ Reply