Hello everyone,↵
I was trying to solve this problem, [problem:1765N].↵
I wrote a code and its logic is same as the editorial but rather than finding from digit '0' to '9' which is occurs first in the next 'k+1' elements in the number from left to right, I just searched the minimum among the 'k+1'.↵
↵
My code works on almost all testcases except when the input is increasing, like n=1337 and k=2. Answer should be 13 but mine gives garbage value.↵
↵
Here is my code, ↵
↵
<spoiler summary="My Code">↵
```c++↵
/**↵
* - Prakhar Mishra↵
* - The force is strong with this code.↵
**/↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll=long long;↵
↵
void solve(int tt)↵
{↵
// taking inputs↵
↵
string s;↵
cin>>s;↵
↵
ll k;↵
cin>>k;↵
↵
// if k==0, no operations, directly output↵
↵
if(k==0)↵
{↵
cout<<s<<endl;↵
return;↵
}↵
↵
// find the minimum digit from the first (k+1) digits of x excluding '0' as leading zero not allowed.↵
↵
ll mn=10;↵
ll ind=-1;↵
for(ll i=0;i<=k;i++)↵
{↵
if(s[i]!='0' && s[i]-'0'<mn)↵
{↵
mn=s[i]-'0';↵
ind=i;↵
}↵
}↵
↵
// remove everything before the smallest digit in x and reduce k accordingly.↵
// add to answer the first digit.↵
↵
string ans="";↵
ans+=s[ind];↵
↵
k=k-ind;↵
↵
// now we repeat this process again till k>0, but we will include '0' also in calculating minimum this time↵
↵
// range to choose next digit from =[ind+1,ind+1+k]↵
ll p1=ind+1;↵
ll p2=p1+k;↵
↵
while(k>0)↵
{↵
// finding minimum digit↵
↵
ll mn=10;↵
ll ind=-1;↵
for(ll i=p1;i<=p2;i++)↵
{↵
if(s[i]-'0'<mn)↵
{↵
mn=s[i]-'0';↵
ind=i;↵
} ↵
}↵
↵
// remove everything before the smallest digit in range and reduce k accordingly.↵
// and add to answer the minimum digit. ↵
↵
for(ll i=p1;i<ind;i++)↵
{↵
k--;↵
}↵
ans+=s[ind];↵
↵
// set the range to choose from for next digit↵
p1=ind+1;↵
p2=p1+k;↵
} ↵
↵
// lastly include everything left after operations are done↵
for(ll i=p1;i<s.size();i++)↵
ans+=s[i];↵
↵
// output↵
cout<<ans<<endl;↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
int T=1;↵
cin >> T;↵
↵
for(int tt=1; tt<=T; tt++)↵
{↵
solve(tt);↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
I saw authors code solutions using stack to keep the smallest elements. ↵
Can someone provide me some corrections in my code, or will i need to implement stack solution?↵
↵
**Edit** <br>↵
Solved the edge case by removing elements from end when k!=0 after traversing through the number. But got TLE as the increasing sequence will always check for minimum from the next 'k+1' elements of each index, resulting in worst case O(n^2) solution.↵
Maintaining stack is the most optimal way to keep the smallest numbers.
I was trying to solve this problem, [problem:1765N].↵
I wrote a code and its logic is same as the editorial but rather than finding from digit '0' to '9' which is occurs first in the next 'k+1' elements in the number from left to right, I just searched the minimum among the 'k+1'.↵
↵
My code works on almost all testcases except when the input is increasing, like n=1337 and k=2. Answer should be 13 but mine gives garbage value.↵
↵
Here is my code, ↵
↵
<spoiler summary="My Code">↵
```c++↵
/**↵
* - Prakhar Mishra↵
* - The force is strong with this code.↵
**/↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll=long long;↵
↵
void solve(int tt)↵
{↵
// taking inputs↵
↵
string s;↵
cin>>s;↵
↵
ll k;↵
cin>>k;↵
↵
// if k==0, no operations, directly output↵
↵
if(k==0)↵
{↵
cout<<s<<endl;↵
return;↵
}↵
↵
// find the minimum digit from the first (k+1) digits of x excluding '0' as leading zero not allowed.↵
↵
ll mn=10;↵
ll ind=-1;↵
for(ll i=0;i<=k;i++)↵
{↵
if(s[i]!='0' && s[i]-'0'<mn)↵
{↵
mn=s[i]-'0';↵
ind=i;↵
}↵
}↵
↵
// remove everything before the smallest digit in x and reduce k accordingly.↵
// add to answer the first digit.↵
↵
string ans="";↵
ans+=s[ind];↵
↵
k=k-ind;↵
↵
// now we repeat this process again till k>0, but we will include '0' also in calculating minimum this time↵
↵
// range to choose next digit from =[ind+1,ind+1+k]↵
ll p1=ind+1;↵
ll p2=p1+k;↵
↵
while(k>0)↵
{↵
// finding minimum digit↵
↵
ll mn=10;↵
ll ind=-1;↵
for(ll i=p1;i<=p2;i++)↵
{↵
if(s[i]-'0'<mn)↵
{↵
mn=s[i]-'0';↵
ind=i;↵
} ↵
}↵
↵
// remove everything before the smallest digit in range and reduce k accordingly.↵
// and add to answer the minimum digit. ↵
↵
for(ll i=p1;i<ind;i++)↵
{↵
k--;↵
}↵
ans+=s[ind];↵
↵
// set the range to choose from for next digit↵
p1=ind+1;↵
p2=p1+k;↵
} ↵
↵
// lastly include everything left after operations are done↵
for(ll i=p1;i<s.size();i++)↵
ans+=s[i];↵
↵
// output↵
cout<<ans<<endl;↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
int T=1;↵
cin >> T;↵
↵
for(int tt=1; tt<=T; tt++)↵
{↵
solve(tt);↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
I saw authors code solutions using stack to keep the smallest elements. ↵
Can someone provide me some corrections in my code, or will i need to implement stack solution?↵
↵
**Edit** <br>↵
Solved the edge case by removing elements from end when k!=0 after traversing through the number. But got TLE as the increasing sequence will always check for minimum from the next 'k+1' elements of each index, resulting in worst case O(n^2) solution.↵
Maintaining stack is the most optimal way to keep the smallest numbers.
