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

×

COINPART - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Pre-computation, Dynamic Programming (Knapsack DP, to be precise), Mathematical proofs.

PROBLEM:

Given $N$ numbers in array $V$, and two sum variables $A$ and $B$, we iterate over numbers from left to right, if $A \leq B$, we add current number to $A$, otherwise we add current number to $B$.

Our aim is to find a permutation of numbers, such that $A$ is maximized. If multiple permutation satisfies, print any.

QUICK EXPLANATION

  • For every element, say at position $i$, let us assume it will be the element last added to $A$. For that to happen, we need $A \leq B$ before adding this element. Find maximum value of $A$, being $A \leq B$.
  • Say maximum value found is $X$, then if ith element is last element added to $A$, then maximum value of $A$ we can achieve is $X+v[i]$. Find $X$ for every position, and thus, find the element, which will be added last to $A$.
  • Find subset of all numbers, except at chosen position, which sums to $X$. Put all this numbers in first set, and all other numbers in another set. Now, make permutation of these elements, taking any element from first set, if $cA \leq cB$ and add to $cA$. Otherwise take any element from second set and add it to $cB$. Make sure to add chosen element to $cA$ only when first set is empty. $cA$ and $cB$ denote current A and B respectively.

EXPLANATION

This problem too, has a relatively simple though hard to prove solution. So, whenever i mention observation, try to prove it yourself first. We will first find maximum possible value of $A$, constructing permutation is shown later.

We can see, that number is added to $A$ if $A-B \leq 0$, otherwise number is added to $B$.

First observation is, that at the end, $A-B \leq X$ where $X$ is the element last added. If $X$ is not last number to be added, Just before adding the last element, $A-B \leq 0$ has to hold.

Suppose we try to keep element $V[i]$ as last element to be added.

Exclude the last element $V[i]$ and make two sets $P$ and $Q$, first one stores elements which will be added to $A$ and second set stores numbers to be added to $B$ from all elements except $V[i]$. Clearly, since $A-B \leq 0$, therefore $sum(P) \leq sum(Q)$ and we need maximum $sum(P)$. Maximum value of $C$ would be $sum(P)+V[i]$.

We take the position which gives maximum value $sum(P)+V[i]$.

So, let's focus on finding maximum sum(P) we can obtain from set of all elements except one element excluded.

We know, that sum of all elements except V[i], is a constant, when V[i] is fixed, say $S$. So, we need to partition set of all numbers excluding V[i], so that $sum(P) \leq S/2$ because $sum(P)+sum(Q) == S$ and $sum(P) \leq sum(Q)$ and sum(P) is maximum possible.

We use Dynamic Programming here. The problem to find whether there exist a subset of values with sum $X$ is well known and is called Knapsack DP or subset sum problem. A brief explanation in secret box.

View Content

So, if you have understood the secret box, you know how to select a subset of values, so that their sum doesn't exceed S/2 as well as sum is maximal possible.

But, This process alone take $O(N*SUM)$ time, and doing this $N$ times have complexity $O(N^2*SUM)$, which is $500^4$, which cannot run in time. We have to optimize it.

For that, We maintain a prefix and a suffix knapsack table, say pre[i][j] and suf[i][j] before hand. (I will explain it use soon.)

pre[i][j] means whether we can make a subset of values up to index i, such that their sum is j. suf[i][j] represent whether there exist a subset of values with index above or equal to i, such that their sum is j.

Transition for this table is same as that for problem in hidden box. Just remember,additionally, if pre[i-1][j] is true, pre[i][j] will also be true. Similar for suf too.

Now, Suppose we have fixed $V[i]$ as last element. We need to make subset $P$ out of values in prefix up to i-1 and suffix after i+1.

After making pre and suf tables, let's fix the element, and notice, if max(sum(P)) achievable is $X$ for current element, it is of form $Y+Z == X$, Where $Y$ is sum of elements chosen in prefix and $Z$ is sum of values chosen in prefix.

Also, build two MX array, one for pre[i-1] and one for suf[i+1], say preMX and sufMX.

We need sum(P) upto S/2, so, iterate over every i, and try to see maximum value of expression preMX[i] + suf[S/2-i]. Maximum value over all i is maximum sum of $P$ achievable.

After finding max(P), take the element having maximum $sum(P)+V[i]$. This is maximum value of $A$ achievable.

Understand up to here properly, only then the next will make sense.

We know, which element will be added to $A$ at last, so, let us build the subset $P$, using the prev array we used in hidden box. Here too, make two prev tables, one for prefix and one for suffix. Also, when finding maximum preMX[i]+sufMX[S/2-i], also store i so that we can make a subset from prefix of sum preMX[i] and subset from suffix having sum sufMX[S/2-i]. Uses same idea as we did in hidden box. and combine both sets obtained. This set represent our Set $P$.

So, Now we reach the final step of solution, that is to build a permutation, so that $A = V[i] + sum(P)$ and $B = sum(Q)$. All Elements not in $P$ are in $Q$, except the chosen element as the last.

Make position vectors for each value v possible, storing indices i, such that $V[i] == v$.

We build permutation from left to right, and have two current sum variables $cA = cB = 0$. If $cA \leq cB$, we know that element at current position will be added to $A$, so we can take any element from $P$, say $x$, place it at current position (by fetching any position with value $x$) and increase CA by x. Otherwise, if $cA>cB$, fetch element from $Q$, place it at current position and add it to cB.

When set $P$ becomes empty and $cA \leq cB$, place the chosen element.

This way, we get the required permutation and aha, you deserve 100 points now. But thinking about, "Is there always exist a permutation of elements, such that elements in $P$ are added to $A$ and others are added to $B$ ?". Let's prove it.

Lemma: Two sets $P$ and $Q$, where $sum(P) \leq sum(Q)$, prove that there always exist a way to place them in a line, so that if we use the selection procedure as given in problem, Values from set $P$ are added to $A$ and values from set $Q$ are added to $B$.

Proof: Since, we know, under optimal choices, $sum(P) \leq sum(Q)$ and $sum(P) + V[i] \geq sum(Q)$ where $V[i]$ is chosen element.

Let us use mathematical induction to prove that a valid permutation always exist. (explaining small cases for clarity)

Suppose N == 1. This element must be chosen element, thus, both $P$ and $Q$ are empty. Only element is placed at only position.

For N==2, One of the element will be chosen, and second one must be in $Q$, so that before adding chosen element, $ca \leq cb$ is necessary.

For N==3, Excluding one element (largest one), smallest element in $P$ and middle element in $Q$. First of all, element in $P$ is placed, then element in $Q$, and then the chosen element.

General case: Suppose there exist a permutation of $N$ elements. We have to prove that a valid permutation exist of $N+1$ elements, after adding one element.

See, the added element, will be either in set $P$, or in set $Q$, or become the chosen element. Suppose we have final permutation. We try to remove element $x$ from right end one by one. If $A-x \leq B$, $x$ belonged to set $P$ (or was chosen element). Otherwise, it belonged to $Q$. we can repeat this procedure.

We will eventually reach the point when $A = B = 0$. If the elements are inserted in exactly opposite order (due to proof being right to left), the permutation will give required sets $P$ and $Q$.

Hence, we can see, that there will always exist a permutation giving sets $P$ and $Q$, and this completes our proof, and the editorial.

Time Complexity

For building pre and suf tables, it takes $O(N*SUM)$ time, which is same as $O(N^2*MAX)$, where MAX is maximum value of $V[i]$ permitted. For finding maximum value of sum(P) for a fixed element takes $O(SUM)$, we do this $N$ times, so, this step also takes $O(N*SUM)$ that is $O(N^2*MAX)$ time.

Subset can be generated in linear times and permutation from set P and Q can be generated in $O(N)$ or $O(N*logN)$ time, depending upon implementation.

Thus, overall complexity is $O(N^2*MAX)$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Edit: Until above links are not working, feel free to refer solution here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 01 Oct '18, 19:03

taran_1407's gravatar image

5★taran_1407
3.9k2387
accept rate: 22%

edited 01 Oct '18, 19:34

admin's gravatar image

0★admin ♦♦
19.7k350498541


William is right saying that there is always an optimal solution, where the largest of all coins is given to Chefu.

Any two sequences of coins A = A_1, A_2, ..., A_k and B = B_1, B_2, ..., B_l can be given to Chefu and Chefa, respectively, as long as Value(A) - A_k <= Value(B) and Value(B) - B_l < Value(A). Suppose w.l.o.g. that the sequences A and B form an optimal solution and A_k is the largest coin in A, and B_l is the largest coin in B. If A_k >= B_l, William is right. If, on the contrary, A_k < B_l, we consider two cases:

1) Value(A) - A_k >= Value(B) - B_l + A_k: Then giving the sequence B_1, B_2, ..., B_{l-1}, A_k, B_l to Chefu is at least as good a solution and gives the largest coin to Chefu, so William is right.

2) Value(A) - A_k < Value(B) - B_l + A_k: Then giving the sequence A_1, A_2, ..., A_{k-1}, B_l to Chefu is an even better solution. Contradiction.

link

answered 03 Oct '18, 15:26

kboitmanis's gravatar image

6★kboitmanis
262
accept rate: 50%

edited 04 Oct '18, 15:12

I know that this is wrong but here is a submission that gets 100 points with random permutation.

https://www.codechef.com/viewsolution/20400368

I looked over the contest ones (they got only 50 points) and I saw this idea and started to think how to make it faster. Inlined the shuffle method and made everything with arrays and increased the iterations.

link

answered 01 Oct '18, 23:02

inseder's gravatar image

6★inseder
3504819
accept rate: 0%

It would be a matter of pure luck. If you have any probabilistic proof, please share, because i am unable to think of any way to calculate number of valid permutations, though i am sure, answer is quite high.

(02 Oct '18, 18:06) taran_14075★

the number is big and I think this is because you don't care about order of numbers you add in the lower bag

(04 Oct '18, 04:44) inseder6★

I think that it's possible to prove that there exists an optimal solution in which the last v[i] added is the maximum value in v, so we can just use normal knapsack instead of using the prefix & suffix trick. Code

link

answered 02 Oct '18, 15:12

tmwilliamlin's gravatar image

7★tmwilliamlin
713
accept rate: 0%

We too tried to prove this, but were unable to come up with some proper proof.

Yes, It is giving correct answer for all cases i tried.

In case you have any proof to support, please share. :)

(02 Oct '18, 18:02) taran_14075★
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:

×2,093
×1,237
×647
×145
×86
×48
×45
×2

question asked: 01 Oct '18, 19:03

question was seen: 2,875 times

last updated: 04 Oct '18, 15:12