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

×

CHEFSTUD - Editorial

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.

This question is marked "community wiki".

asked 26 Nov '16, 19:51

pkacprzak's gravatar image

pkacprzak ♦♦
61382963
accept rate: 16%

edited 26 Nov '16, 23:01

admin's gravatar image

admin ♦♦
13.1k346482500


//CHEFSTUD //29NOV2016

include <iostream>

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?

link

answered 29 Nov '16, 03:26

sidsudhanshu's gravatar image

sidsudhanshu
1
accept rate: 0%

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

link

answered 12 Jan, 11:35

salman_1's gravatar image

salman_1
1
accept rate: 0%

toggle 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

Tags:

×8,659
×800
×23
×3

Asked: 26 Nov '16, 19:51

Seen: 2,653 times

Last updated: 12 Jan, 11:35