[Solution] Increase 2 consecutive characters solution codechef

Increase 2 consecutive characters solution codechef – Chef has 22 strings AA and BB of equal length NN. Both strings contain lowercase english alphabets only.

Chef can perform several moves on string AA. In one move, Chef has to:

  • Select an index i (1iN1)i (1≤i≤N−1).
  • Replace A[i]A[i] with (A[i]+1)(A[i]+1).
  • Replace A[i+1]A[i+1] with (A[i+1]+1)(A[i+1]+1).

Increase 2 consecutive characters solution codechef

For example, if A=𝚊𝚋𝚌𝚣𝚎A=abcze, a valid move would be to select index 33. This way the string becomes 𝚊𝚋𝚍𝚊𝚎abdae after performing the move. Note that the value at an index is cyclically incremented. This means that, 𝚊𝚋a→b𝚋𝚌b→c𝚣𝚊z→a.

Chef has been asked to answer QQ queries. Each query is of the form:

  • LL RR: Given 1LRN1≤L≤R≤N, Chef wants to know if it is possible to convert the substring A[L,R]A[L,R] to B[L,R]B[L,R] by performing the above mentioned move any number of times.

For each query, output in a single line 𝚈𝚎𝚜Yes, if the conversion is possible using any number of moves. Otherwise, print 𝙽𝚘No.

NOTE: Queries are independent. Thus, the original strings AA and BB would be retained to process next query.

Input Format

  • The first line will contain TT – the number of test cases. Then the test cases follow.
  • First line of each test case contains two integers N,QN,Q.
  • Second line of each test case contains string AA.
  • Third line of each test case contains string BB.
  • QQ lines follow, where the ithith line contains two integers LiRiLiRi – the ithith query.

Increase 2 consecutive characters solution codechef

Output QQ lines, where the ithith line contains the answer to the ithith query. The answer is 𝚈𝚎𝚜Yes, if the conversion is possible using any number of moves. Otherwise, the answer is 𝙽𝚘No.

You may print each character of the string in uppercase or lowercase (for example, the strings 𝚢𝙴𝚜yEs𝚢𝚎𝚜yes𝚈𝚎𝚜Yes and 𝚈𝙴𝚂YES will all be treated as identical).

Constraints

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • 1Q21051≤Q≤2⋅105
  • 1LRN1≤L≤R≤N
  • Sum of NN over all test cases does not exceed 21052⋅105.
  • Sum of QQ over all test cases does not exceed 21052⋅105.

Increase 2 consecutive characters solution codechef

 

1
5 3
abcdz
nbhea
2 2
1 3
4 5

Sample Output 1 

Yes
No
Yes

Increase 2 consecutive characters Explanation

Test Case 11:

  • For the first query, the substring A[2,2]=𝚋A[2,2]=b is already same as B[2,2]=𝚋B[2,2]=b. Thus, the answer is 𝚈𝚎𝚜Yes.
  • For the second query, it can be proven that the substring A[1,3]A[1,3] can never be made equal to B[1,3]B[1,3] using any number of moves.
  • For the third query, the substring A[4,5]=𝚍𝚣A[4,5]=dz and B[4,5]=𝚎𝚊B[4,5]=ea. Applying the move on index 44, we get A[4]=𝚎A[4]=e and A[5]=𝚊A[5]=a. Hence, after one move, A[4,5]=B[4,5]A[4,5]=B[4,5]. Thus, the answer is 𝚈𝚎𝚜Yes in this case.

For Solution

Click Here

Leave a Comment