BTAR - Editorial

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.

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

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

@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

@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

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

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)

commented line has two statements.

Which one u are referring?

@rajiv2605
check this input :

1

6

2 2 2 3 3 4

your output:2

correct o/p:3

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

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

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.

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

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

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.

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.

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

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.

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

why is this not working

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