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

×

DIVSET - Editorial

2
3

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.

This question is marked "community wiki".

asked 29 Jul, 22:41

arpa's gravatar image

5★arpa
4916
accept rate: 0%

edited 31 Jul, 22:02


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.

link

answered 30 Jul, 18:18

h_bar's gravatar image

5★h_bar
422
accept rate: 0%

edited 30 Jul, 18:41

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, 18:28) h_bar5★

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

(01 Aug, 19:00) drajingo5★

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...:)

link

answered 30 Jul, 00:58

vijju123's gravatar image

5★vijju123 ♦
9.8k213
accept rate: 18%

edited 30 Jul, 00:59

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, 06:02) abhikalpu_1233★

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, 06:20) abhikalpu_1233★

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

(30 Jul, 10:11) vijju123 ♦5★

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

link

answered 30 Jul, 01:58

beginner_1111's gravatar image

0★beginner_1111
706
accept rate: 0%

see my comment in viju123's answer.

(30 Jul, 06:22) abhikalpu_1233★

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

link

answered 30 Jul, 10:19

abizerl123's gravatar image

4★abizerl123
1
accept rate: 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.

link

answered 30 Jul, 16:40

aditya1701's gravatar image

5★aditya1701
11
accept rate: 0%

edited 30 Jul, 16:42

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

link

answered 02 Aug, 22:02

pk301's gravatar image

2★pk301
936
accept rate: 6%

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, 18:40) adkroxx7★

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

(04 Aug, 16:57) pk3012★

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.

link

answered 03 Aug, 23:05

deepcpp's gravatar image

3★deepcpp
562
accept rate: 42%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,590
×594
×104
×15

question asked: 29 Jul, 22:41

question was seen: 1,037 times

last updated: 03 Aug, 23:05