You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSIGN - Editorial

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

asked 15 Jul '17, 06:48

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 17 Jul '17, 16:41

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 18 Jul '17, 04:35

ahuja_vaibhav's gravatar image

2★ahuja_vaibhav
141
accept rate: 0%

could any one tell why this gives WA https://www.codechef.com/viewsolution/14569995

link

answered 17 Jul '17, 22:47

sierra101's gravatar image

2★sierra101
11
accept rate: 0%

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;
}
link

answered 17 Jul '17, 23:33

hard_c0d3r's gravatar image

2★hard_c0d3r
1
accept rate: 0%

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 '><<<><<'

link

answered 18 Jul '17, 20:47

zodiac_bestro's gravatar image

2★zodiac_bestro
1
accept rate: 0%

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...

https://pastebin.com/6QJRau0v

http://i64.tinypic.com/2rmwima.png

link

answered 18 Jul '17, 20:57

blank_0014's gravatar image

1★blank_0014
1
accept rate: 0%

Can anybody tell me what's wrong with it.

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

link

answered 20 Jul '17, 17:12

anchal24's gravatar image

2★anchal24
-31
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×1,024
×968
×229
×22

question asked: 15 Jul '17, 06:48

question was seen: 2,044 times

last updated: 20 Jul '17, 17:12