KQM23B Editorial

PROBLEM LINK:

Contest
Practice

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Naman Chaurasia

DIFFICULTY: EASY-MEDIUM

PREREQUISITES:

Math

PROBLEM:

given a 2D grid of characters. The characters in the grid can be read from top to down, down to top, left to right, right to left and diagonally(diagonally in all 4 directions NW to SE, SE to NW, NE to SW and SW to NE).
find the number of names found in the grid from given set of names.

QUICK EXPLANATION:

Basically for each name in list L, find a way to check in all 8 directions given, if set of characters are there matching the name.

EXPLANATION:

convert the given grid into a single string combining strings from all 8 directions
eg-: for grid
[a b]
[c d]
strings formed from

  1. top to down: ac, bd
    2.down to top: ca,db
    3.left to right: ab,cd
    4.right to left: ba,dc
    5.NW to SE: c,ad,b
    6.SE to NW: c,da,b
    7.NE to SW: a,bc,d
    8.SW to NE: a,cb,d

Note-: separate each string obtained by a special character.
let this combined string be called STR.
and now just compare if a substring exists in this STR matching the name

calculating time complexity- O(10^5)
grid contains maximum 100 characters
8 possible directions N,S,E,W,NW to SE, SE to NW, NE to SW and SW to NE
length of combined string =8*100 (10^3)
10 strings of 10 characters= 100(10^2)

SOLUTIONS:

Setter's Solution
using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int n=int.Parse(Console.ReadLine());
		string[]ss=Console.ReadLine().Split();
		string[]vv=Console.ReadLine().Split();
		int a=int.Parse(vv[0]);
		int b=int.Parse(vv[1]);
		string[] kk=new string[a];
		for(int i=0;i<a;i++)
		{
			kk[i]=Console.ReadLine();
		}
		int count=0;
		for(int i=0;i<n;i++)
		{
			if(yes(ss[i],kk)){count++;}
		}
		Console.WriteLine(count);
	}
	public static string san(string v,int t)
	{
		if(v.Length<=t)return v;
		return v.Substring(v.Length-t);
	}
	public static bool yes(string s,string[]k)
	{
		for(int i=0;i<k.Length;i++)
		{
			string v="";
			for(int j=0;j<k[0].Length;j++)
			{
				if(k[0].Length-j<s.Length)break;
				v=k[i].Substring(j,s.Length);
				if(v==s)return true;
				if(ret(v)==s)return true;
			}
		}
		for(int i=0;i<k[0].Length;i++)
		{		
			string v="";	
			for(int j=0;j<k.Length;j++)
			{
				v+=k[j][i];
				
				if(san(v,s.Length)==s)return true;
				if(ret(san(v,s.Length))==s)return true;
			}
		}
		
		for(int i=0;i<k.Length;i++)
		{
			for(int j=0;j<k[0].Length;j++)
			{
				string v="";
				for(int t=j,u=i;t<k[0].Length && u>=0;t++,u--)
				{
					v+=k[u][t];
					if(v.Length==s.Length)break;					
				}
				
				if(v==s)return true;
				if(ret(v)==s)return true;
			}
		}
		for(int i=0;i<k.Length;i++)
		{
			for(int j=0;j<k[0].Length;j++)
			{
				string v="";
				for(int t=j,u=i;t<k[0].Length && u<k.Length;t++,u++)
				{
					v+=k[u][t];
					if(v.Length==s.Length)break;
				}
				if(v==s)return true;
				if(ret(v)==s)return true;
			}
		}return false;
	}
	public static string ret(string s)
	{
		
		char[]cc=s.ToCharArray();
		Array.Reverse(cc);
		return new string(cc);
	}
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	ll n,i,j,k,r,c,x,ans=0;
	cin>>n;
	string s[n],com="";
	for(i=0;i<n;i++)cin>>s[i];
	cin>>r>>c;
	string grid[r];
	for(i=0;i<r;i++)cin>>grid[i];
	//left to right
	for(i=0;i<r;i++,com+=".")
	    for(j=0;j<c;j++)
	        com+=grid[i][j];
	//right to left
	for(i=0;i<r;i++,com+=".")
	    for(j=c-1;j>=0;j--)
	        com+=grid[i][j];
	//down to up
	for(j=0;j<c;j++,com+=".")
	    for(i=r-1;i>=0;i--)
	        com+=grid[i][j];
	//up to down
	for(j=0;j<c;j++,com+=".")
	    for(i=0;i<r;i++)
	        com+=grid[i][j];
	//south west
	for(int j=0;j<=r-1+c-1;j++,com+=".")
	    for(int i=0;i<r;i++)
	        if(0<=j-i&&j-i<c)
	            com+=grid[i][j-i];
	//north east
	for(int j=0;j<=r-1+c-1;j++,com+=".")
	    for(int i=r-1;i>=0;i--)
	        if(0<=j-i&&j-i<c)
	            com+=grid[i][j-i];
	//south east
	for(int j=-(c+r);j<=c+r;j++,com+=".")
	    for(int i=0;i<r;i++)
	        if(0<=i+j&&i+j<c)
	            com+=grid[i][i+j];
	//north west
	for(int j=-(c+r);j<=c+r;j++,com+=".")
	    for(int i=r-1;i>=0;i--)
	        if(0<=i+j&&i+j<c)
	            com+=grid[i][i+j];
	//cout<<com<<"\n";
	for(int i=0;i<n;i++)
	    for(int j=0;j+s[i].size()-1<com.size();j++)
	        if(com.substr(j,s[i].size())==s[i])
	        {
	            ans++;
	            break;
	        }
	cout<<ans<<endl;
	return 0;
}