You are not logged in. Please login at www.codechef.com to post your questions!

×

# DIVSET - Editorial

 2 3 PROBLEM LINK - 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. This question is marked "community wiki". asked 29 Jul '17, 22:41 6★arpa 49●2●7 accept rate: 0%

 2 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. answered 30 Jul '17, 18:18 4★h_bar 42●2 accept rate: 0% Broke some of the formulas, I've no idea why (it worked in the preview). The normal size text following * is in the subscript. (30 Jul '17, 18:28) h_bar4★ Thanks a lot! Greedy solutions without proof of why they work always seem like a mystery. (01 Aug '17, 19:00) drajingo4★
 0 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...:) answered 30 Jul '17, 00:58 15.2k●1●18●59 accept rate: 18% 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 ;) ). If there does not exist a answer we will run out of array elements. Hope the above helps :{D (30 Jul '17, 06:02) 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. (30 Jul '17, 06:20) Okay, I think i am getting the logic. Thanks for taking time out to explain, I appreciate that!! THANKS BUDDY :) (30 Jul '17, 10:11)
 0 Can u please add some more explanation, unable to figure it out ? answered 30 Jul '17, 01:58 240●1●10 accept rate: 13% see my comment in viju123's answer. (30 Jul '17, 06:22)
 0 Could someone please explain the basic logic from the start? Couldn't understand the editorial at all, comments didn't help much. answered 30 Jul '17, 10:19 46●2 accept rate: 33%
 0 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. answered 30 Jul '17, 16:40 1●1 accept rate: 0%
 0 can anyone please suggest some test case or please check the code where the logic is lacking? http://ideone.com/NXIGZY answered 02 Aug '17, 22:02 3★pk301 627●10 accept rate: 16% 3 1 4 2 2 1 2 3 4 Your code outputs 1 for the above case while the answer should be 2. (03 Aug '17, 18:40) adkroxx6★ @adkroxx thanku for viewing my code.. :) but sorry for your test case it is giving correct answer.. http://ideone.com/sHhL4F (04 Aug '17, 16:57) pk3013★
 0 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. answered 03 Aug '17, 23:05 4★deepcpp 56●2 accept rate: 37%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,490
×1,023
×108
×15

question asked: 29 Jul '17, 22:41

question was seen: 2,145 times

last updated: 03 Aug '17, 23:05