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

×

BTAR - Editorial

1
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

This question is marked "community wiki".

asked 21 Dec '17, 16:57

likecs's gravatar image

6★likecs
3.7k1978
accept rate: 9%

edited 27 Dec '17, 19:00

(26 Dec '17, 14:10) resda4★

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.

link

answered 26 Dec '17, 01:03

lebron's gravatar image

7★lebron
3.2k317
accept rate: 25%

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) likecs6★

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) likecs6★

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

(26 Dec '17, 01:37) likecs6★

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.

(26 Dec '17, 02:57) hemanth_16★

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) hemanth_16★
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:(
link

answered 25 Dec '17, 11:58

pant0000's gravatar image

4★pant0000
814
accept rate: 11%

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) likecs6★

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

(25 Dec '17, 12:37) taran_14076★

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

link

answered 25 Dec '17, 00:59

doramon's gravatar image

1★doramon
865
accept rate: 5%

edited 25 Dec '17, 01:34

commented line has two statements.

Which one u are referring?

(25 Dec '17, 01:09) taran_14076★

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.

link

answered 25 Dec '17, 09:56

rajiv2605's gravatar image

2★rajiv2605
11
accept rate: 0%

edited 25 Dec '17, 10:16

@rajiv2605 check this input :

1

6

2 2 2 3 3 4

your output:2

correct o/p:3

(25 Dec '17, 10:10) beginner_11114★

@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) beginner_11114★

Oh nice... Thanks! I'll update my code.

(25 Dec '17, 10:18) rajiv26052★

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

link

answered 25 Dec '17, 12:21

jagreetdg's gravatar image

4★jagreetdg
2189
accept rate: 9%

@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

link

answered 25 Dec '17, 16:33

akshatsharma's gravatar image

4★akshatsharma
282
accept rate: 0%

@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) likecs6★

@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

link

answered 25 Dec '17, 16:33

akshatsharma's gravatar image

4★akshatsharma
282
accept rate: 0%

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)

link

answered 26 Dec '17, 14:40

beginner_2017's gravatar image

5★beginner_2017
11
accept rate: 0%

edited 31 Dec '17, 00:11

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:

×15,116
×3,607
×965
×590
×106
×72
×9

question asked: 21 Dec '17, 16:57

question was seen: 3,418 times

last updated: 31 Dec '17, 00:11