HTMLTAGS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Bharat Singla
Tester: Felipe Mota
Editorialist: Aman Dwivedi

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM:

You are given a string S. Your task is to find whether the given string S is a valid closing HTML tag or not.

A closing HTML tag must:

  • Start with "</"
  • End with ">"
  • Have only, and at least 1, lower-case alpha-numeric characters as its body

Help Chef by printing Success if the tag is fine. If not, print Error.

QUICK EXPLANATION:

We have a string S, and our goal is to find whether the given string is a valid HTML tag or not. Let us check the condition one by one:

Case 1: It should Start with "</"

  • It means that the first character of the given string should be < while the second character of this string should be /.

  • If the starting two characters of string S fulfill the requirement, we will move to check another condition otherwise the string is not valid.

Case 2: It should end with ">"

  • It means that the last character of the given string should be >.

  • If the requirement is fulfilled we move to check the last condition left otherwise the string is not valid.

Case 3: Have only, and at least 1, lower-case alphanumeric characters as its body

  • It means the remaining characters of the string S should contain only lowercase English alphabets ora digit and there should be at least one such character in the body.

  • We can simply iterate on the remaining string and can check this condition.

If all the conditions are full-filled then the string S is considered to be valid otherwise not.

TIME COMPLEXITY:

O(|S|) per test case

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
 
void solve() {
 
    string s;
    cin >> s;
    int n = s.length();
 
    if (n < 4 or s.substr(0, 2) != "</" or s[n-1] != '>') {
        cout << "Error\n";
        return;
    }
 
    bool is_valid = true;
    for (int i = 2; i < n - 1; i++) {
        bool is_alpha = (s[i] >= 'a' and s[i] <= 'z');
        bool is_num = (s[i] >= '0' and s[i] <= '9');
        if (!is_alpha and !is_num) {
            is_valid = false;
            break;
        }
    }
 
    cout << (is_valid ? "Success" : "Error") << endl;
}
 
int main() {
 
    int tc;
    cin >> tc;
    while (tc--) solve();
 
    return 0;
}	
Tester
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, 1000);
	while(t--){
		string s = readStringLn(1, 1000);
		for(auto c : s){
			assert(33 <= c && c <= 126);
		}
		if(s.size() > 3){
			bool ok = s[0] == '<' && s[1] == '/' && s[s.size() - 1] == '>';
			for(int i = 2; i + 1 < s.size(); i++)
				if(islower(s[i]) || isdigit(s[i]));
				else ok = false;
			cout << (ok ? "Success\n" : "Error\n");
		} else {
			cout << "Error\n";
		}
	}
	return 0;
}

Editorialist
##include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  bool ok = true;

  string s;
  cin>>s;

  int n=(int)s.size();

  if(n<4)
  {
    cout<<"Error"<<"\n";
    return;
  }

  if(s[0]!='<' || s[1]!='/' || s[n-1]!='>')
    ok=false;

  if(ok)
  {
    for(int i=2;i<n-1;i++)
    {
      if(!((s[i]>='a' && s[i]<='z') ||
        (s[i]>='0' && s[i]<='9')))
      {
        ok=false;
        break;
      }
    }
  }

  if(ok)
    cout<<"Success"<<"\n";
  else
    cout<<"Error"<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);


  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

Can anyone explain me what is the error in this code?

#include <bits/stdc++.h>
#define ll long long
#define MOD 1e9 + 7
using namespace std;
// Use Ctrl+B to run

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    while (t--)
    {
        string s;
        cin>>s;
        if((s[0]=='<' && s[s.length()-1]=='>') && (s[1]=='/'))
        {   
            bool ans = false;
            for(int i=2; i<s.length()-1; i++)
            {
                if((((int)s[i])>=48 && ((int)s[i])<=57) || ((int)s[i])>=97 && ((int)s[i])<=122)
                {
                    ans = true;
                }
                else
                {
                    ans = false;
                    break;
                }
            }
            if(ans)
            {
                cout<<"Success\n";
            }
            else
            {
                cout<<"Error\n";
            }
        }  
        else
        {
            cout<<"Error\n";
        }
    }

    return 0;
}

there is no error in your code it’s working fine :grinning:

bro i did the same code but did not get submit

But it gave me WA :cry:
https://www.codechef.com/viewsolution/48214857
Oops got my mistake I am so frustrated now…

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t–){
string tag;
cin >> tag;
int cnt = 0, wrong = 0, space = 0;
for(int i = 2; i < tag.length() - 1; i++){
if((tag[i] >= 97 && tag[i] <= 122) || (tag[i] >= 48 && tag[i] <= 57)) cnt++;
else if(tag[i] == 32) space++;
else wrong++;
}
if((tag.length() - 3 - space == cnt ) && tag[0] == ‘<’ && tag[1] == ‘/’ && tag[tag.length() - 1] == ‘>’ && space >= 0){
cout << “Success\n”;
}
else cout << “Error\n”;
}
return 0;
}
// Can anyone help me out?

Fun to note that you can solve it in a few lines with a simple regex.

C++ solution

4 Likes

try giving input with lots of spaces. It would print ‘Error’ instead of ‘Success’

First error is that say I have a test case like this
</ > There is a space in between in that case it’ll fail. Another condition is say </> this is the case where there is nothing in it at that one also if fails.
Also group the statements
(!((s[I]>=97 && s[I]<=122) || (s[I]>=48 && s[I]<=57)))

You will have to see that its not an empty tag as well.For eg </>. This should print ‘Error’ as well.

Why getting wa ??
ll t ;
cin >> t;

while (t--) {
	string tag;
	cin >> tag;

	int s = tag.size();
	int op = tag.find_last_of("<");
	int sl = tag.find_last_of("/");
	int en = tag.find_last_of(">");
	bool ch = false ;
	nloop(i, s) {
		if (isupper(tag[i])) {
			cout << "Error" << nline;
			ch = true;
			break;
		}
	}
	if (ch == true ) continue;
	if (tag[0] == '<' && tag[1] == '/' && tag[s - 1] == '>' && op == 0 && sl == 1 && en == s - 1 && s >= 4  )
		cout << "Success" << nline;
	else
		cout << "Error" << nline;
}

Can someone please explain why is this submission(link attached) incorrect?
https://www.codechef.com/viewsolution/48200364

Consider the test input:

1
</4>

Please post your entire, formatted code, or link to your submission :slight_smile:

Edit:

I’ll make a guess - consider the test input:

1
</>>

this gives error for me:-
int n=s.size();
but when i declared n as long long it got submitted. Why n is long long? Constraint says that length(tag) is <=1000.
Can anyone explain this?

Please link to both solutions (the WA one and the AC one).

int main() {
fio;
ll t;
cin>>t;

while(t--){
 string s;
 cin>>s;
 
if(s[0]=='<' and s[1]=='/' and s[s.size() - 1]=='>' and s.size()>3){
    bool check1=1;
    for(ll i=2;i<s.size()-1;i++){
        if(!(s[i]>='a' and s[i]<='z'|| s[i]>='1' and s[i]<='9')){
        
            check1=0;
            break;
        }
        
    }
    if(check1){
        cout<<"Success" nl;
    }
    else{
        cout<<"Error" nl;
    }
}
else{
    cout<<"Error" nl;
}
 
 
}

}

Can some tell me what is wrong in this…i am getting WA.

Can anyone please explain what the error is in my code?

for _ in range(int(input())):
    tag_input = input()
    tag = list(tag_input)
    length = len(tag)
    s = True
    if length > 3 and tag[0: 2] == ['<', '/'] and tag[-1] == '>':     
        for i in range(3, length - 1):
            if '1' <= tag[i] <= '9' or 'a' <= tag[i] <= 'z':
                continue
            else:
                s = False
                break
    else:
        s = False
    if s:
        print('Success')
    else:
        print('Error')

Please post your entire, formatted code, or link to your submission :slight_smile: