I am unable to understand YET ANOTHER PARTITION PROBLEM. Please help!

This is the question link.
https://www.codechef.com/LRNDSA03/problems/EXUNC

In the explanation part, I can see an array S with some values. From how these values came from? I’m not clear with the question.

It’s all given in the problem statement. Once you split the array into subarrays, S_i refers to the index of the subarray i_{th} element belongs to. So supposing you are given [1, 3, 9, 4, 16, 5] as your input array, S = [1, 1, 1, 2, 2, 3], because 1 divides 3, and 3 divides 9 so they belong to the first subarray. Then 4 divides 16 so those two belong to the second subarray, and finally 5 has no descendant so it belongs to its own subarray (the 3rd one). This is the only doubt I could see you having.

Yup. Got it! Thanx a lot.

1 Like