Can I know why my code fails? CodeChef: Practical coding for everyone
Slightly optimized approach (O(N) solution)-
- After eliminating all odd length cases, we can maintain a frequency array of size 26(a-z) and it will store frequencies of each char, in something like this-
int freq[]= new int[26];
for (int i = 0; i < c.length; i++)
freq[(int)c[i]-97]++;
- We make a result_string in form of char array of size N, then we maintain a pointer, which-
i. Sets result-string[ptr] as corresponding i th frequency character
ii. ptr is incremented by frequency of current character
iii. We also set a sort of terminate variable in case any frequency crosses n/2
//this flag is to terminate in case
//we find any frequency more than half of n
boolean term_flag=false;
for (int i = 0; i < freq.length; i++) {
if(freq[i]>0)
{
//a*****b***c******d****
//something like this we mark the result_string
result_string[ptr]=(char)(i+97);
ptr+=freq[i];
}
if(freq[i]>n/2)
term_flag=true;
}
if(term_flag==true)
{
out.println("NO");
continue;
}
- Then simply we set all empty char in result_string with char before and reverse the second half (both O(N)
//next me mark the remainder with previous values
//ie replace * with value before *
for (int i = 1; i < result_string.length; i++)
if(result_string[i]=='\u0000')
result_string[i]=result_string[i-1];
//now we flip the second half of the string
int i=n/2,j=n-1;
while(i<j)
{
char t=result_string[i];
result_string[i++]=result_string[j];
result_string[j--]=t;
}
out.println("YES");
out.println(new String (result_string));
Over all time complexity 26*N= O(N)
Solution link (Java)-
https://www.codechef.com/viewsolution/57666074
CAN ANYONE PLEASE TELL ME MY MISTAKE???PLS
I AM GETTING TLE ON 4 AND 5 TASK
my code : CodeChef: Practical coding for everyone
Thanks in advance
Don’t use scanner class & system.out.print.ln(), use BufferedReader & PrintWriter classes …also instead of string builder use char array. Default I/O of java is very slow for large number of test cases ~10^4…If it still fails then try using 1:1 correspondence list instead of HashMap
ok sir, Thank you so much sir
Can someone tell why this fails for some cases:
#include
using namespace std;
#include <bits/stdc++.h>
int main() {
long long int t;
cin>>t;
for(int =0;<t;_++)
{
vector v;
long long int n,m,x=0;
cin>>n;
long long int c[26];
for(int i=0;i<26;i++)c[i]=0;
for(long long int i=0;i<n;i++)
{
char ch;
cin>>ch;
c[ch-‘a’]++;
}
m=n/2;
for(int i=0;i<26;i++)
if(c[i]>x)
x=c[i];
if(x>m || n&1){
cout<<“NO\n”;continue;}
cout<<“YES\n”;
long long count=0;
for(int i=0;i<26;i++)
{
char ch=‘a’+i;
if(count<m && count+c[i]>m)
v.push_back(ch);
else{count=count+c[i];
for(long long int j=0;j<c[i];j++)
cout<<ch;}
}
while(count<n){
for(unsigned int i=0;i<v.size();i++)
{
char ch=v[i];
if(c[ch-‘a’]>0)
{cout<<ch;
count++;
c[ch-‘a’]–;
}
}
}
cout<<"\n";
}
return 0;
}
My logic was to re-arrange the string such that sum of frequency of all the letters gets divided into two halves.
Intuition: If each half of the string have frequency equal to ( Total sum of frequency ) /2. Then, It will be an anti-palindrome, if and only if, each letter appears <=(n/2) times.
Example for intuition:
aabbbcccdd (a*2,b*3, c*3,d*2)
So, the two halves will not match with each other. You can also think in a way that:
a(2) and d(2) cancels out.
b(3) and d(3) cancels out.
Note: Calculation of frequency of each half is as follows:
Write all the occurrences of each letter together. If a letter appears x times in continuation(not in scattered way), then whole x will be added to the frequency, we cannot partition x.
Example for Note:
n=10 and string = abbbccdddd
Frequencies of letters are as follows:
a - 1
b-3
c-2
d-4
Total sum of frequency - 10
We cannot do this way: 1+3 +1+1+4 (Order:a(1),b(3),c(1),c(1),d(4))
Which refers to - abbbccdddd
To count the frequency of c in the first half as 1 in order to ensure the frequency of first half as 5(10/2), we have to break the continuation of c.
So, add rest of the part of occurrences of c in the end of second half.
Right way of doing it: 1+3 +1+4+1 (Order:a(1),b(3),c(1),d(4),c(1))
Which refers to - abbbcddddc
After this, Just check if it is an anti-palindrome or not. If yes, then print the answer and if no, then print NO. It will not be an anti-palindrome, when a letter has a frequency > n/2.
Proof of correctness:[1 based indexing]
If a letter z appears only 1 time at index 1 and If a letter p appears n/2 times in continuation after z, and to ensure the frequency of the first half equal to ( Total sum of frequency ) /2, we have to break the continuation of occurrences of p.So, the extra x occurrences of p will be added at the end of second half.
Considering n=10
extra x is calculated as : (1(z) + 5(p)) - ( Total sum of frequency ) /2
So, x = 6-5=1
Now, question arises, if p is at ith index, will p be at (n+1-i)th index ?
Lets, check,
- Starting and ending Index of occurrences of p in the first half after breaking the continuation will be:
- starting index (s1): (index at which p occurred first), which is 2 ( always <=n/2)
- ending index (e1): (n/2), which is 5
- Starting and ending Index of occurrences of p in the second half after breaking the continuation will be:
- starting index (s2): (n-x+1) which is n
- ending index (e2): (n)
if i=e1
Then n+i-1 = n+1 - (n/2) = (n/2) + 1According to Rule, s[n/2]!=s[(n/2) + 1]
If we check s2, As x can never be n/2 (If x=n/2, that means it’s not an anti-palindrome), hence, s2 will never be n/2 +1, which means at index=n/2+1 some other character is present which is not p.
if i=s1
Then n+i-1 = n+1 - (s1)
According to Rule, s[s1]!=s[n-(s1)+1]
Note: (s1) ranges from [2,n/2] if (s1)=1, then there is no need for breaking the partition.If we check s2, As x will always be < s1 (If x=s1, that means it’s not an anti-palindrome), hence, s2 will never be equal to n-(s1)+1, which means at index=n-(s1)+1 some other character is present which is not p.
Hence its proved that if p is at ith index, p will be never be at (n+1-i)th index
My AC Solution - Click Here
Thanks!
1 Like
After Sorting , we need to reverse the right half of the string according to explanation . Then our output will become : “aaaabccbbb” .
Well, I made a couple of basic mistakes on my way to a solution. Hopefully instructive.
The first one was to go with my intuition rather than the actual definition, since I think the exclusion of odd-length strings where the central character is “equal to itself” is a distortion of the natural definition of anti-palindrome, but there’s no doubt that it follows from the stated S_i \neq S_{(N+1−i)}
I then handled odd-length strings as a special “NO” case. I was already correctly checking for the “NO” case arising from the highest frequency character being more than half the string. Second error, I fumbled the creation of an anti-palindrome by simply adding characters in descending frequency count. This of course allows the potential for the character in the middle of the string to be common to both halves.
So I then updated the character frequency table, which I already had in descending frequency order, to reduce frequency on the entry which crossed the middle and add those characters back as a final entry. So for example abcabcabcabcabca would give frequencies (a,6), (b,5), (c,5) which would be changed to (a,6), (b,2), (c,5), (b,3) and produce aaaaaabbcccccbbb