Problem LinkSetter: Trung Nguyen Tester: Hasan Jaddouh Editorialist: Bhuvnesh Jain DifficultyEASY PrerequisitesModular Operation, Greedy Algorithms ProblemFind the minimum number of steps to convert the array such that each element is divisible by 4 or tell it is not possible to do so. Each step takes 2 elements of the array, removes them and puts back their sum back into the array. ExplanationSince we want all the numbers to be divisible by 4 in the end, it is easy to convert all numbers modulo 4 initially as all addition operations can be performed in modulo field only. First of all, let us see when the answer will exist. The invariant here is that the sum of numbers before and after the operation doesn't change. In the end, we want all the numbers to be divisible by 4, meaning that their sum should be also divisible by 4. Thus, if the initial sum is divisible by 4, then only the solution exists. Let us call an element bad if it is not divisible by 4 else good. The basic observation is that we should not apply any operation on the good elements. Now, let us try to find the minimum number of steps to convert the array into one with every number divisible by 4, only when the solution exists. In each step, we take 2 numbers and put back one number back into the array. Thus, each step can essentially fix a maximum of 2 bad elements in the array. Let us assume the count of elements leaving remainder 1, 2, 3 when divided by 4 are $a_1$, $a_2$ and $a_3$ respectively. We will try to greedily pair elements of $a_2$ with $a_2$ and elements of $a_1$ with $a_3$. This helps us to achieve fixing a maximum of 2 elements at a time. Now, we can either we left with only 1 $a_2$ element or none. If we are left with 1 $a_2$ element, then we can pair with 2 remaining $a_1$ or $a_3$ elements. This will incur a total of $2$ steps. At last, we would be only left with $a_1$ or $a_3$ elements (if possible). This can only we fixed in one way. That is taking $4$ of them and fixing them all together in $3$ steps. Thus, we are able to fix all the elements of the array. To prove this is the optimal strategy, see the claim we made regarding the maximum number of elements that can be fixed at any moment of time. Our approach strictly tries to maximise the number of elements that can be fixed in one step at any given moment of time. Thus, we proved our greedy algorithm. It is also recommended to go through the discussion by @lebron below so that you get more details regarding the same. For more details, refer to the editorialist solution below. Time Complexity$O(N)$, per test case Space Complexity$O(N)$ or $O(1)$ Solution Links
This question is marked "community wiki".
asked 21 Dec '17, 16:57

Part of the editorial which you call a proof of greedy doesn't really sound like a proof to me. You are acting in greedy way, but there is no formal proof provided that doing optimal move at given point will not lead to worse forced moves in future. It is more or less clear for this one because amount of options is small and problem is trivial, yet if you'll try to provide optimal strategy to solve same problem for 5 or 6 instead of 4, things will get much worse. And in this one, somebody may ask "Why isn't it possible that we made some fixin1 move which made us run out of something and therefore forced us to do fixin3 instead of fixin1 for some of the elements in future?" and so on. answered 26 Dec '17, 01:03
I think the last part of your comment (i.e. the question) can be answered as follows. Say we made a move and fixed no element in the process, i.e. tried to combine 2 good elements only. Then this move is extra only and can be eliminated since all operations are done modulo $4$ only. So, even if a good element was to be combined with some bad element, we can directly do that process with 1 good element only instead of combining them first and then doing the process.
(26 Dec '17, 01:36)
Similarly, we can argue that once after the operation is applied and the resulting element turns good, it doesn't need to be touched again. This argument can also be applied to same problem for 5 or 6 but there, the number of cases to consider while combining can be quite large and things will get worse as you said.
(26 Dec '17, 01:37)
@lebron, thanks for your feedback, I will update the editorial too.
(26 Dec '17, 01:37)
Correct me if I'm wrong, but this is why I think that the greedy choice is correct: We can also think of this problem in another way, given a set of numbers, partition them into disjoint subsets, each having sum modulo 4 equal to zero. The cost of some way of partitioning will then be the summation of subset_size1 over all subsets and we would like to minimise this cost. In such a situation, joining pairs of 2s is optimal. Suppose that in an optimal solution, a pair of 2s say a,b belong to different subsets s_a, s_b. Let s_a1 and s_b1 be the corresponding subsets leaving out a and b.
(26 Dec '17, 02:57)
If you group them as (s_a1 U s_a2) and {a,b} instead, you'd still get the same cost. We can argue about pairing 1s and 3s in a similar way. And once that is done we do whatever we can with the remaining numbers. Also, any of the subsets must not contain in it a proper subset having modulo 4 equal to zero, because in that case we can take them separately and get a better cost. That's why we can leave out 'good' numbers as mentioned by likecs
(26 Dec '17, 03:00)

"At last, we would be only left with $a_1$ or $a_3$ elements (if possible). This can only we fixed in one way. That is taking $4$ of them and fixing them all together in $3$ steps."
answered 25 Dec '17, 11:58
What is not clear in this part? We first try to fix the $a_2$ elements and $a_1$, $a_3$ elements as far as possible. Thus we would be left with only $a_1$ or $a_3$ elements. You can prove that if solution exists, they should be left in multiple of 4 only. Thus, you take 4 of them and fix them in 3 steps. For example: Say, numbers {$1, 5, 1, 5$} were left, then you can fix by first combining $(1, 5)$ and then combining $(6, 1)$ and finally combining $(6, 6)$ to get the array as beautiful in 3 steps.
(25 Dec '17, 12:21)
Just see that (4)%4 = (2+2)%4 = (1+3)%4 = (1+1+2)%4 = (3+3+2)%4 Notice that if we merge two elements with %4 == 2, we will get a number%4 == 0. Same goes for all expressions. Notice that above eqn represent the possible mergings needed to achieve a number divisible by 4, with number of elements less 1 telling the number lf mergings required. So, we greedily try first two mergings, 2+2 and the 1+3, and then do one of the other two mergings (either 1 or 3 will be zero, because performing 1+3 operation max times reduces both one and three by min(one,three).
(25 Dec '17, 12:37)

https://www.codechef.com/viewsolution/16655865 it gives wa This gives AC:https://www.codechef.com/viewsolution/16657439 difference b/w these two is merging (1/3) to form 2 answered 25 Dec '17, 00:59

I thought of this logic:
This is the code:
I tried various test cases and got correct answers for them. But, Codechef is returning WA. It would be great if someone could help me out in this. answered 25 Dec '17, 09:56
(25 Dec '17, 10:10)
@rajiv2605 your logic is not right divn will not always be even as in the above case .Please read the editorial
(25 Dec '17, 10:14)
Oh nice... Thanks! I'll update my code.
(25 Dec '17, 10:18)

I had everything cleared up, except the case when number of a2 type elements is odd and you can add the one extra a2 type element with two a1 or a3 type elements to make the array beautiful. Cost me rank difference of around 500 and also a drop from 4 star to 3 star. sigh answered 25 Dec '17, 12:21

bro can you tell me how do you prove greedy techniques .every time i prove myself some greedy approach on codechef questions , it pass does not pass all test cases. as here the greedy step : i found the greedy as if( a1/4>min(a1,a3)) , then first do the a1/4 and (a1%4  a3) Also iam stuck on december long challenge problem CHEFUNI , which is also the greedy problem , any advice or suggestions will be welcome answered 25 Dec '17, 16:33
@akshatsharma, for proving greedy strategy, first try to find what you want to minimise/maximise. Here we want to minimise the number of steps to convert array into beautiful one. Each step fixes maximum of 2 elements only. Hence, the reason for this approach. Suggest you to read the editorial once again.
(25 Dec '17, 16:48)

bro can you tell me how do you prove greedy techniques .every time i prove myself some greedy approach on codechef questions , it pass does not pass all test cases. as here the greedy step : i found the greedy as if( a1/4>min(a1,a3)) , then first do the a1/4 and (a1%4  a3) Also iam stuck on december long challenge problem CHEFUNI , which is also the greedy problem , any advice or suggestions will be welcome answered 25 Dec '17, 16:33

Hey @taran_1407 and @likecs can you please tell me about the difference between the following two codes as one got WA while the other got AC. The only difference in the two codes is that in one i have used only "if" statements to compare numbers having modulo 1 and 3(WA) while in the other i used "nested if else"(AC). Please help me as i got WA during contest and would not want this to happen again. link text (WA) link text (AC) answered 26 Dec '17, 14:40

why is this not working
https://www.codechef.com/viewsolution/16667987