Fri. Mar 31st, 2023

CodeChef Solution

Check Algorithm Codechef Solution

ByBrokenprogrammers

Dec 10, 2022 CodeChef, CodeChef Solution, programs

Check Algorithm Codechef Solution

Hello Programmers In this post, you will know how to solve the Check Algorithm Codechef Solution.

Check Algorithm Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

One day, Saeed was teaching a string compression algorithm. This algorithm finds all maximal substrings which contains only one character repeated one or more times (a substring is maximal if it we cannot add one character to its left or right without breaking this property) and replaces each such substring by the string “cK”, where KK is the length of the substring and cc is the only character it contains. For example, “aabaaa” is compressed to “a2b1a3”.

Saeed wanted to check if the students understood the algorithm, so he wrote a string SS on the board and asked the students if the algorithm is effective on SS, i.e. if the string created by compressing SS is strictly shorter than SS. Help them answer this question.

Input

The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
The first and only line of each test case contains a single string SS.

Output

For each test case, print a single line containing the string "YES" if the algorithm is effective on SS or "NO" if it is not.

Constraints

1≤T≤1001≤T≤100
1≤|S|≤1031≤|S|≤103
SS may consist of only lowercase English letters.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1

3
bbbbbbbbbbaa
c
aaaaaaaaaabcdefgh

Sample Output 1

YES
NO
NO

Explanation

Example case 1:

The compressed string of “bbbbbbbbbbaa” is “b10a2”, which is shorter.
The compressed string of “c” is “c1”, which is not shorter than “c”.
The compressed string of “aaaaaaaaaabcdefgh” is “a10b1c1d1e1f1g1h1”, which is not shorter than “aaaaaaaaaabcdefgh” (both strings have length 1717).

Check Algorithm CodeChef Solutions in JAVA

/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
	    int t = input.nextInt();
	    while(t-- >0){
	       String S = input.next();
	       StringBuilder br = new StringBuilder();
	       int count = 0;
	       char a = S.charAt(0);
	       for(int i = 0; i<S.length(); i++){
	           char c = S.charAt(i);
	           if(a == c ){
	               count++;
	           }else if(a != c || i == S.length()){
	                br.append(a);
	                br.append(count);
	                a = S.charAt(i);
	                count = 1;
	           }
	       }
	       br.append(a);
	       br.append(count);
    	   String A = br.toString();
    	   if(S.length() > A.length()){
    	       System.out.println("YES");
    	   }else{
    	       System.out.println("NO");
    	   }
	    }
	}
}

Check Algorithm CodeChef Solutions in CPP

#include <bits/stdc++.h>
using namespace std;
int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    string s;
	    cin>>s;
	    int count=1,rc=0;
	    for(int i=0; i<s.size()-1; i++)
	    {
	        if(s[i]==s[i+1])
	        {
	            count++;
	        }
	        else
	        {
	            rc++;
	            if(count<10)
	            {
	                rc++;
	            }
	            else
	            {
	                while(count>0)
	                {
	                    rc++;
	                    count/=10;
	                }
	            }
	             count=1;
	        }
	    }
	    if(s[s.size()-1]!=s[s.size()-2])
	    {
	        rc+=2;
	    }
	    else
	    {
	        rc++;
	            if(count<10)
	            {
	                rc++;
	            }
	            else
	            {
	                while(count>0)
	                {
	                    rc++;
	                    count/=10;
	                }
	            }
	    }
	    if(rc<s.size())
	    {
	        cout<<"YES"<<endl;
	    }
	    else
	    {
	        cout<<"NO"<<endl;
	    }
	}
	return 0;
}

Check Algorithm CodeChef Solutions in Python

for _ in range(int(input())):
    a=input()
    b=len(a)
    c=''
    if b==1:
        print("NO")
    else:
        count=1
        for i in range(1,b):
            if a[i]==a[i-1]:
                count+=1
            else:
                c+=a[i-1]+str(count)
                count=1
        if a[-1]!=a[-2]:
            c+=a[-1]+'1'
        else:
            c+=a[-1]+str(count)
        if len(c)>=len(a):
            print("NO")
        else:
            print("YES")

Disclaimer: The above Problem (Check Algorithm ) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Chef and Coins Game Codechef Solution

By Brokenprogrammers

Related Post

CodeChef Solution

Brackets Codechef Solution

Dec 24, 2022 Brokenprogrammers

CodeChef Solution

A Big Sale Codechef Solution

Dec 24, 2022 Brokenprogrammers

CodeChef Solution

TV Discount Codechef Solution

Dec 23, 2022 Brokenprogrammers

Leave a Reply Cancel reply