Coding Exercise, Episode 1

I have received the following exercise from an interviewer, he didn't give the name of the problem. Honestly, I have no idea how to solve this problem even I have tried to read it three times before. Since I used to be a person who always tells myself "I am not the one good at algorithms", but giving up something too soon which I feel that I didn't spend enough effort to overcome is not my way. Then, I have sticked on it for 24 hours.

According to the given image on the problem, I tried to get more clues by searching. Thanks to Google, I found a similar problem on Hackerrank (attached link below). My target here was trying my best to just understand the problem and was trying to solve it accordingly by the Editorial on Hackerrank. Due to this circumstance, it turns me to love solving algorithms from now on (laugh). Check it out!

Problem

You are given a very organized square of size N (1-based index) and a list of S commands

The i^th command will follow the format (a[i], b[i], d[i]) and will be executed as:

For every elements inside the inner-square whose top-left corner located at (a[i], b[i]) and bottom-right corner located at (a[i] + d[i], b[i] + d[i]) will rotate 90 degree clockwise. And the i^th inner-square always contains (i + 1)^th inner-square

E.g. If the input square with size N = 7 and command (2, 3, 3), the execution will be (image):

After executed S commands, you will then be asked to do L queries to determine the final location given the initial value w[i].
E.g. With the above example, the final position of 25 will be (4, 4) - its initial location was (4, 5)

Input format and constraints

- Line 1: integer N - size of the square (N <= 10^7)

- Line 2: integer S - number of commands (S <= 10^5)

- S subsequent lines: S commands with format (a[i], b[i], d[i]) with constraints

1 <= a[i], b[i] and 0 <= d[i] < N
a[i-1] <= a[i] and a[i] + d[i] <= a[i - 1] + d[i - 1]
b[i-1] <= b[i] and b[i] + b[i] <= b[i - 1] + b[i - 1]

The next line will contains integer L - number of queries (L <= 10^5)

Each subsequent line ask for the final position of a number w[i] (0 <= w[i] < N^2)

Here is one input example

7

2

1 2 4

2 3 3

2

11

24

Here is the output

4 4

2 5

Solution 

(with my commenting on the code)

	package vn.nvanhuong.coding.exercise;
	import java.util.Scanner;
	/**
	* All squares (original & sub-squares) has these following characteristics:
	* [1]. sorted entries
	* + right entry - left entry = 1
	* + below entry - above entry = dimension
	* [2]. if we know smallest entry (T), dimension (N) & orientation -> we can know the rest entries
	*/
	public class Solution {
	public static void main(String[] args) {
	//Step 1. Find smallest entry of each input square. Time complexity: O(S)
	//The value at cell (i,j) of a great square whose smallest entry is T is T + i*N + j
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt(); //N: size of original square
	int s = scanner.nextInt(); //S: numbers of commands
	long[] a = new long[s+1]; //entered rows
	long[] b = new long[s+1]; //entered columns
	long[] d = new long[s+1]; //entered dimension
	long[] t = new long[s+1]; //T: found smallest entries
	//init the original square (already known)
	a[0] = 1;
	b[0] = 1;
	d[0] = n-1;
	t[0] = 0;
	//input and find smallest entries
	int orientationNum = 4;
	for (int i = 1; i <= s; i++) {
	a[i] = scanner.nextInt();
	b[i] = scanner.nextInt();
	d[i] = scanner.nextInt();
	/* for example: T0 = 0, N = 7
	* 0 1 2 3 4 5 6
	* 7 8 9 10 11 12 13
	* 14 15 16 17 18 19 20
	* 21 22 23 24 25 26 27
	* 28 29 30 31 32 33 34
	* 35 36 37 38 39 40 41
	* 42 43 44 45 46 47 48
	* */
	//apply characteristic [2] and formula: V = T + i*N + j
	if (i % orientationNum == 1) {//TOP
	/* command (1,2,4) -> T1 = 0 + (1-1)*7 + (2-1) = 1
	/* % 29 22 15 8 1 %
	* % 30 23 16 9 2 %
	* % 31 24 17 10 3 %
	* % 32 25 28 11 4 %
	* % 33 26 19 12 5 %
	* % % % % % % %
	* % % % % % % %
	* */
	t[i] = t[i-1] + (a[i]-a[i-1])*n + (b[i]-b[i-1]);
	} else if (i % orientationNum == 2) {//RIGHT
	/* command (2,3,3) -> T2 = 1 + ((2+4)-(3+3))*7 + (2-1) = 2
	/* % % % % % % %
	* % % 26 25 24 23 %
	* % % 19 18 17 16 %
	* % % 12 11 10 9 %
	* % % 5 4 3 2 %
	* % % % % % % %
	* % % % % % % %
	* */
	t[i] = t[i-1]+((b[i-1]+d[i-1])-(b[i]+d[i]))*n+(a[i]-a[i-1]);
	} else if (i % orientationNum == 3) {//BOTTOM
	t[i] = t[i-1]+((a[i-1]+d[i-1])-(a[i]+d[i]))*n+((b[i-1]+d[i-1])-(b[i]+d[i]));
	} else if (i % orientationNum == 0) {//LEFT
	t[i] = t[i-1]+(b[i]-b[i-1])*n+((a[i-1]+d[i-1])-(a[i]+d[i]));
	}
	}
	//Step 2. Determine some values
	//Each square is contained in the previous one -> binary search. Time complexity: O(log S)
	//The location of a value v in a great square whose smallest entry is T is ((v-T)/N, (v-T)%N)
	int l = scanner.nextInt(); //L: number of queries
	long[] w = new long[l];
	for (int i = 0; i < l; i++) {
	w[i] = scanner.nextLong();
	int low = 0;
	int high = s;
	//find position of smallest entry
	while (low != high) {
	int mid = (low+high+1)/2;
	if (w[i] >= t[mid] && w[i] < t[mid]+(d[mid]+1)*n && w[i]%n >= t[mid]%n && w[i]%n <= (t[mid]%n)+d[mid]){
	low = mid;
	}else{
	high = mid-1;
	}
	}
	//find position of input number with formula: (i, j) = ((v-T)/N, (v-T)%N)
	long off1 = (w[i]-t[low])/n;
	long off2 = (w[i]-t[low])%n;
	if (low % orientationNum == 0) {//TOP
	System.out.println((a[low]+off1)+" "+(b[low]+off2));
	} else if (low % orientationNum == 1) {//RIGHT
	System.out.println((a[low]+off2)+" "+(b[low]+d[low]-off1));
	} else if (low % orientationNum == 2) {//BOTTOM
	System.out.println((a[low]+d[low]-off1)+" "+(b[low]+d[low]-off2));
	} else if (low % orientationNum == 3) {//LEFT
	System.out.println((a[low]+d[low]-off2)+" "+(b[low]+off1));
	}
	}
	scanner.close();
	}
	}

view raw Coding Exercise.java hosted with ❤ by GitHub

Reference
[1]. https://www.hackerrank.com/challenges/king-richards-knights