Please read the new rule regarding the restriction on the use of AI tools. ×

zoro2000's blog

By zoro2000, history, 11 months ago, In English

Question: Given an array of N elements We want to divide this into K subarrays ( non-intersecting) such that the total cost is minimum , total cost is sum of cost of all subarrays

Now for a subarray the cost is defined as the no of unordered pairs of elements which have different indices and their values are the same , i.e for array A , i < j && A[i] = A[j]

We want to output the total cost .

Constraints .

2 <= N <= 1e5 .

1 <= A[i] <= N .

2 <= K <= min(N,20) .

Eg : [ 1 , 1 , 2 , 2 , 1 ] and k = 2

Most optimal way is [ 1, 1, 2 ] [2,1] where the cost of subarray one is 1 , subarray 2 is 0

So total cost = 1 + 0 = 1

My Approach .

Seeing the constraints I tried applying a DP of index , k however I was soon faced in a issue where I needed to find the (no.of pairs for a given range l , r) in such a way that it does not exceed the time limit

How to approach such questions

PS : Thank you in advance :)

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give the link to this problem ?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach (Recursive DP)

f(i, j) -> minimum cost to divide first i elements into j groups.

f(i, j) = min(f(i + 1, j), f(i + 1, j + 1) + cost[j]) ;

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did not get it exactly can you please tell me more