PROBLEM LINK:
Setter: Ramanan S
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Maths and Construction.
PROBLEM:
You have given an array of N integers and you can apply the following operation on it.
- Choose any two consecutive odd elements and replace them by a single element - their sum.
- Choose any two consecutive even elements and replace them by a single element - their sum +1.
By applying the above operation find the shortest size to which array that can be formed and in case of multiple arrays with the same length
QUICK EXPLANATION:
- For the array in which there are no consecutive odd or even numbers. In that case, we can’t make any operation to reduce the size of the array so the final answer will be the array itself.
- If X is the number of even elements in the array and Y is the number of odd elements in the array then if X% 3 = Y% 3 Initially then it will remain true after applying any number of operation and if X% 3 != Y% 3 then it will remain true after applying any number of operation.
- For the array which has at least one pair of consecutive elements which have the same parity. The following conditions are true. (Note X is the number of even elements and Y the number of odd elements).
- If initially X% 3 != Y% 3, then the array can be reduced to a single element.
- If initially X% 3 = Y% 3, then the array can be reduced to two elements.
EXPLANATION:
First, let us consider that array in which there are no consecutive odd or even numbers. In that case, we can’t make any operation to reduce the size of the array so the final answer will be the array itself.
Now we will consider only those array in which there are some(\geq 1) consecutive odd or even numbers present in the array. Now some observation regarding the operation we are performing.
- If X is the number of even elements in the array and Y is the number of odd elements in the array then if X% 3 = Y% 3 Initially then it will remain true after applying any number of operation and if X% 3 != Y% 3 then it will remain true after applying any number of operation. (
Why? suppose you do an operation on odd consecutive then you are adding -2 to the X and 1 to Y after the operation and (-2)%3 == (1)%3 so initial condition will remain same.)
Now let us try to solve the first subtask. Let us consider an array of only even parity(same can be observed for odd) so we have X elements of even parity initially and Y elements(Y == 0) of odd parity and let us consider 3 possible cases. Note I will represent even elements of the array with 0 and odd elements with 1.
- When X % 3 == 0, In this case, you can reduce the array to two elements(
Why not 1 element? because as initially (X % 3) == (Y % 3) (as Y == 0 initially) so when only 1 element left, then one of these two should be non-zero and other zero which violates the condition hence two elements is the next optimal answer which I will show a way to construct). If X == 3, then to make lexicographic smallest order just merge the last two elements. when X > 3(i.e. 6, 9 ...) then you can reduce its size by 3 by doing [0, 0, 0, 0] -> [1, 1] -> [0] reducing the total size by 3. so to build the lexicographically smallest leave the first element and keep on applying this operation and you will get the array [0, 1], where ‘0’ represent a number with even parity and ‘1’ with odd parity.- So finally we will get an array [0, 1] or you can do the same to get [1, 0](by merging the first two elements when only 3 elements are left will be used later).
- When X % 3 == 1, In this case you can compress the array into size of 1. [0, 0, 0 … X elements] -> [0]. can be done by applying the above operation of taking 4 elements and compressing it to 1 element ([0, 0, 0, 0] ->[0]) repeatedly.
- So finally we will get an array [0]. Note the parity of the element is the same.
- When X % 3 == 2, In this case, you can again compress the array into the size of 1 and that one element will be of odd parity [0, 0, 0 … X elements] -> [1]. How? First just consider the array with X-1 elements, Then (X-1) % 3 == 1, so we can compress this array of X-1 element into single element [0] then finally we will be left with two elements [0, 0], we will merge them togethor to [1] and get our answer.
- So finally we will get an array [1]. Note the parity of the element is different.
Now let us consider the array of type [0, 0, 0, … x times and 1, 1, 1, 1 … y times]. We will use the conversion done above to handle this array.
- Case 1 : x % 3 != y % 3
- x % 3 == 1 and y % 3 == 2, then [0, 0] -> [1]
- x % 3 == 2 and y % 3 == 1, then [1, 1] -> [0]
- x % 3 == 2 and y % 3 == 0, then [1, 1, 0] -> [0, 0] -> [1]
- x % 3 == 0 and y % 3 == 2, then [1, 0, 0] -> [1, 1] -> [0]
- x % 3 == 1 and y % 3 == 0, then [0, 0, 1] -> [1, 1] -> [0]
- x % 3 == 0 and y % 3 == 1, then [0, 1, 1] -> [0, 0] -> [1]
So the final array in this case always be of length one Now the answer of this can be efficiently computed as :(As you know that final array is a single element so we just have to compute the sum of elements and number of operation where even numbers are added as they add 1 to our answer)
int X = numOfeven; // we will refer to it as 0
int Y = numOfodd; // we will refer to it as 1
ans = sum_of_array_elements;
while(X+Y > 1) {
cur_x = X;
cur_y = Y;
X = cur_x % 2; // merging all 0, 0, 0, 0... into pairs of two making a continous segment of 1's and if count of 0 is odd then leave one 0 and if its even then leaving zero 0.
Y += cur_x/2; // as all merged 0's will be converted to 1, note it is an integer division.
ans += cur_x/2; // as all merged 0's will add one to our answer, note it is an integer division.
cur_x = X;
cur_y = Y;
Y = cur_y % 2; // merging all 1, 1, 1, 1... into pairs of two making a continuous segment of 0's and if count of 1 is odd then leave one 1 and if its even then leaving zero 1.
X += cur_y/2; // as all merged 1's will be converted to 0, note it is an integer division.
}
Why can we able to just merge them by doing division by 2. It is because they form a continuous segment of 0’s and 1’s after each iteration that’s why we just simply dividing it by 2 first converting all 0’s to 1’s and if the count is odd leaving one 0 at the border between 0 and 1 and then merging all 1’s to 1’s and if the count is odd leaving one 1 at the border.
- Case 2 : x % 3 == y % 3
- x % 3 == 1 and y % 3 == 1, then [0, 1]
- x % 3 == 2 and y % 3 == 2, then [1, 0]
- x % 3 == 0 and y % 3 == 0, then [1, 0, 0, 1] -> [1, 1, 1] -> [0, 1] or [1, 0]
Since we have to print the most beautiful final array, we have to make the first element as small as possible. Let the original array be A = [a_1, a_2 … a_n] and the final array be B = [b_1, b_2]. We know that b_1 \geq a_1 and hence the smallest value of b_1 is a_1. So for computing b_2 we can separate the first element of the array and only consider the array from [a_2, a_3 … a_n] now for this array (x % 3 != y % 3 ) hence we can compute b_2 by applying operation described above.
Now we will consider the case where the array can have any arbitrary order of even and odd element and have at least one pair of the consecutive element which have the same parity.
Claim : We can convert the this array in the form of array of [0, 0, 0, 0 … x element 1, 1, 1, 1 … y element] or [1, 1, 1, 1 … y element 0, 0, 0, 0 … x element] or [0, 0, 0, 0 … x element] or [1, 1, 1, 1 … y element] so we can compute the answer by applying the above methods. And if initially x % 3 != y % 3 then we can reduce it to single elment and when x % 3 == y % 3 then we can reduce it two element and in this case to make it lexicographically smallest separate the first element now the new array will have x’ % 3 != y’ % 3 compute the single element as computed in the first case and final array will be [first element, computed_sum]. Now to convert the array following observations are made.
-
We can always destroy the subsegment lying between two consecutive sets of consecutive numbers. Example
- [1, 1, 1,
0, 1, 0, 1, 0, 1, 1, 1, 1] this highlighted segment can be deleted to get the final array as [1, 1, 1, 1, 1, 1]. - [1, 1, 1,
0, 1, 0, 1, 0, 1, 0, 0, 0, 0] this highlighted segment can be deleted to get the final array as [1, 1, 1, 1, 0, 0]. - [1, 1, 1,
0, 1, 0, 1, 0, 1] this can form to [1, 1, 1] - [1, 1, 1,
0, 1, 0, 1, 0] this can form to [1, 1]
- [1, 1, 1,
-
So after deleting all such segment we will get the array of form [0, 0, … 0, 0, 1, 1, … 1, 1, 0, 0, … 0, 0, 0, 1, 1, … 1, 1, 1]. now this segment can be easily converted to an array of the form [0, 0, 0, 0 … x elements 1, 1, 1, 1 … y elements]. How? consider the first 3 continuous segments of 0’s and 1’s and 0’s. you can delete all 1’s(or convert them to 0’s) between the continuous segments of 0’s and merging two connecting 0’s segment by applying the following operation. I will refer to the segment as segement 1, 2 and 3.
- If the length of segment 2 is greater then consider the first 2 consecutive 1’s and merge them to get a 0 and this 0 will become a part of segment 1, reducing the length of segment 2 by 2 and increasing the length of segment 1 by 1. If the length of segment 2 is 1 then consider the last 2 0’s of segment 1 and the only 1 of segment 2 and apply [0, 0, 1] -> [1, 1] -> [0].
- So by applying the above operation multiple times we will get the final array of the form described above and we can compute the answer.
Now all the above transformation I explained are for the purpose of explaining how things will work but for implementation purpose. You don’t have to individually go and delete each element to transform the array to compute the answer. You just have to count X number of even in the array and Y number of odd in the array(note array should have at least one consecutive pair with the same parity). Then you just have to check the condition for (X % 3 == Y % 3) and (X % 3 != Y % 3). And to compute the single element which we will get after applying operation for the array (X % 3 != Y % 3) can be computed with the below operation without the array conversion. It will handle it.(try to think why)
int X = numOfeven; // we will refer to it as 0
int Y = numOfodd; // we will refer to it as 1
ans = sum_of_array_elements;
while(X+Y > 1) {
cur_x = X;
cur_y = Y;
X = cur_x % 2;
Y += cur_x/2;
ans += cur_x/2;
cur_x = X;
cur_y = Y;
Y = cur_y % 2;
X += cur_y/2;
}
TIME COMPLEXITY:
- As we can only do at max N-1 operations and O(N) for traversing the array for various cases described above. So the total time complexity per test case is O(N).
SOLUTIONS:
Setter's Solution
//g++ file.cpp -o a.exe && a.exe
#include<bits/stdc++.h>
using namespace std;
long long int getAns(vector<long long int> &a,long long int odd_cnt,long long int even_cnt)
{
long long int n = a.size(),ans=0,temp1=0,temp2=0;
//assigning sum of array to ans
for(int i = 0; i<n ; i++)
ans+=a[i];
while(odd_cnt+even_cnt>1)//untill array length becomes 1
{
//converting even to odd and incrementing ans by 1 for each conversions
temp1 = odd_cnt; temp2 = even_cnt;
even_cnt = temp2%2;
odd_cnt += temp2/2;
ans += temp2/2;
//converting odd to even and no increment in ans
temp1 = odd_cnt; temp2 = even_cnt;
even_cnt += temp1/2;
odd_cnt = temp1%2;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin); freopen("error.txt", "w", stderr);
freopen("output.txt", "wb", stdout);
#endif
int t=1;
cin>>t;
while(t--)
{
long long int n,odd_cnt=0,even_cnt=0,final_length=0;
bool repeat = false;
cin>>n;
vector<long long int> a(n),ans;
for(int i=0;i<n;i++)
cin>>a[i];
//checking if we do atleast 1 operation i.e if there is atleast one 2 consecutive odd/even nos
for(int i=1;i<n;i++){
if( (a[i]%2)==(a[i-1]%2) ){
repeat = true;
break;
}
}
//if there is no consecutive odd/even nos then we can't do anything and hence print original array
if(!repeat)
{
cout<<n<<'\n';
for(int i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<'\n';
continue;
}
for(int i=0;i<n;i++)
a[i]%2==0? even_cnt++:odd_cnt++;
if((odd_cnt%3)!=(even_cnt%3))
{
final_length = 1;
long long int val = getAns(a,odd_cnt,even_cnt);
ans.push_back(val);
}
else
{
final_length = 2;
ans.push_back(a[0]);
a[0]%2==1?odd_cnt--:even_cnt--;
auto it = a.begin();
a.erase(it);
long long int val = getAns(a,odd_cnt,even_cnt);
ans.push_back(val);
}
//printing final answer
cout<<final_length<<'\n';
for(int i=0;i<final_length;i++)
cout<<ans[i]<<' ';
cout<<'\n';
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int a[100009];
ll f(int l,int r){
ll sum = 0,x=0,y=0;
repA(i,l,r){
sum+=a[i];
if(a[i]%2) x++;
else y++;
}
while(x>1||y>1){
ll a = x/2;
ll b = y/2;
x-=2*a-b;
y-=2*b-a;
sum+=b;
}
return sum;
}
ll sum = 0;
void solve(){
//int n=readIntLn(1,100000);
int n;cin>>n;
assert(n>=1&&n<=100000);
sum+=n;
repA(i,1,n) {
//a[i]=readIntSp(0,1e6);
cin>>a[i];
assert(a[i]>=0&&a[i]<=1000000);
}
//a[n] = readIntLn(0,1e6);
int s = 0,mn = n,lst = -1;
bool fg=0;
repD(i,n,1){
if(a[i]%2==lst%2){
fg=1;
}
lst = a[i];
if(a[i]%2) s++;
else s+=2;
if(s%3!=0&&fg){
mn = i;
}
}
if(!fg){
cout<<n<<'\n';
repA(i,1,n) cout<<a[i]<<' ';
cout<<'\n';
}
else{
if(mn==1){
cout<<1<<'\n';
cout<<f(1,n)<<'\n';
}
else{
cout<<2<<'\n';
cout<<f(1,mn-1)<<' '<<f(mn,n)<<'\n';
}
}
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
//int n=readIntLn(1,100);
int n;cin>>n;
assert(n>=1&&n<=100);
rep(i,n) solve();
assert(getchar()==EOF);
assert(sum<=1000000);
return 0;
}
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 