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[i])){
		vec[nw].push_back(a[i]);
		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.

4 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:

1 Like

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[i][0](the smallest value in vector i) as small as possible for each i and then tried to make Vector[i][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[i][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

1 Like

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.

1 Like

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?

1 Like

@arpa can you please explain the logic behind it because I did not understood anything from both editorial and editorial discussion.

Infinity is the maximum value of the data type you are taking, like for int it is INT_MAX, for long int it is LONG_MAX. So, here we need to multiply c to the last element of one of the vector in the array hence its product if greater than inf can’t be stored and used for compairing with any other element which is less than inf.

1 Like