DIVSET - Editorial

PROBLEM LINK -

Practice

Contest

Author and Editoriallist - AmirReza PoorAkhavan

Tester - MohammadSina Pakseresht

Second Tester - Shayan CheshmJahan

DIFFICULTY

PREREQUISITES

Binary-search

EXPLANATION

We want to find the maximum possible X, such that we can do X steps. Let’s use binary search for finding this value. Now we need function check, such that it returns true if we can make X steps, and false, otherwise.

We can check if we can do X steps using a greedy solution:

Sort the array, get X vectors and set currentVectorIndex = 0 at first. We define a number is addable to some vector if the vector is empty or the last element of the vector is less than or equal to \frac{TheNumber}{c}. In another word, number B is addable to vector V if and only if v.empty() || v.back() * c <= B.

Now start iterating on the array. For each element check if it can be added to the end of currentVectorIndex, if is possible, add it and set currentVectorIndex = currentVectorIndex + 1 \mod X. At any moment if all of the vectors have k elements, break the process and return true. If the iteration finished with a vector with less than k elements, return false.

Psudocode of check function:

int nw = 0;
for (int i = 0; i < n; i ++){
if (vec[nw].size() == k)
return 1;
if (vec[nw].empty() || (vec[nw].back() < inf / c && vec[nw].back() * c <= a*)){
vec[nw].push_back(a*);
nw = (nw + 1) % X;
}
}
return 0;

Proof: It’s obvious that if check(X) returns true, it’s possible to make X steps. For each vector, choose its elements and delete them. There are k elements in each vector and there are X vectors, so you have made X steps obviously.

Also, because we are picking the smallest remaining value each time for currentVectorIndex, if we don’t find an answer, so there is no way to make X steps.

Time complexity: \mathcal{O}(n \log n).

IMPLEMENTATION -

Author’s code - here
Tester’s code - here
Second tester’s code - here.

2 Likes

I am sorry, but WHAT?

I can neither make head nor tail of what you are trying to say. I expected a bit more details…like Why or how are those theories true?

Can somebody please provide an explanation? I will appreciate that…:slight_smile:

Can u please add some more explanation, unable to figure it out ?

Could someone please explain the basic logic from the start? Couldn’t understand the editorial at all, comments didn’t help much.

The Basic Logic here is:
not considering the elements of the array, answer lies between 0 to N/K.
We can use binary search on range [0,N/K] and use check function as mentioned in Editorial above to check the mid value of binary search. If check(x)=true all values<=x is also true , so we check in the range> x+1 for the answer.

To those who are wondering, the greedy approach works because of the following.
Suppose we can take m steps, that is, there are m finite sequences of length k,
\{x_{ij}\}_{j=0}^{k-1} for i=0, \ldots, m-1, such that
c \cdot x_{ij} \le x_{i(j+1)} for all 0 \le i \le m-1 and for all 0 \le j \le k-2. Take all these points and sort them. Let y_i denote the $i$th smallest one for i = 0,\ldots, k\cdot m-1. Construct the sequences \{y_{i+j\cdot m}\}_{j=0}^{k-1} for 0 \le i \le m-1. These are all valid sequences, because there are m+1 points between y_{i+j\cdot m} and y_{i+(j+1)\cdot m} (inclusively), and by the pigeonhole principle, at least two of these, say y_{i_0} and y_{i_1}, come from the same original sequence. Hence
c \cdot y_{i+j\cdot m} \le c \cdot y_{i_0} \le y_{i_1} \le y_{i+j\cdot (m+1)}. Therefore we can consider only these special, “interleaved” sequences.

2 Likes

can anyone please suggest some test case or please check the code where the logic is lacking? http://ideone.com/NXIGZY

Could someone please explain why the greedy algorithm gives the correct answer?

I read h_bar’s comment but I didn’t understand the proof.

Bro, greedily we tried to make the Vector*[0](the smallest value in vector i) as small as possible for each i and then tried to make Vector*[1] as small as possible for each i and so on… . If there exists a answer for some X vectors our algorithm will eventually find it as we are taking the smallest possible value for Vector*[j] also we rest assured that we will not run out of original array elements while doing the algorithm (as greedily we are taking the smallest :wink: ). If there does not exist a answer we will run out of array elements. Hope the above helps :{D

When i am thinking how to crack the problem i thought all the same but taking the largest possible value instead of smallest ;). Btw if you want to dig more technically the problem was asking to decompose a poset into disjoint chains.

see my comment in viju123’s answer.

Okay, I think i am getting the logic. Thanks for taking time out to explain, I appreciate that!! THANKS BUDDY :slight_smile:

Broke some of the formulas, I’ve no idea why (it worked in the preview). The normal size text following * is in the subscript.

Thanks a lot! Greedy solutions without proof of why they work always seem like a mystery.

1
4 2 2
1 2 3 4

Your code outputs 1 for the above case while the answer should be 2.

3 Likes

@adkroxx thanku for viewing my code… :slight_smile:
but sorry for your test case it is giving correct answer… http://ideone.com/sHhL4F

Can anyone tell what is inf in pseudo code above?