ENCMSG- Editorial

cook96
implementation
string

#1

PROBLEM LINK:

Div1
Div2
Practice

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*,s[i+1]); }

2. Using temporary variable-

for(int i=0;i< n-1;i+=2){ char c=s*; s* = 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* with s*='a'+('z'-s*);

Click to view

for(int i=0;i< n;i++){ s* = 'z' + 'a'- s*; }

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.

Setter

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

‘);
}
string readStringLn(int l,int r){
return readString(l,r,’
‘);
}
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* && s*<='z');
		}
		for(int i=0;i<n-1;i+=2){
			char c=s*;
			s* = s[i+1];
			s[i+1] = c;
		}
		for(int i=0;i<n;i++){
			s*  = 'z' + 'a'- s*;
		}
		cout<<s<<endl;
	}
	assert(getchar()==-1);
} 

Tester

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

');
}

string readStringLn(int l,int r){
	return readString(l,r,'

');
}

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* && s* <= 'z');
	assert(ch);
	for (int i = 0; i < n - 1; i += 2) swap(s*, s[i + 1]);
	for (int i = 0; i < n; i++) s* = (char)((int)'a' + (int)'z' - (int)s*);
	cout << s << "

";
}

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 :smiley:

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*; s* = 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* 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. :slight_smile:


#2

Hi everyone, I have a curiosity here. Instead of swapping the values, can’t we dynamically print the output? Here a sample code to explain my point. TestCases on IDE runs well but at the end while submitting I get WA. Any help will be great.

Language:C

int main()
{
    int T;
    scanf("%d",&T);
    do{
        int B;
        scanf("%d",&B);
        char str**;
        scanf("%s",str);
        for(int i=0; i< ((B/2)*2); i++){
            if(i%2==0){
                printf("%c",219 - str[i+1]);
            }else{
                printf("%c",219 - str[i-1]);
            }
        }
        if(B%2 != 0)
            printf("%c

",219 - str[B-1]);
}while(T–>1);
return 0;
}


#3

#include <stdio.h>
#include <string.h>
void main(){
char S[100]
int T
scanf("%d",&T);
scanf("%d",&N);
gets(S);
if (N%2==0)
{
for(j=N;j>=0;j–){
str[j]=str[j–];
goto nextstep;
exit();
}
}
else
{
nextstep:
for (int i = 0; i < N; i++)
{
temp=str*;
str*=str[i+1];
str[i+1]=temp;
break;
}
for (int k = 0; k < N; k++)
{
str[k] = ‘z’ + ‘a’- str[k];
}
}
printf("%s",str);
}

can anyone help…


#4

@imvarnit_1996

  1. you can’t use void main(). You have to use int main() with return statement at end.
  2. taking character array of length 100 is wrong because in the end there is null character of each string and any string of length 100 wouldn’t fit in the array.
  3. for(j=N;j>=0;j++) is wrong. Nth character would be NULL.

I don’t know what logic you used because of poor readability of code but I hope this helps.


#5

Yes, instead of swapping you can do it directly as well. Take two characters every iteration, print the second character’s corresponding alphabet first, then do same for first one.