Greatest Difference -Editorial || MAXDIFF3

editorial
1

PROBLEM LINK: Greatest Difference | CodeChef

Problem Code: Greatest Difference | CodeChef

Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef

Contest : Carnival Finale Coding Competition | CodeChef

Author: Codechef Adgitm Chapter :
codermine29 | CodeChef User Profile for Nishtha Kapoor | CodeChef
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

DIFFICULTY:

Medium

PROBLEM:

Chef and Priyank are close friends. The chef is looking for ingredients to make his best cuisine, priyank is helping Chef in search for the ingredients. Priyank is preparing the list having the prices of the ingredients(Note: There can be two prices for the same ingredient). But priyank lost the track record. So, now he want you to find the two possible lists having the maximum difference in cost. There must be only n ingredients And the total sum of prices is given. Find the two lists if possible else you can print NO.

Note : The whole list can be imagined as integer so list can’t have zero as first price of list

EXPLANATION:

Use Even Odd concept.

SOLUTION:

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

vector finddiff(vector mx, vector mn) {
int cr = 0, st = mx.size() - 1;
// for(int i = 0; i <= st; i++) {
// cout << mx[i];
// }
// cout << endl;
// for(int i = 0; i <= st; i++) {
// cout << mn[i];
// }
// cout << endl;
vector ans;
while (st >= 0) {
if (mx[st] - cr >= mn[st]) {
ans.push_back(mx[st] - cr - mn[st]);
cr = 0;
}
else {
ans.push_back(10 + mx[st] - cr - mn[st]);
cr = 1;
}
st–;
}
reverse(ans.begin(), ans.end());
return ans;
}

void solve() {
int n , s;
cin >> n >> s;
vector f(n,0),se(n,0);
f[0] = 1;
se[0] = 1;
if(s < n || s > n*9) {
cout << “NO” << endl;
return;
}
s -= 1;
int num = s;
for(int i = 0; i < n; i++) {
if(f[i]) {
if(num >= 8) {
f[i] += 8;
num -= 8;
} else {
f[i] += num;
num -= num;
break;
}
}
else {
if(num >= 9) {
f[i] = 9;
num -= 9;
} else {
f[i] = num;
num -= num;
break;
}
}
}

for(int i = n-1; i >= 0; i--) {
	if(se[i]) {
		if(s >= 8) {
			se[i] += 8;
			s -= 8;
		} else {
			se[i] += s;
			s -= s;
			break;
		}
	}
	else {
		if(s >= 9) {
			se[i] = 9;
			s -= 9;
		} else {
			se[i] = s;
			s -= s;
			break;
		}
	}
}

vector<int> ans = finddiff(f,se);
int i = 0;
while(i < n && ans[i] == 0) {
	i++;
}
for(; i < n; i++) {
	cout << ans[i] ;
}
cout << endl;
// your code goes here
// return 0;

}

int main() {
int test;
cin >> test;
while(test–) {
solve();
}
return 0;
}