KETEKI3D Editorial

PROBLEM LINK:

Practice
Contest

Author: Digvijay Janartha
Tester: Chandan Boruah
Editorialist: Gaurav Jaiswal

DIFFICULTY:
EASY-MEDIUM

PREREQUISITES:
Binary search, prefix sum

EXPLANATION:
The idea to solve this problem is to use a 2D-prefix sum to calculate number
of characters in a square/rectange.
Prefix[i][j] stores the number of characters included in the area formed by rectange,
whose co-ordinates are (1,1),(1,j),(i,1),(i,j).
For each query, we do binary search to find the minimum length of diagonal of square,
which covers all the characters that are needed to form the string.
For implementation of the above, that how do we calculate prefix sum you can see setter’s code.

SOLUTIONS:

Setter's Solution
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
 
using namespace std;
using namespace __gnu_pbds;
 
template < typename T > using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    int len = comma - names;
    for (int i = 0; i < len; ++i) {
        cout << names[i];
    }
    cout <<  " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif
 
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef pair < int, int > pii;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef gp_hash_table < int, int > fast;
 
#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define unique_sort(x) (sort(x.begin(), x.end()), x.resize(distance(x.begin(), unique(x.begin(), x.end()))))
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
const ll LINF = LLONG_MAX, base = 1e9, MOD = 1e9 + 7, N = 1e3 + 5, M = 1e3 + 5;
const int INF = INT_MAX;
const db PI = acos(-1), EPS = 1 / db(1e6);
 
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
 
int n, m, q, x, y, pre[N][N][26], cnt[26];
 
void test();
bool check(int side);
 
int main() {
    fast_io();
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    cout << fixed << setprecision(15);
    test();
    #ifndef ONLINE_JUDGE
        cout << "Time: " << (int)(clock() * 1000. / CLOCKS_PER_SEC) << "ms";
    #endif
    return 0;
}
 
void test() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            ++pre[i][j][c - 'a'];
        }
    }
    for (int k = 0; k < 26; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                pre[i][j][k] += pre[i - 1][j][k] + pre[i][j - 1][k] - pre[i - 1][j - 1][k];
            }
        }
    }
    cin >> q;
    while (q--) {
        cin >> x >> y;
        string s;
        cin >> s;
        for (auto &c: s) {
            ++cnt[c - 'a'];
        }
        int lo = 1, hi = min(m - y, n - x) + 1, mid, ans = -1;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (check(mid)) {
                hi = mid - 1, ans = mid;
            } else {
                lo = mid + 1;
            }
        }
        cout << (ans == -1 ? -1 : ans * ans) << "\n";
        fill(cnt, cnt + 26, 0);
    }
}
 
bool check(int side) {
    int e = side + x - 1, f = side + y - 1;
    for (int k = 0; k < 26; ++k) {
        int cur = pre[e][f][k] + pre[x - 1][y - 1][k] - pre[e][y - 1][k] - pre[x - 1][f][k];
        if (cur < cnt[k]) {
            return false;
        }
    }
    return true;
}
Tester's Solution
using System;
using System.Collections.Generic;
class some

{
	public static void Main()
	{
		test();
	}
	public static int[]cnt;
	public static int[,,]pre;
	public static void test()
	{
		string[]ss=Console.ReadLine().Split();
		int n=int.Parse(ss[0]);
		int m=int.Parse(ss[1]);
		pre=new int[n+1,m+1,26];
		for(int i=1;i<=n;i++)
		{
			string tt=Console.ReadLine();
			for(int j=1;j<=m;j++)
			{
				++pre[i,j,int.Parse(""+(tt[j-1]-'a'))];
			}
		}
		for(int k=0;k<26;k++)
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{
					pre[i,j,k]+=pre[i-1,j,k]+pre[i,j-1,k]-pre[i-1,j-1,k];
				}
			}
		}
	
		int q=int.Parse(Console.ReadLine());
		while(q-->0)
		{
			string[]tt=Console.ReadLine().Split();
			int x=int.Parse(tt[0]);
			int y=int.Parse(tt[1]);
			string s=Console.ReadLine();
			
			cnt=new int[26];
			foreach(char cc in s)
			{
				cnt[int.Parse(""+(cc-'a'))]++;
			}
			
			int lo=1;int hi=Math.Min(m-y,n-x)+1;
			int mid=0;int ans=-1;
			while(lo<=hi)
			{
				mid=lo+(hi-lo)/2;
				if(check(mid,x,y))
				{
					hi=mid-1;ans=mid;
				}
				else
				{
					lo=mid+1;
				}
			}
			
			if(ans==-1)
				Console.WriteLine(-1);
			else
				Console.WriteLine(ans*ans);
		}
	}
	public static bool check(int side,int x,int y)
	{
		int e=side+x-1;
		int f=side+y-1;
		for(int k=0;k<26;k++)
		{
			int cur=pre[e,f,k]+pre[x-1,y-1,k]-pre[e,y-1,k]-pre[x-1,f,k];
			
			if(cur<cnt[k])
			{
				return false;
			}
		}
		
		return true;
	}
}
1 Like