×

# CHEFSTUD - Editorial

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

CAKEWALK

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.

This question is marked "community wiki".

73484290
accept rate: 12%

18.5k348495529

//CHEFSTUD //29NOV2016

# 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?

1
accept rate: 0%

//here is the C++ code

# include <bits stdc++.h="">

using namespace std;

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

2★salman_1
1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×14,071
×1,369
×28
×3

question asked: 26 Nov '16, 19:51

question was seen: 3,591 times

last updated: 12 Jan '17, 11:35