ALLDIV3 - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

SIMPLE

PROBLEM:

Given an array A of N integers. Determine the minimum number of operations to make every element of A divisible by 3.

In each operation, you must select two distinct indices i,j and increase/decrease A_i/A_j by 1, respectively.

EXPLANATION:

Claim: It is impossible to make all elements of A divisible by 3 if the sum of elements of A is not divisible by 3.

Proof

Making every element divisible by 3 would imply that the sum of all elements in the final array is divisible by 3.

It is clear that the sum of elements of A is unchanged when performing an operation. Thus, if the sum of elements is not divisible by 3, no sequence of operations will generate the required solution.

When the sum is divisible by 3, I claim that it is always possible to make every element divisible by 3. The rest of the solution is constructive.

Let X represent all elements A_i where A_i\equiv 1\pmod 3. Similarly, let $Y$represent all elements A_i where A_i\equiv 2\pmod 3. Our goal is then to make all elements in X and Y divisible by 3.

Step 1: While both X and Y are not empty, select one element from each set and decrement/increment it, respectively. It is clear that both the selected elements become divisible by 3 after this move.

If after this step, one set is still non-empty, proceed to step 2. It is guaranteed that the number of elements in the non-empty set is divisible by 3 (why?).
Without loss of generality, let us consider set X as the non-empty set (a similar technique can be used when set Y is non-empty).

Step 2: While X is non-empty, select three elements from it - call them a,b and c. Increment a and decrement b by 1. Then, increment a and decrement c by 1. It is easy to see that the operations make the three elements divisible by 3.

At the end of the two steps, all elements of A will be divisible by 3.

To summarise, let x and y represent the number of elements in A that leave a remainder of 1 and 2 when divided by 3, respectively. Then, the number of operations done is equal to:

  • \min(x,y) in Step 1, and
  • 2*(\frac{x-\min(x,y)}{3}+\frac{y-\min(x,y)}{3}) in Step 2.

The final answer is simply the sum of the two values!

TIME COMPLEXITY:

O(N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

Can anyone please help me why my code gives wrong ans even it passes all sample test cases

#include<bits/stdc++.h>

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

int main()

{

fast;

int tc;

cin>>tc;

while(tc--)

{

    long long int n;

    cin>>n;

   long long  int left=0;

   long long  int right=0;

    long long int k;

    for (int i = 0; i < n; i++)

    {

        cin>>k;

        if((k-1)%3==0){

            left++;

        }else if ((k+1)%3==0){

            right++;

        }

    }

    cout<<left<<" "<<right<<"\n";

    if(left==right){

        cout<<left<<"\n";

    }

    else if(left==0 && right==0){

        cout<<"0\n";

                }

                else {

                    cout<<"-1\n";

                }

}

return 0;

}

2 Likes
4

Why My answer giving wrong answer?

Solution

1 Like
5 
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;

const ll large = 1e11, remi2 = 998244353;
const ll remi = 1e9 + 7, inf = LLONG_MAX;
const ld Pi = acos(-1);

#define pb push_back
#define F first
#define S second
#define ins insert
#define el "\n"
#define ell cout << el
#define sp " "
#define all(x) x.begin(), x.end()
#define setp(x) fixed << setprecision(x)
#define dbg(x) cout << #x << ": " << x << sp;
#define rep(i, m, n) for (ll i = m; i < n; i++)
#define rev(i, n, m) for (ll i = n - 1; i >= m; i--)

void vpri(vl v)
{
    for (ll i = 0; i < v.size(); i++)
        cout << v[i] << sp;
    cout << el;
}

// JMS
ll PowI(ll a, ll b, ll m)
{
    ll ans = 1 % m;
    while (b > 0)
    {
        if (b % 2)
            ans = (((ans % m) * (a % m)) % m);
        a = (((a % m) * (a % m)) % m);
        b = (ll)(b / ((ll)2));
    }
    return ans;
}

void Foxtrot()
{  
    ll n; cin>>n;
    vl v(n);
    rep(i,0,n) cin>>v[i];
    ll cnt = 0;
    ll c1=0,c2=0,c3=0;
    rep(i,0,n){
        if(v[i]%3==1){
            c1++;
        }
        if(v[i]%3==2){
            c2++;
        }
        if(v[i]%3==0){
            c3++;
        }
    }
    if(c3==n){
        cout<<0<<el;
        return;
    }
    ll k = min(c1,c2);
    ll m = max(c1,c2);
    ll op = k;
    if((m-k)==0){
        cout<<m<<el;
        return;
    }
    if((m-k)%3==0 and (k>0 or c3>0)){
        cout<<op+(m-k)<<el;
    }
    else{
        cout<<-1<<el;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T = 1;
    cin >> T;
    rep(i, 1, T + 1)
    {
        // cout<<"Case #"<<i<<": ";
        Foxtrot();
    }

    return 0;
}

Can anyone pls provide me with a test case where this code fails? I am not able to figure it out :confused: My contest code

6

Just go through this below given test case
3
2 2 2
Your code gives wrong answer but this test case is right it gives anser 2.

Explanation:-

1st step
i=0 , j=1
A[i]–; A[j]++; // A[i] =1 and A[j] = 3

2nd step
i=0 , j=2
A[i]–; A[j]++; // A[i] =0 and A[j] = 3

Thus array will become 0 3 3
And each element is divisible by 3 , it takes 2 step to get this result.

2 Likes
7

I guess this test case will be the corner case in which many people will fail

2 Likes
11

i didn’t know that were i got wrong
plz check my solun…

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

12

Please help, getting WA
#include <bits/stdc++.h>
using namespace std;

#define REP(i, a, b) for (ll i = a; i <= b; i++)
typedef long long ll;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

int t = 1;
cin >> t;
while (t--)
{
    ll n, sum=0, count=0;
    cin >> n;
    ll a[n];
    REP(i,0,n-1)
        cin>>a[i];
    REP(i,0,n-1)
    {
        sum+=a[i];
        if(a[i]%3!=0)
            count++;
    }
    if(sum%3!=0)
        cout<<"-1"<<endl;
    else
        cout<<ceil(count/2.0)<<endl;

}

return 0;

}

13

Hey @ritesh_gupta97 :wave:
Output in the else condition is not necessary to be always true. as in case of n = 6, array (2,2,2,2,2,2) your code will give 3 as output but the answer will be 4 as it is never possible in 3 steps.