PALPALS - Editorial

editorial
, , ,
46

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;
}
47

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
48

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

49

Thanks. Got it where I was doing it wrong.

50

Here, freqOne should be used as the no. of all odd times occurring characters in string.
For example:

If we take string to be: "aaabbc"
then freqOne = 2 ; pairs = 2
which makes it valid PalPal String.
51

yes.Me too misunderstood that sentence and wasted nearly a hour in that.But ,yes it is given clear .

52

using namespace std;
#include<bits/stdc++.h>
void solve()
{
string s;
cin>>s;
cin.ignore();
vectorv;
sort(s.begin(),s.end());
for(int i=0;i<s.length():wink:
{
int c=0;
while(s[i]==s[i+1])
{
++i;
++c;
}
v.push_back(c+1);
++i;
}
int c1=0,cev=0;
for(int i=0;i<v.size();++i)
{
if(v[i]==1)
++c1;
else
if(v[i]%2==0)
cev++;

}
if(c1<=cev)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
int main()
{
//freopen(“ii.txt”,“r”,stdin);
//freopen(“o.txt”,“w”,stdout);
int t;
cin>>t;
while(t–)
solve();
}
why i m getting WA ???,plz help me out…

53

one of the reasons why you should always put your code in blocks (between a pair of triple backticks)

54

what should i do ??The loop is running correctly i guess ,or if not the suggest something to make it correct or my whole logic is wrong ?? plz give some testcases.

55

i was talking about the code formatting. From next time put your code between a pair of triple backticks.

56

Same here!! Even mentioned in the comments section of the problem…but it was too late by then :upside_down_face:

57

Could some one help…
Why my code is not giving desired output??

from collections import Counter
import math
for _ in range(int(input())):
s=input()
x=Counter(s)
odd=0
even=0
for k,v in x.items():
if v%2!=0:
odd+=1
else:
even+=1
if (odd%2==0 or odd<=even) and ( (len(set(s))<math.ceil(len(s)/2)+1)):
print(“YES”)
else:
print(“NO”)

58

There’s no meaningful difference between these two sentences. Characters happen to be letters in this case and “is present in” is synonymous with “appears in”. You can’t “misunderstand” a sentence as itself.

Maybe you think that e.g. the string “aaaa” contains one letter instead of four. Is that the case?

59

#include <bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while(t--)

{

    int arr[123]={0};

    string s;

    cin>>s;

    for(int i=0;i<s.length();i++)

    {

        arr[s[i]]++;

    }

    int ecount=0;

    int ocount=0;// 

    for(int i=97;i<=122;i++)

    {

       if(arr[i]!=0 && arr[i]%2==0)

       {

           ecount+=arr[i]/2;

    

       }

       if(arr[i]!=0 && arr[i]%2==1)

       {

           ocount=ocount+arr[i];

    

       }

    }

    if(ecount>=ocount)

    {

        cout<<"yes"<<endl;

    }

    else

    {

        cout<<"no"<<endl;

    }

}

return 0;

}
Why is this code giving me a wrong ans??

60

No not that case. Take for example the last sample test case the string “xyxyxy”. I understood from the statement mentioned in the question that all the ‘x’ occur together in exactly one particular palindromic substring and similarly for the all the ‘y’. i.e. the valid substrings for the given string are xxx+yyy ,yyy+xxx only. The question probably meant that the character at a given positition of the string occurs in exactly one substring.

Perhaps the statement avoided all together would have been more clear than the statement which was written in the question.

61

So you read the explanation for example case 3 that directly contradicts your “the valid substrings for the given string are xxx+yyy ,yyy+xxx only” and yet expected that to be the case?

Also, that’s a weird assumption to make considering there’s nothing like it written in the statement. As usual, assuming too much is a mistake.

1 Like
62

I didn’t read the explanation for the test case(for the major part of the contest) as with my interpretation too the sample case passed and gave the desired output (partly my fault as well but just felt that the question statement could have been clearer).

63

Can somebody point out where am I going wrong in this solution? I am trying to separately consider characters with freq=1, characters with freq=3 and with freq>=5(and odd), and the remaining characters with even freq. Everything I have done within the main() function.
Link: CodeChef: Practical coding for everyone