PROBLEM LINK:
Setter- Hasan Jaddouh
Tester- Ivan Safonov
Editorialist- Abhishek Pandey
DIFFICULTY:
CAKEWALK
PRE-REQUISITES:
Strings, Arrays, ASCII system for characters
PROBLEM:
Given a string S on N characters, we have to perform the following operations-
- swap adjacent characters. Eg- Swap 1 with 2, 3 with 4 and so on.
- swap every alphabet OF THE ORIGINAL STRING with its mirror reverse, i.e. if ASCII value of the character is K , swap it with character of ASCII value 'a'+('z'-K). Hence, 'a' is replaced by 'z', 'b' with 'y' and so on.
QUICK EXPLANATION:
Key to AC- This is a majorly implementation question. Proper practice in these topics is the key to quick AC.
Swapping of the adjacent characters is trivial. The replacement of alphabets can be easily done by realizing that every alphabet is replaced by 'a'+('z'-K) counterpart, where K is ASCII value of the character.
EXPLANATION:
This editorial will have only a single section, as its majorly an easy implementation problem. We will be discussing setter’s solution owing to its neat implementation.
1.Setter’s solution-
The first thing to carry out is the swap operation. Remember the kind of swapping. Let me denote character at index i with c_i. We have to swap c_0 with c_1, c_2 with c_3 and so on. Familiarity with arrays and strings is needed. You can use a temporary variable for swapping, or perhaps put std::swap function from C++ STL. Both the ways are given in tab below-
Click to view
1. Using std::swap-
for(int i=0;i< n-1;i+=2){
swap(s[i],s[i+1]);
}
2. Using temporary variable-
for(int i=0;i< n-1;i+=2){
char c=s[i];
s[i] = s[i+1];
s[i+1] = c;
}
Now all that remains is to do the alphabet replacing. We can do that trivially using the formula given above. An example is given under tab. We will replace s[i] with s[i]='a'+('z'-s[i]);
Click to view
for(int i=0;i< n;i++){
s[i] = 'z' + 'a'- s[i];
}
SOLUTION:
The codes of setter and tester are pasted below in tabs for you guys to refer if the links dont work. @admin needs some time for linking solutions, hence code was pasted for your convenience.
Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n;
string s;
int main(){
T=readIntLn(1,1000);
while(T--){
n=readIntLn(1,100);
s=readStringLn(n,n);
for(int i=0;i<n;i++){
assert('a'<=s[i] && s[i]<='z');
}
for(int i=0;i<n-1;i+=2){
char c=s[i];
s[i] = s[i+1];
s[i+1] = c;
}
for(int i=0;i<n;i++){
s[i] = 'z' + 'a'- s[i];
}
cout<<s<<endl;
}
assert(getchar()==-1);
}
Click to view
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
// read template
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
// end
void solve()
{
int n;// = readIntLn(1, 100);
cin >> n;
string s;// = readStringLn(n, n);
cin >> s;
assert((int)s.size() == n);
bool ch = true;
for (int i = 0; i < n; i++) ch &= ('a' <= s[i] && s[i] <= 'z');
assert(ch);
for (int i = 0; i < n - 1; i += 2) swap(s[i], s[i + 1]);
for (int i = 0; i < n; i++) s[i] = (char)((int)'a' + (int)'z' - (int)s[i]);
cout << s << "\n";
}
int main()
{
int T;// = readIntLn(1, 1000);
cin >> T;
while (T--) solve();
//assert(getchar() == -1);
return 0;
}
Time Complexity= O(N)
CHEF VIJJU’S CORNER 
1. Some contestants wrote a logic similar to below while coding for swapping part-
for(int i=0;i< n-1;i++){
char c=s[i];
s[i] = s[i+1];
s[i+1] = c;
}
Is something wrong there? :o
2. This time, we were able to derive a formula. What if, this wouldnt be possible? What if mapping would had been random, eg - Replace ‘a’ with ‘g’, ‘h’ with ‘i’, ‘b’ with also ‘g’ , or perhaps what if mapping would be given in input? Its easy still! Just make an array of size 26 and store which alphabet is i'th one mapped to. Meaning, table[i] would store the character to which alphabet with ASCII 'a'+i gets mapped to. Now, another version, what if I say that the characters are upto {10}^{9}, but only {10}^{5} are used and need to be mapped? I want to bring std::map data structure to your attention. 