CHEFSTUD - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

For a given string S[1..N] consisting of characters ‘>’, ‘<‘ and ‘*’, the goal is to find the number of its adjacent characters S[i] and S[i+1], such that after replacing each ‘<‘ in with ‘>’ and each ‘>’ with ‘<‘ in the original string, we have S[i] = ‘>‘ and S[i+1] = ‘<‘.

QUICK EXPLANATION:

If one pays enough attention to the statement, he can notice that each ‘>’ has corresponding ‘<‘ to its right and each ‘<‘ has corresponding ‘>’ to its left. This observation can lead to one simple solution. On the other hand, a solution not taking any advantage of this fact is also simple and possible. Both these approaches are described below.

EXPLANATION:

Approach 1:

Since each ‘>’ has corresponding ‘<‘ to its right and each ‘<‘ has corresponding ‘>’ to its left in the original string, then after all swaps of characters are made, each consecutive blocks of K characters, where no character is ‘*’ will produce (K-2) / 2 adjacent pairs of characters we are looking for. As an example, let’s consider such a block of characters “><><><”. Then after swaps are made it looks like this: “<><><>” and each character with the exception of the first and the last one participates in exactly one pair of consecutive characters we are looking for.

Based on the above approach we can solve the problem as follows.

Since in the first subtask there is no ‘*’ in the input string, then the answer is (N-2) / 2, where N is the length of the input string.

In the general case, one can at the beginning split the input string into substring containing only ‘<‘ and ‘>’ characters and then compute the final answer as the sum of results for all these substrings computed in the same way as described above as the solution for the first subtask.

Approach 2:

Since each ‘>’ is swapped with ‘<‘ and vice versa, then we can just find the number of adjacent characters S[i] and S[i+1] in the original string for which we have S[i] = ‘<‘ and S[i] = ‘>’. This is true because after all swaps are made then each such pair corresponds to a pair that we are interested in. Moreover, on the other hand, each pair of adjacent characters we are interested in the string after all swaps are performed is formed from a pair of adjacent characters ‘<‘ and ‘>’ in the original string. This observation allows us to not perform any swap operations at all.

The second observation is that no two pairs of characters we are interested in can overlap, which is quite straightforward.

Both these two observation can lead to approach based on just counting the number of adjacent pairs of characters ‘<‘ and ‘>’ in the original string. The following pseudocode illustrates this approach:


    result = 0
    for i = 1 to |s| - 1
       if s[i] == ‘<‘ and s[i+1] == ‘>’:
          result += 1
    print result

Both these approaches runs in linear time in terms of the length of the input string.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

2

//CHEFSTUD
//29NOV2016
#include
#include<string.h>
using namespace std;

int main ()
{
char stud[25];
int n;
int Count=0;
int flag=1;
cout << "Please, enter current configuration: ";
cin.getline (stud,25);
n=strlen(stud);
cout<<“Current number of students: “<<n<<”\n”;
cout << "Hello, current configuration is " << stud << “\n”;
for(int i=0; i<25; ++i)
{
if(stud[i]==’>’)
{
stud[i]=’<’;
}
else
if(stud[i]==’<’)
{
stud[i]=’>’;
}
}
cout<<“After teacher is there: “;
cout.write(stud,n);
cout<<”\n”;
for(int i=0; i<25; ++i)
{
if(stud[i]==’>’&&stud[i+1]==’<’)
Count++;
if(stud[i]==’*’)
flag=0;
}
cout<<“Teacher sees: “<<Count<<” student\n”;
if(flag==1)
cout<<“No student is studying!\n”;
return 0;
}
This works on my PC but CodeChef compiler says its wrong, is there a specific way to write answer on CodeChef?

3

//here is the C++ code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
int main()
{
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;
int l=s.size();
int i=0;
while(i<l)
{
if(s[i]==’>’&&s[i+1]==’<’)
{
s[i+1]=’>’;
s[i]=’<’;
i+=2;
}
else
i++;
}
int c=0;
i=0;
while(i<l)
{
if(s[i]==’>’&&s[i+1]==’<’)
{
c++;
i+=2;
}
else
i++;
}
cout<<c<<endl;
}
return 0;
}