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

×

CHEFTMA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

Greedy, In-built data structures

PROBLEM:

EXPLANATION:

Subtask 1
Given constraints are very small. Thus, a brute force solution can easily work. Trying all possible buttons in all possible ways and noting the minimum over all such arrangements gives the answer. The total complexity of this approach is $\mathcal{O}(2^N*2^M*2^K)$. This will pass under the given constraints.

Subtask 2
There are many observations to make here which reduce this problem substantially:

  • For the given $A[i]$ and $B[i]$ values, we are only interested in the value $A[i]-B[i]$. Basically, we can modify each $A[i]$ to $A[i]-B[i]$. From this point onwards in this editorial, array $A$ is assumed to be containing the modified values, i.e., $A[i]-B[i]$.

  • The black and white buttons fundamentally do the same things when dealing with the modified values of the array $A$. Thus, we put all the values from the two arrays, $C$ and $D$, in a common multiset called $buttons$. A multiset is a set which allows duplicates to exist.

Now, before we go on to the formal algorithm, let's think of a smaller problem. Let's take two values from the array $A$ (just reminding, the values aren't the ones which were taken as input) $A[i]$ and $A[j]$. Let's assume that $A[j] > A[i]$. Now, let us take two values $x$ and $y$ from the $buttons$ multiset. Let's say that $x$ < $y$ < $A[j]$. Which button should be use for $A[j]$ then. Intuition tells us that it is beneficial to use $y$. This is for two reasons. First one is that using $y$ allows us to complete more number of tasks on the $j^{th}$ day than $x$ using why would. Second reason is that assume $y$ > $A[i]$ and $x$ < $A[i]$. If we use $x$ on $A[j]$, we won't be able to use $y$ on $A[i]$. A better strategy is to use $x$ on $A[i]$ and $y$ on $A[j]$. What if both $x$ and $y$ were less than $A[i]$. Then we could use either of buttons on $A[i]$ and the other on $A[j]$. This is because we will anyway be reducing the same number of tasks from the sum of total incomplete tasks.

This gives us our greedy algorithm: for a particular value $A[i]$, use the button $x$ such that $x$ hasn't been used up till now and $x$ is the largest value less than or equal to $A[i]$ in the $buttons$ multiset. Now, the incomplete tasks left will be $A[i] - x$. Add this to the accumulator variable which is to be finally returned as the answer. $x$ is removed from the multiset since one button can't be used twice. The proof of this greedy algorithm has been given above and can be more formally stated as "Exchange Argument". You can find more about proofs of greedy algorithms here.

The multiset data structure can be found in almost all the major programming langauges. Writing one on your own requires knowledge of balanced binary search trees. All operations in a multiset are in order $\mathcal{O}(\log N)$.

The editorialist's program follows the editorial. Please see for implementation details.

OPTIMAL COMPLEXITY:

$\mathcal{O}(N\log N)$ per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 01 Jan '16, 16:27

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156281
accept rate: 4%

edited 10 Mar '16, 13:22

admin's gravatar image

0★admin ♦♦
15.9k347484508

Seriously? Optimal complexity is suggested to be O(NlgN) ? It can be solved in O(N) without any complex data-structure but just arrays.

(12 Jan '16, 10:13) akumar33★

Yes array does it. But you do need to sort it. Can you do this in O(n)?

(14 Jan '16, 13:47) s1d_35★

NO requirement of any data structures like multiset or balanced binary trees. Just an algorithm, also called "2-pointer algorithm" which reduces the complexity from O(n^2) to O(n). Here is a link to a tutorial on 2-pointer algorithm (link).

First just sort the initial difference array in descending order and find the most suitable candidate for it in the buttons array using binary search or just linear search as well. Then using 2 pointer concept, iterate over the buttons and difference array. Here is a link to my AC solution.

Another problem on 2 pointer concept is Codeforces problem

link

answered 11 Jan '16, 18:29

likecs's gravatar image

6★likecs
3.1k636
accept rate: 9%

I think you sorted it. That's O(nlogn). And yes arrays are way easier

(14 Jan '16, 13:46) s1d_35★

Implemented the same $O(nlogn)$ solution as in the editorial.

Code

link

answered 11 Jan '16, 19:36

arvindnair's gravatar image

5★arvindnair
112
accept rate: 0%

link

answered 12 Jan '16, 11:03

shadek's gravatar image

3★shadek
10913
accept rate: 0%

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
×780
×716
×222
×106

question asked: 01 Jan '16, 16:27

question was seen: 2,963 times

last updated: 10 Mar '16, 13:22