PROBLEM LINK
Market Arrangement
Author:-Faiz Alam
Editorialist:-Faiz Alam
Tester:-Prasoon Jain
PREREQUISITES
String Searching Algorithm
PROBLEM
There is a market in ChefLand with N shops, marked from integers 0 to 9. Now, some of these shops (0 or more) from the end of the market were cyclic shifted. We are given initial arrangement of shops in the market and the modified arrangement of shops. We have to tell if the modified arrangement of shops is cyclic shifted or not. If modified arrangement is properly cyclic shifted it is good arrangement else it is bad arrangement.
EXPLANATION
To find weather modified arrangement is cyclic shifted or not we can simply find the occurence of modified arrangement in arrangement s which is equivalent to s=initial arrangement concatenated with initial arrangement. If we find it we return GOOD else
BAD.
SOLUTIONS
Setter's Solution (O(N) solution
#include <bits/stdc++.h>
using namespace std;
void computeLPSArray(string pat, int M, int* lps);
bool check(string pat, string txt)
{
int M = pat.length();
int N = txt.length();
// create lps[] that will hold the longest prefix suffix
// values for pattern
int lps[M];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
return true;
j = lps[j - 1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i]) {
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return false;
}
// Fills lps[] for given patttern pat[0..M-1]
void computeLPSArray(string pat, int M, int* lps)
{
// length of the previous longest prefix suffix
int len = 0;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0) {
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int A[n];
int B[n];
for(int i=0;i<n;i++)
{
cin>>A[i]; //Creating Original Sequence of Shop
}
for(int i=0;i<n;i++)
{
cin>>B[i]; //Taking Modified Sequence of Shops from the User as input
}
string a;
string b;
for(int i=0;i<n;i++)
{
a+=to_string(A[i]);
}
for(int i=0;i<n;i++) //Making Original sequnece as a string equivalent to twice of original array
{ // if A=[1,2,3,4] then string a= 12341234
a+=to_string(A[i]);
}
for(int i=0;i<n;i++)
{
b+=to_string(B[i]); //Making modified sequence of shops as string
}
// cout<<a<<" "<<b;
if(check(b,a))
{
cout<<"GOOD\n";
}
else
{
cout<<"BAD\n";
}
}
}
Tester's Solution
import java.util.Scanner;
class MarketArrang {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t>0) {
int n=sc.nextInt();
int initialArr[]=new int[n];
int finalArr[]=new int[n];
for(int i=0;i<n;i++) {
initialArr[i]=sc.nextInt();
}
for(int i=0;i<n;i++) {
finalArr[i]=sc.nextInt();
}
int isGood=0;
for(int j=0;j<n;j++) {
int i=0;
int temp=j;
while(finalArr[temp]==initialArr[i]) {
i++;
temp=(temp+1)%n;
if(i==n-1) {
break;
}
}
if(i==n-1) {
isGood=1;
break;
}
}
if(isGood==1) {
System.out.println("GOOD");
}
else {
System.out.println("BAD");
}
t--;
}
} }
Complexity:-O(N^2)