isn’t this description simply wrong?
this question should not be considered in ranking.
Can someone explain this line " Every Character of the string is present in one and only one substring?" .Does this mean that every string must contain unique characters ??? Like abc def ghi is valid and abc ceb is not valid as c and b is repeating in both.???
I wasted many minutes on that. Don’t why they don’t write clear statement
I had done the same but later read the question carefully, and then I realized that same character(by same i mean the value) can occur in two different substrings.
example : given string : addddd
substring 1: dad
substring 2: ddd
the statement was little bit confusing which costed me my time
here is my submission in case you want to see.
https://www.codechef.com/viewsolution/43185380
Now understood,… thanx!!
Why did you print NO when size of string < 4
yeah a little bit on tricky side
1 Like
Even they are odd if their count is >= 5 (ex: “aaaaa”) you can divide them further such as “aaa” and “aa” and the even part should be added to the number of evens so it can used to turn one of the single characters into palindrome if needed. if count for odd is n then you should add (n-3)//2 to your evens.
where I am wrong?
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (int i = 0; i < n; ++i)
#define ll long long
#define pb(a) push_back(a)
int print()
{
string s;
cin>>s;
int a[26]={0};
fo(i,26)
{
a[i]=count(s.begin(),s.end(),97+i);
}
int l1=0,l2=0,l3=0;
fo(i,26)
{
if(a[i]>1&&a[i]%2==0) ++l1;
if(a[i]==1) ++l3;
}
if(l1<l3&&l3!=0) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
return 0;
}
int main()
{
ll t;
cin >> t;
while (t–)
{
print();
}
return 0;
}
i cannot understand what is wrong with my code and which test case it is failing.
#include
using namespace std;
int main()
{
long t;
cin >> t;
for (long T = 0; T < t; T++)
{
string s;
long a[26] = {0};
long counter = 0;
cin >> s;
for (int i = 0; i < s.length(); i++)
a[(s[i] - 97)]++;
for (int i = 0; i < 26; i++)
if (a[i] % 2 == 1)
counter++;
if (counter >= (s.length() / 2.0))
cout << "NO\n";
else
cout << "YES\n";
}
}
Exactly, I had couple of wrong submissions due to this. Finally tried removing the condition of number of sub-strings and got an AC. 
void solve()
{
string s;
cin>>s;
int arr[26];
memset(arr, 0 ,sizeof(arr));
for(int i=0; i<s.size(); ++i)
arr[(int)(s[i]-97)]++;
int side=0, center=0;
for(int i=0; i<26; ++i)
{
if(arr[i] == 1)
center++;
else if(arr[i]>0 && arr[i]%2==0)
side++;
}
if(center>side)
cout<<"NO";
else
cout<<"YES";
cout<<"\n";
}
Which testcase is failing??
You’re not alone. codechef should be more clear with their problem statement
WA.My approach was to put all the characters of frequency = 1 between 2 (same) characters . For example : aab will become aba. If Any character with an odd frequency they can be formed independently as they can form a palindrome. but the frequency of even characters must be considered for placing the character with frequency = 1.
for example : acbbbadzdz will be aca|bbb|dd|zz
for a better understanding plz see my code: CodeChef: Practical coding for everyone
can someone please help what is wrong in this approach or did i just misunderstand the question?
You are missing some cases.
If there are aaaabc it should print yes bcoz it can be break in aba, aca.
And aaaaaaabc should also print yes
It can be break in aba, aca, aaa
We treat each character seperately, it doesn’t matter if it’s same
Odd frequency numbers will also contribute here, eg aaaaaaa can be broken into aa aa aaa
Can anyone find the test case which fails this code as I am getting WA each time and I don’t know why?
Any help would be appreciated!
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s; cin >> s;
int a[26] = {0};
for(int i=0; i<s.size(); i++) a[s[i]-'a']++;
int eves = 0, ones = 0, odds = 0, atl_4 = 0;
for(int i=0; i<26; i++) {
if(a[i]) {
if(a[i] == 1) ones++;
else if(!(a[i]&1)) eves++;
else odds++;
if(a[i] >= 4) atl_4 = 1;
}
}
if(ones <= eves) {
if((ones == eves && eves == 1 && odds == 0) || (eves == 0 && odds == 1 && !atl_4) || (odds == 0 && eves == 1 && !atl_4)) {
cout << "NO";
} else cout << "YES";
}
else cout << "NO";
cout << '\n';
}
int main() {
int tc = 1; cin >> tc;
while(tc--) solve();
return 0;
}
yes! the statement clearly says that no each character should be present in any other substring, but in there in solution they are writing every character in other substring, this got me -18 else i would easily do that question. codechef should be clear with statements
1 Like
What is wrong in this approach :
pairs = 0, freqOne=0
Count the frequency of each letter
for [letter,pair] in freqmap:
if freq == 1 : freqOne++
if freq%2==0 and freq > 0 : pairs+=(freq/2)
if(pairs>=freqOne) then Yes
else No