PROBLEM LINK:
Contest
Author: Shahjalal Shohag
Tester: Ildar Gainullin
Editorialist: Rajarshi Basu
DIFFICULTY:
Cakewalk
PREREQUISITES:
Implementation
PROBLEM:
You are given a string S with length N \leq 1000. You may perform the following operation any number of times: choose a non-empty substring of S (possibly the whole string S) such that each character occurs an even number of times in this substring and erase this substring from S. (The parts of S before and after the erased substring are concatenated and the next operation is performed on this shorter string.) Is it possible to erase the whole string using one or more operations?
EXPLANATION:
Let us see what we are trying to do in every operation. We are taking
even number of occurrences of some of the letters of the string (which happen to be a substring but this shouldn’t bother us too much) and are deleting them. Therefore the parity of the frequency of the characters do not change.
Now, what if the all the characters in the string S had even number of occurrences? We could have taken the entire string right? Okay… that was easy.
Now what if some character occurs an odd number of times. Then, however many number of operations we performed, we could never delete all occurrences of that number right? I mean, let’s say the number ’a’ had 5 occurrences. After two operations, maybe we removed 4 of them. But note that we can never remove all 5 since we cannot pair odd number of occurrences in any particular reduction.
So essentially, if any character is present odd number of times, the answer is NO, else the answer is YES.
SOLUTION:
Setter’s Code
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 200);
while (t--) {
int n; cin >> n;
string s; cin >> s;
assert(n == s.size());
assert(1 <= s.size() && s.size() <= 1000);
for (auto c: s) assert('a' <= c && c <= 'z');
int mask = 0;
for (auto c: s) mask ^= 1 << (c - 'a');
if (mask) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}
2 Likes
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
string s;
cin>>s;
int ans=(int)s[0];
for(int i=1;i<n;i++){
ans=ans^(int)s[i];
}
if(ans==0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Why is this wrong
6 Likes
@rajarshi_basu please add editorials for CHEFMOD too … .
I have already written, just needs to be verified. will be uploaded very soon.
1 Like
@rajarshi_basu Can you explain in brief what the following line of instruction does:
for (auto c: s) mask ^= 1 << (c - 'a');
I solved the problem using map but that’s an overkill so can you tell me about how the above instruction was helpful?
2 Likes
I also had nearly same logic but ended up with a wrong answer
2 Likes
(c - 'a')
This part assigns a number to each alphabet; 0 for a, 1 for b and so on.
1 << (c - 'a');
This part changes the expression like 1 for a, 2 for b, 4 for c and so on. (powers of 2 using left shift)
mask ^= 1 << (c - 'a');
What this is doing is, XORing the mask with each of such numbers associated with each alphabet. If it comes even times, it would give 0 as A XOR A is 0. If it comes Odd number of times, it would give A, as A XOR 0 is A. If all alphabets appear even number of times, the value of mask will be 0 else it will be non zero.
Correct me if I am wrong - @rajarshi_basu
2 Likes
Why on taking string input through for loop I got WA??
While taking whole string through cin directly worked??
Can someone explain
#include<bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL)
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define mod 1000000007
#define F first
#define S second
#define DEBUG(x) do { std::cerr << x; } while (0)
#define ll long long int
using namespace std;
int main()
{
sync;
//cin.tie(0);
int t;cin>>t;
bool f1=0;
while(t--)
{
int n;cin>>n;
string s;bool f1=0;
std::vector<int> a(26,0);
for(int i=0;i<n;i++)
{
cin>>s[i];
a[s[i]-'a']++;
}
for(int i=0;i<26;i++)
{
if((a[i]%2) != 0)
{
f1=1;break;
//cout<<"NO"<<"\n";break;
}
}
if(!f1)
cout<<"YES"<<"\n";
else
cout<<"NO"<<"\n";
}
return 0;
}
why i got wrong answer for this code during contest??
#include <bits/stdc++.h>
using namespace std;
int f[26];
int main() {
int t,n;
cin>>t;
while(t--){
cin>>n;
string s;
cin>>s;
memset(f,0,26);
for(int i=0;i<n;i++){
f[s[i]-'a']++;
}
int ans=0;
for(int i=0;i<26;i++){
if(f[i]!=0 && f[i]%2==1){
ans=1;
break;
}
}
if(ans==1)
cout<<"NO\n";
else
cout<<"YES\n";
}
return 0;
}
Replace f[i]%2==1 with f[i]%2!=0
Check my solution : CodeChef: Practical coding for everyone
here is my code , its very basic and does the job…
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n=0,t=0;
string str="";
cin>>t;
while(t--){
int c=0,countt[1000]={0};
cin>>n;
cin>>str;
for(int i=0;i<n;i++){
countt[int(str[i])]++;
}
for(int i=0;i<n;i++){
if(countt[int(str[i])]%2==0){
c=1;
}else{
c=0;
break;
}
}
if( c==1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}
2 Likes
thanks ,now i will not carelessly use xor everywhere XD.
Implementation using XOR was just awesome…learnt a new application !
then what about
input : abcabc
it has even no of occurances , but the answer should be “NO”.
After staring at the problem for some 15-20 minutes this is the easiest approach I discovered
import java.io.*;
import java.util.HashSet;
class Eventual {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t--!=0) {
int n = Integer.parseInt(br.readLine());
char[] str = br.readLine().toCharArray();
HashSet<Character> hs = new HashSet<>();
for (int i = 0; i < str.length; i++) {
char ch = str[i];
if(!hs.isEmpty() && hs.contains(ch)) {
hs.remove(ch);
}else {
hs.add(ch);
}
}
if(hs.isEmpty()) System.out.println("YES");
else System.out.println("NO");
}
}
}
1 Like
Yes even I used a similar type of logic ,
I used an unordered set to map frequencies to each letter and condition was that the length is even and the frequencies of all character should be even
Check out my solution here : CodeChef: Practical coding for everyone
1 Like
for loop on input for string expects array of strings example-[bc, fajfssf, skf, fajsf] but we have a single string as input ,if you want to input using for loop use char array of size n than your solution will work.