BTAR - Editorial

editorial
, , , , , ,
1

Problem Link

Practice

Contest

Setter: Trung Nguyen

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

EASY

Prerequisites

Modular Operation, Greedy Algorithms

Problem

Find 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.

Explanation

Since 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

Setter’s solution

Tester’s solution

Editorialist’s solution

1 Like
2

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

3

commented line has two statements.

Which one u are referring?

4

I thought of this logic:

  1. If the total sum is not div3ible by 4, return -1.
  2. Else, take mod of each number and find the total no. of non-zero mods(Let that be called divn).
  3. Divn would always be even, hence the no. of steps would be half of divn.

This is the code:

#include<iostream>
#include<vector>

typedef long long int ll;

using namespace std;

main()
{
	ll T, n;
	vector<ll> ans;

	cin>>T;

	while(T--)
	{
		ll sum = 0, steps = 0, divn = 0;
		cin>>n;
		ll arr[n];

		for(ll i=0; i<n; i++)
		{
			cin>>arr[i];
			
			arr[i] %= 4;
			
			if(arr[i] != 0)
				divn++;

			sum += arr[i];
		}

		if(sum%4)
			steps = -1;
		else
			steps = divn/2;

		ans.push_back(steps);
	}

	for(ll i=0; i<ans.size(); i++)
		cout<<ans[i]<<endl;
}

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.

5

@rajiv2605
check this input :

1

6

2 2 2 3 3 4

your output:2

correct o/p:3

6

@rajiv2605 your logic is not right divn will not always be even as in the above case .Please read the editorial

7

Oh nice… Thanks! I’ll update my code.

8

I A NOT UNDERSTANDING THIS PART OF EDITORIAL— HEY @taran_1407 COULD YOU HELP ME, PLEASE…
“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.”

   CAN'T ASK A QUESTION.. LOW ON KARMA:(
1 Like
9

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.

10

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

11

@pant0000

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

12

@likecs

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 :

a1= number of elements with modulo 4 ==1;

a2 =same as above but ==2

a3=same as above but ==3

i found the greedy as if( a1/4>min(a1,a3)) , then first do the a1/4 and (a1%4 - a3)

but you said it will be always be optimal to have a1-a3 or a3-a1 , how ??

Also iam stuck on december long challenge problem CHEFUNI , which is also the greedy problem , any advice or suggestions will be welcome

13

@likecs

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 :
a1= number of elements with modulo 4 ==1;
a2 =same as above but ==2
a3=same as above but ==3

i found the greedy as if( a1/4>min(a1,a3)) , then first do the a1/4 and (a1%4 - a3)
but you said it will be always be optimal to have a1-a3 or a3-a1 , how ??

Also iam stuck on december long challenge problem CHEFUNI , which is also the greedy problem , any advice or suggestions will be welcome

14

@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.

15

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 fix-in-1 move which made us run out of something and therefore forced us to do fix-in-3 instead of fix-in-1 for some of the elements in future?” and so on.

4 Likes
16

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.

17

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.

18

@lebron, thanks for your feedback, I will update the editorial too.

19

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_size-1 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.

20

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