problem link : Problem - A - Codeforces
why this approach is not working ?
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
void solve() {
int n;
cin>>n;
char arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int a[n];
bool flag = true;
for(int i=0;i<n;i++)
{
a[i] = arr[i]-'0';
}
for(int i=0;i<n;i++)
{
if(a[i] <= a[i+1])
{
flag = true;
}
}
if(flag)
{
cout<<"YES"<<"\n";
}
else
{
cout<<"NO"<<"\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc ;
cin>>tc;
while(tc--)
{
solve();
}
return 0;
}
Can you explain your logic because it would be easy to debug the code then!!
It feels like somewhere you are logically wrong.
Please note that:
The sequence could be ADDCC and still the teacher won’t have any suspicion it is not necessary that the letters are arranged alphabetically(lexicographically)
Maybe thats where you went wrong!!
AADA → teacher would have suspicion(OP : “NO”)
BBAA → teacher wont have suspicion (OP : “YES”)
Yes some logic would be good.
I personally would make an array of all alphabets and just update it like so:
alpha[str[a] - “A”]++
I would update it as long as the last letter that we updated was the same character as the current one, i.e
if(str[a-1] == str[a])
Now if they are not the same I would check their recorded frequency in the alpha array and if it is greater than zero, it would mean that it has occured somewhere before. Simple O(n) solution.
Yaa, Yesterday I approached it through the same approach.We can even solve the problem using maps .For instance, If we have a sequence like AABBCC
we can consider AA to be as A, BB as B ,CC as C so that when we encounter these letters next time we can simply increment the count…
if the count is greater than 1 then teacher would have suspicion else no suspicion.
Time complexity would be greater than the above approach but this approach is also accepatable.
Hey, your solution is always giving you “YES”, cause you have never turn your flag to false. The logic is wrong too.
Anyway you can try this: take a variable let’s say it c and assign it to the first character of input string.
Run a loop from i=1, i<n, check if s[i] != c, if so, run a loop from j=i+1, j<n. Inside second loop check if s[j] == c, if so, turn flag to false and break, exit second if, exit second loop and reassign c = s[i], exit first if, exit first loop.
Now you can say “YES” if flag is true else “NO”.
Hey @fake_revenge , you logic seems to be somewhere wrong for this problem.
Find out the best explanation and solution of the problem here.
Link to solution and explanation
1 Like
Hey, I got your logic but I think you are missing some edge cases…
A better approach will be just taking input of characters in vector and while taking input use FIND(STL) to check whether the char is already present or not…If it is present then chech whether it is the previous char in vector or not…
If not ouput NO and return.
Otherwise at end just cout YES.
BY this approach time complexity will also get reduced…
Hope you like it…
Hey your whole logic is wrong in this question u have to just basically see the different characters occurring in order and if any charater occurs more than you have to output “NO” else “YES”.
int n;
cin>>n;
string s;
cin>>s;
int a[26]={0};
char k=s[0];
a[s[0]-‘A’]++;
for(int i=0;i<s.length();i++){
if(s[i]==k){
continue;
}
else{
k=s[i];
a[k-‘A’]++;
}
}
bool m=true;
for(int i=0;i<26;i++){
if(a[i]>1){
cout<<“NO”<<endl;
m=false;
break;
}
}
if(m){
cout<<“YES”<<endl;
}
A BETTER APPROACH IS TO TRANSVERSE ARRAY FORM STARTING
TAKE A ARRAY TO STORE THE OCCURENCES OF EACH LETTER
WHILE TRANSVERSING THROUGH THE STRING
CHECK FOR EACH CHARACTER IF ITS OCCURENCE IS ZERO OR NON-ZERO
→ IF ITS ZERO THEN INCREMENT ITS OCCURENCE
AFTER INCREMENTING START A WHILE LOOP WHICH WILL INCREMENT THE **
** INDEX WHICH WE ARE TRANSVERSING TILL THE CONSECUTIVE CHARACTERS
ARE SAME.
→ IF ITS NON-ZERO :- HERE IS WHERE YOU HAVE TO BREAK TRANSVERSING THE STRING
i.e. WHERE TEACHER IS SUPSCIOUS, you can use a bool here to verify this
condition
NOW AFTER TRANSERVSING CHECK YOUR BOOL ACCORDING TO IT OUTPUT YES OR NO
Let a be the input array. Instead of storing characters 'a', 'b',\cdots we can instead store numbers 1, 2, \cdots.
The cleanest \mathcal{O}(n) approach would be to store an array lst_i for 1 \leqslant i \leqslant 26 which stores the last indice of a at the current moment. Initialize some boolean value truth = 1 and run a loop through the array a. In the i th operation we check if i-lst_{a_i} is equal to 1. If not we change truth to 0. After this we update lst_{a_i} = i.
Hope this approach helps…