Hey buddy!!!
I also tried this problem and the answer should be simple.
I also get the right output but submission shows incorrect. I have checked both my code and logic 5 times.
If someone can figure this out then please help me also.
While inserting the pattern in the sorted string you have to check both the cases whether to insert before the first match of p[0] p is pattern string in this case , or after the last match of p[0] in the main string .
For ex.
let the test case be 1 aabb ba
Then what you have to do is to check where to insert pattern "ba" after the b in the main string or before b in the main string and here the optimal answer will be to insert before the b in the main string .
Hence the optimal answer of this case is abab instead of abba.
We have to choose lexicographically smallest S. aaakaeekmnnry < akaaaeekmnnry
and in the test case
1
deadzacrosdead
dad
aacdadddeeorsz < aacdddadeeorsz
Hope you get the logic behind this, I’m really bad at explaining @anon18089129 has explained it above.
You can also refer to the editorial.
@fallmount@coder_indian4
You can do the following changes in your code after your final sorted list
np=len(pattern)
flag=1
for k in range (1,np):
if(p[k]<p[0]):
flag=0
break
if(p[k]>p[0])
break
Now if flag==1 then your codes will work fine since the sorted list will give the expected output.
For flag equals zero,
#Lets say s is your final list after sorting
if (flag==0):
pos=0
for i in range(0,len(s)):
if (s[pos] == p[0]):
index = s.index[p]
s[pos],s[index] = s[index],s[pos]
#swapping pattern with first occurance of p[0]
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr;
for(int i=0;i<n;i++){
int a;
cin>>a;
arr.push_back(a);
}
sort(arr.begin(),arr.end());
int s=arr[0];
int ans=0;
for(int i=1;i<n;i++){
if(arr[i]<=s && i!=n-1){
if(arr[i+1]>s){
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
s+=arr[i];
}
s=arr[0];
for(int i=1;i<n;i++){
if(arr[i]<=s){
ans++;
}
s+=arr[i];
}
cout<<ans<<endl;
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
return 0;
}
the ‘debug my code’ feature showed me the case where it failed.
1
2
6 5
my output given is
0
5 6
which is correct. But it marks it as wrong. Checked with other correct solutions also, my output is correct.
WHat is the problem??!