MINECRFT - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Code Battle 2021.1.2

Author: Utkarsh Goel , Aditya Rana
Tester: Akshit Monga , Utkarsh Goel
Editorialist: Saksham Aggarwal

DIFFICULTY:

EASY

PREREQUISITES:

Basic Maths, Binary Search

PROBLEM:

Given a 2D array and another 1D array, we have to find the positions(coordinates) of 1D array numbers in 2D array.

QUICK EXPLANATION:

In each query, we have to search the coordinates of the block of a particular height given in query.

EXPLANATION:

  1. Brute Force Approach: Use linear search to find every query number(height). Run a for loop from i=0 till i=n-1 and another nested for loop from j=0 till j=m-1. Now search by comparing every element of 2D array till you find the query number. Repeat the same procedure for every query element.

  2. Optimised Approach: Consider the first query element. First binary search the element in first row. If not found, search in next row. If found in that row, break the loop. It is given that query element exists and will definitely be found in one of the rows. Print the row and column. Repeat the same procedure for every query element.

  3. Another more optimised approach can be to use binary search 2 times, first to find the required row, and another to find required element in that row. The implementation of this approach is left as an exercise for reader so that there is scope for exploration.

COMPLEXITIES:

TIME: O(N*logM) , O(N) for considering each row and O(logM) for binary searching in each row, in optimised approach.
SPACE: O(1), no extra space required.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	long long t;
	cin >> t;
	while (t--)
	{	
		long long n, m, q;
		cin >> n >> m >> q;
		long long a[n][m];
		for (long long i = 0; i < n; i++)
		{
			for (long long j = 0; j < m; j++)
			{
				cin >> a[i][j];
			}
		}
		for (long long Q = 0; Q < q; Q++)
		{
			long long l;
			cin >> l;
			bool found = false;
			for (long long i = 0; i < n; i++)
			{
				auto it = lower_bound(a[i], a[i] + m, l);
				if ((it - a[i]) >= m) continue;
				if (a[i][(it - a[i])] == l)
				{
					cout << i << " " << (it - a[i]) << endl;
					found = true;
					break;
				}
				if (found) break;
			}	
		}
	}
	return 0;
}
Tester's Solution 
    '''Author- Akshit Monga'''
import sys
from sys import stdin, stdout
# input = stdin.readline
# sys.stdin = open('input.txt', 'r')
t = int(input())
# assert t<=10
for _ in range(t):
    n,m,q=map(int,input().split())
    # assert n<=100 and m<=100 and q<=10**5
    vals=[]
    for i in range(n):
        temp=list(map(int,input().split()))
        for j in temp:
            # assert j<=10**8
            vals.append(j)
    # assert len(vals)==len(set(vals))
    s=-1
    for i in vals:
        assert i>=s
        s=i
    hash={}
    c=-1
    for i in range(n):
        for j in range(m):
            c+=1
            if vals[c] not in hash:
                hash[vals[c]]=(i,j)
    # for i in range(n*m):
    #     hash[vals[i]]=i
    for i in range(q):
        h=int(input())
        # assert h<=10**8
        # row=h//m
        # col=(h%m-1)%m
        row,col=hash[h]
        stdout.write(str(row)+" "+str(col)+'\n')
1 Like