CHEFSIGN - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given a sequence of N arithmetic signs ( = , + , - ) between N+1 unknown integers. You are allowed to fix these integers using numbers in the range [1,P] such that the expression is true when you read it from left to right. (Numbers don’t violate the signs). You are asked to calculate minimum possible P such you can construct a valid expression.

EXPLANATION:

First of all, it’s clear that we can drop all ‘=’ signs and pretend that they never existed, because each number which follows an ‘=’ sign would be identical to the number preceding this sign. So these signs aren’t affecting our answer at all.
After discarding all ‘=’ signs our answer would be :

P = max(maximum number of consecutive ‘<’ signs, maximum number of consecutive ‘>’ signs) + 1

Let’s process our expression from left to right, If we are facing X (X ≤ P-1) consecutive ‘<’ signs, our starting number would be P-X, and we increment our last number by 1 after each sign,so the number after the last sign would be exactly P (which will be followed by ‘>’ sign). Our last number will be followed by Y consecutive ‘>’ signs, so we assign the next number to Y (Y < P) and we decrement the last number by 1 by each ‘>’ sign we process. The number after the last sign would be 1. (In case our expression starts with ‘>’ the situation would just be reversed).
After that we would have another block of Z consecutive ‘<’ signs, so we assign the next number to P-Z (P-Z ≥ 1) so the number after the last sign would be P and we continue…

Following this approach, the last number after a block of consecutive ‘<’ signs would be P (the maximal value), and the last number after a block of consecutive ‘>’ signs would be 1 (the minimal value). So according to our bold assumption below we can assign values using numbers in the range [1,P] without violating the signs.

Let’s take an example:

<<<=>=>=>>><<>>>><<<<<>><<>>

After removing = signs our sequence would be

<<< >>>>> << >>>> << >>>>>

(Blocks are separated by spaces for clarity)

here P = max(3 , 5 , 2 , 4 , 5 , 2 , 2 , 2) + 1 = 6

Our sequence would be

3 < 4 < 5 < 6 > 5 > 4 > 3 > 2 > 1 < 5 < 6 > 4 > 3 > 2 > 1 < 5 < 6 > 5 > 4 > 3 > 2 > 1

AUTHOR’S AND TESTER’S SOLUTIONS:

TESTER’s solution: Will be found here
EDITORIALIST’s solution: Will be found here

1 Like
2

could any one tell why this gives WA CodeChef: Practical coding for everyone

3

I am also getting few of the testcases accepted and others wrong answer.
https://www.codechef.com/viewsolution/14563406

Please help me find my mistake!

#include <iostream>
#define lli long long int
using namespace std;

int main(void) {
    int t;
    cin >> t;
    while(t--){
        char s[100011];
        lli tmp = 1, pmax = 1, pmin = 1;
        lli i;
        lli ans;
        cin >> s;
        for(i = 0; s[i] != '\0'; i++){
            if(s[i] == '<'){
                tmp++;
            } else if(s[i] == '>'){
                tmp--;
            }
            if(pmax < tmp) pmax = tmp;
            if(pmin > tmp) pmin = tmp;
        }
        //cout << pmax << " " << pmin << endl;
        if(pmin < 1) {
            ans = pmax - pmin + 1;
        } else {
            ans = pmax;
        }
        cout << ans << endl;
    }
    return 0;
}
4

Yes, In both of your codes, you guys are assuming that the numbers increase or decrease by 1, which is not always the case.
Consider this,
str = ‘><<<><<’

Your code will give the answer as 5.
your answer == 2>1<2<3<4>3<4<5

but the actual answer would be 4
== 2>1<2<3<4>1<2<3

like this.

6 Likes
5

Here is my code … what do you think is wrong about it. Please, help me find my mistakes

#include <bits/stdc++.h>

using namespace std;

#define fast_cin ios_base::sync_with_stdio(false)

typedef long long ll;

int main()
{
	fast_cin;
	ll t; cin >> t;
	while(t--){
		string s; cin >> s;
		ll in = 1, ans = 0;
		for (int i = 0; i < s.size(); ++i)
		{
			if (s[i] == '<')
			{
				in++;
				ans = max(ans,in);
			}
			else if (s[i] == '>')
			{
				in = 1;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

It is giving current answer for string s = '<<<=>=>=>>><<>>>><<<<<>><<>>'or ‘><<<><<’

6

can any one pls tell me why am i not able to pass 2 cases in main task… ? i have my code and screen shot of my result here…

7

Can anybody tell me what’s wrong with it.

https://www.codechef.com/viewsolution/14523196

8

editorial code is best i like the algo is used in coding.

9

same…

10

I am having some difficulty. I don’t know why some test cases are failing.
What my code does is to scan through the string, and increment currScore every time the character in hand is same as the character at the previous place, and when the character is different, I update maxScore as max of of the two and updates currScore as 0.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string removeEqual( string str){
    long long int strLength =str.length();
    string ansStr="";
    for(long long int i=0;i< strLength; i++){
        if( str[i] != '='){
            ansStr= ansStr+ str[i];
        }
    }
    return ansStr;
}

long long int maxNoOfContSymbols (string str){
    
    long long int currMax=0;
    long long int currScore=0;
    long long int strLen =str.length();
    
    for(long long int i=1; i< strLen; i++){
        
        if(str[i-1] == str[i]){
            currScore++;
        }
        else{
            currMax=max(currMax,currScore);
            currScore=0;
        }
    }
    currMax=max(currMax,currScore);
    return currMax+2;
}

int main() {
	
	long long int T;
	cin>>T;
	long long int t=0;
	while(t <T){
	    
	    string str;
	    cin>>str;
	    
	    cout<<maxNoOfContSymbols( removeEqual( str))<<endl;
	    
	    t++;
	}
	
	return 0;
}