S06E06 - Editorial

[notsoloud]

PROBLEM LINK:

Contest Division 2
Contest Division 3

Setter: Kanhaiya Mohan
Tester: Nishant Shah
Editorialist: Abhishek Ghosh

DIFFICULTY

Easy

PREREQUISITES

None

PROBLEM

Given a number N. You need to maximize the product of its digits by incrementing them at most K times.

EXPLANATION

Observation: Incrementing smaller numbers contribute more to the overall product as compared to incrementing larger numbers.

Proof

A product of 2 numbers can be laid out on a 2-dimensional grid. E.g. 3 * 5 can be represented as

Incrementing the larger number i.e. 5 will include region 1 and increase the product by 3.

Whereas, incrementing the smaller number i.e. 3 will include region 2 and increase the product by 5.

The same idea can be extended to any product of multiple numbers.

So, we increment the digits in the increasing order of their value until either we exhaust all our operations or reach the maximum possible number.

IMPLEMENTATION

In each operation we take the current minimum digit (If it is not equal to 9) ​and increase that by 1.

→ Example:

Consider the sample test case with N=2221 and K=3.

In the first iteration, there is no digit less than 1 in the array.

In the second iteration, 2221 → 2222 and K=2.

In the third iteration, 2222 → 3322 and K=0 (No more moves left).

So, the maximum product = 3 * 3 * 2 * 2 = 36.

Time complexity - O(9*K), where K is the number of digits in N

SOLUTIONS

Setter's Solution

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


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


    int t;
    cin >> t;
    while(t--){
        string s;
        int k;
        cin >> s >> k;
        for(int i = 1; i <= 9; i++){
            for(int j = 0; j < s.length(); j++){
                if(s[j] < char('0' + i)){
                    if(k == 0){
                        break;
                    }
                    s[j] = '0' + i;
                    k--;
                }
            }
        }
        int ans = 1;
        for(char j : s){
            ans *= (j - '0');
        }
        cout << ans << '\n';
    }


    return 0;
}

[sudhir_19]

After getting input n and k as int, I implemented the following logic. but it’s not working. Can someone give any explain why?
a = list(str(n))
a = [int(i) for i in a]
hq.heapify(a)
while k>0:
# print(a)
x = hq.heappop(a)
if x == 9:
break
x = x + 1
hq.heappush(a, x)
# print(a)
k-=1
ans = 1
for i in range(len(a)):
ans *= a[i]
print(ans)

[sudhir_19]

The code is in python

[ssvb]

You forget to push 9 back into the heap before break.

[jjjjjj]

Why this code shows WA on 2nd and third test case
https://www.codechef.com/viewsolution/54543180

[d_patil_02]

#include
using namespace std;

int main()
{
// your code goes here
int ts;
cin >> ts;
long long int N, K;
long long int size;
long long int maxIndex;
long long int maxProduct;
long long int product;
while (ts)
{
cin >> N >> K;
size = 0;
maxProduct = 1;
long long int A[7] = {1};
while (N)
{
A[size] = N % 10;
N = N / 10;
size++;
}

for (long long int i = 0; i < size; i++)
{
  if (A[i] == 0)
  {
    A[i] = 1;
    K--;
  }
}
for (long long int i = 0; i < size; i++)
{
  maxProduct = maxProduct * A[i];
}
for (long long int j = 1; j <= K; j++)
{
  maxIndex = -1;
  for (long long int i = 0; i < size; i++)
  {
    if (A[i] != 9)
    {
      product = 1;
      for (long long int m = 0; m < size; m++)
      {
        if (m == i && A[m] != 9)
          product = product * (A[m] + 1);
        else
          product = product * A[m];
      }
      if (product > maxProduct)
      {

        maxProduct = product;
        maxIndex = i;
      }
    }
  }
  if(maxIndex!=-1)
    A[maxIndex]++;
}

cout << maxProduct << endl;

ts--;

}
return 0;
}

After getting input n and k as int, I implemented the following logic. but it’s not working. Can someone give any explain why? Means it is Accepted for 1 subtask but other two giving WA.

[thunderboltz]

1
13 4

Your O/P: 15
Correct: 16

[thunderboltz]

2
0 0
20 0

Your O/P:
1
2

Correct:
0
0

[ishan301]

Can anyone tell me why my code is giving WA? Thanks in advanced.
https://www.codechef.com/viewsolution/54513043

[devansh_0007]

/* – author: Devansh_0007 (CF) – /
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define debug(x) cout << #x <<" " << x << endl;
#define endl “\n”
#define pb push_back
#define vi vector
#define F first
#define S second
#define sp " "
#define vll vector
#define vpii vector<pair<int , int>>
#define vpll vector<pair<ll , ll>>
#define pii pair<int , int>
#define vs vector
#define mii map<int , int>
#define mll map<ll , ll>
#define set_bits __builtin_popcountll
#define sz(n) (int)n.size()
#define all(n) n.begin(), n.end()
#define allr(n) n.rbegin(), n.rend()
#define for0(i, n) for (int i = 0; i < n; i++)
#define mem(a) memset(a, 0, sizeof(a));
double PI = 3.1415926536;
const ll inf = 1e17+7;
const int MOD = (1e9 + 7);
inline ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a;}
inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
inline bool ispalindrome(string s){
int n=s.length(),i=0,j=n-1;
while(i <=j){
if(s[i] != s[j])return false;
i++,j–;
}
return true;
}
vector prime((ll)1e7 , 1);
vll primenum;
inline void sieveOfEratosthene(){
ll n = 1e7;
prime[0] = prime[1] = 0;
for (int p = 2; p * p <= n; p++){
if (prime[p] == true){
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
primenum.pb(1);
primenum.pb(2);
for(ll i = 3 ; i < 1e7 ; i+=2){
if(prime[i]){
primenum.pb(i);
}
}
}
inline bool isprime(ll n){
if(n%2 == 0)
return false;
for(int i=3;ii<=n;i+=2)
if(n%i == 0)
return false;
return true;
}
ll fastpow(ll x , ll n){
ll res = 1;
while(n > 0){
if(n%2){
res = x;
}
n = n/2;
x =x;
}
return res;
}
ll pow_mod(ll x, ull n, ll m = MOD ){
ll res=1;
x=x%m;
if (x==0) return 0;
while (n > 0){
if (n & 1) // n is odd
res = (resx) % m;
n = n>>1; // n = n/2
x = (xx) % m;
}
return res;
}
ll modInverse(ll a, ll m){
int g = gcd(a, m);
return pow_mod(a, m - 2, m);
}
void printbinary(int n){
for(int i = 10 ; i >= 0 ; i–){
cout<<((n >> i) & 1 );
}
}
void solve(){
string ss;
cin >> ss;
ll k , n = sz(ss);
cin >> k;
vll a(n);
for0(i,n){
a[i] = ss[i] - ‘0’;
}
sort(all(a));
ll ans = 1;
for(ll i = 0 ; i < n-1; i++){
while( (a[i] < a[i+1] ) && k > 0){
k–;
a[i]++;
}
}
while(k > 0){
bool f = 1;
ll mm = k;
for(int i = 0 ; i < n; i++ ){
if(a[i] != 9){
a[i]++;
k–;
}
if(k <= 0){
f = 0;
break;
}
}
if(!f || mm == k){
break;
}
}
for(int i = 0 ; i < n; i++ ){
ans = ans * a[i];
}
cout << ans;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
sieveOfEratosthene();
cin >> t;
for(int i=1;i<=t;i++){
// cout<<“Case #”<<i<<": ";
solve();
cout<<endl;
}
return 0;
}

Why it got WA on test case 2

[r32vik]

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

int main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--){
	    int n,k;
	    cin >> n >> k;
	    if(n<10) {
	        cout << n+k <<endl;
	        continue;
	    }
	    int temp=n,sum=1;
	    priority_queue<int,vector<int>,greater<int>> res;
	    while(temp!=0){
	        int rem=temp%10;
	        res.push(rem);
	        temp=temp/10;
	    }
	    while(k--){
	        int s=res.top();
	        res.pop();s+=1;
	        res.push(s);
	    }
	    while(!res.empty()){
	        int s=res.top();
	        sum=sum*s;
	        res.pop();
	    }
	    cout << sum <<endl;
	    
	}
	return 0;
}

Does anyone have an idea on why this is failing for 2nd and 3rd cases??
Thank-you!!

[jjjjjj]

Thanks bhai

[kode_23]

import numpy
t = int(input())
for i in range(t):
a,N = map(int,input().split())
a = str(a)

a = list(a)
count1 = 0
if(min(a) == 0):
    if(a.count(0) > N):
        print(0)
        exit(1)
else:
    while(count1<N):
        a = list(map(int, a))
        i = a.index(int(min(a)))
        a[i] = int(a[i])+1
        count1 = count1+1
a = list(map(int, a))
result1 = numpy.prod(a)
print(result1)

#Could anyone point out what is going wrong in this code…
Thanks in advance

[sheetal2000]

(https://www.codechef.com/viewsolution/54598971)

Please help me with this, Why this is showing the wrong answer when I am following the same approach.

[aditya_1105]

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include <unordered_set>
#include <unordered_map>

//#include
using namespace std;

#define ln ‘\n’
#define ll long long
#define MOD 1000000007

void solve()
{
string n; ll k;
cin >> n >> k;
////////////////////////////////////////
map<char, ll> mp;
for(char c : n) {
mp[c]++;
}
while(k > 0) {
auto p = mp.begin();
if(p->first == 9) break;

    if(k >= p->second) {
        k -= p->second; 
        mp[p->first + 1] += p->second;
        mp.erase(p->first);
    } else {
        mp[p->first] -= k;
        mp[p->first + 1] += k;
        k = 0;
    }
}

ll ans = 1;
for(auto p : mp) {
    ans *= pow((ll)(p.first - '0'), p.second);
} 

cout << ans << ln;

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ll t = 1;

cin >> t;
while (t--)
    solve();
return 0;

}

can anyone help me please, it’s given wrong answer

[drakcy]

#include<bits/stdc++.h>
using namespace std;// #define {}[]
const int N=1e6+10;

long long trees[N];
map<int,vector>mp;

int main(){
int n; cin>>n;
while(n–) {
int t,k; cin>>t>>k;
std::vector v;
while(t){
int k=t%10;
v.push_back(k);
t=t/10;
}
for (int i = 1; i <= k; ++i)
{
sort(v.begin(),v.end());
if (v[0]!=9)
{
v[0]=v[0]+1;
}

        }
        int c=1;
        for (int i = 0; i < v.size(); ++i)
        {
            c*=v[i];
            
        }
        
        cout<<c<<"\n";

    }
return  0;

}

is this good
?