RootChutney

Salt pans from top of City wall - Ston

View of Split up top - Marjan Hill, Split

Fort of Meereen from Game of Thrones and neighboring Split - Kliss Fortress

Hvar town center - Hvar

Dubovica beach - Hvar

View of Hvar from Spanish Fort - Hvar

Dubrovnik Port - Dubrovnik

Shops and squares - Dubrovnik

Another location prop for Game of Thrones - Lovrjenac fortress, Dubrovnik

Another great view of Dubrovnik

Another interesting problem around binary search trees ->

Given the insertion order of nodes in a binary search tree, find the distance between two nodes in the tree.

The brute force way to approach this will be -
- To build the tree [which is O(nlogn)]
- Look for the two nodes in the tree and construct paths from root to node [which is O(logn)]
- Find the distance between two nodes based on the path found above [ worst case O(n) in time complexity but average case of O(log n) as well]

Hence, giving us an effective time complexity of O(nlogn)

But there is a better way to get to the distance without building the tree [thanks to a colleague of mine, Harish for suggesting the solution]

We rely on narrowing down the search space(maximum and minimum values) on the insertion order as we go inserting/finding nodes, pretty much similar to finding if a given tree is a valid binary search tree.

The solution for the problem relies on two variables 'rangeMin' and 'rangeMax' for keeping tabs on the current search space/insertion space of a node. Using this, we figure out the path from the root node to the given node if a binary search tree was to be constructed using the nodes inserted in the order given without any balancing of the tree.

- rangeMin is updated when given node is greater than current node and current node is greater than current rangeMin(hence moving nearer to the given node from the bottom search space)

- rangeMax is updated when given node is lesser than current node and current node is lesser than current rangeMax(hence moving nearer to the given node from the upper search space)

For example, take the insertion order {9,1,5,7,8,10,12,4,6}

If a tree were to be constructed using the same, it would look like -

fig 1 - Binary Search Tree constructed using given insertion order

If we were looking to find path from root to node 4, the rangeMin, rangeMax changes and node path from root to node would look like this ->

rangeMin	rangeMax	Path from root to node
MIN_INT	MAX_INT	[ ]
MIN_INT	9	[9]
1	9	[9,1]
1	5	[9,1,5]
...Skipped as out of range	...Skipped as out of range	...Stays the same until 4 encountered
1	5	[9,1,5,4]

Similarly, the path from root to node 6 goes as follows -

rangeMin	rangeMax	Path from root to node
MIN_INT	MAX_INT	[ ]
MIN_INT	9	[9]
1	9	[9,1]
5	9	[9,1,5]
5	7	[9,1,5,7]
...Skipped as out of range	...Skipped as out of range	...Stays the same until 6 encountered
5	7	[9,1,5,7,6]

The code is available here.

The time complexity for the above solution is -
- Look for the two nodes in the insertion order and construct paths from root to node [which is O(n)]
- Find the distance between two nodes based on the path found above [ worst case O(n) but average case of O(log n) as well]

Giving us an effective time complexity of O(n)

Where rainbows start and never end !! [Route 36 (Thingvallavegur)]

Divide and erode [Thingvellir National Park]

Striking Strokur [Geysir]

The golden falls [Gulfoss]

Although a cloudy picture, but the famous Eyjafjallajökull to the right and Katla in the center [Hvolsvollur]

The joy of standing behind a waterfall [Seljalandsfoss]

Just another big waterfall and a trailhead for a lot of cool things [Skogafoss]

The huge landscape that leads to Skogafoss [somewhere up top Skogafoss]

That glacier lagoon bled so much blue, the sky had that hue. [Jokulsarlon]

Footsteps in the dark [Black sand beach in Eastern Fjords]

Just another lake hard to miss [outside of Egilstadir]

Some snaky carvings into the sunset [Dettifoss]

I feel so close to you right now, its a force field !! [Dettifoss]

Modern architecture for churches from cities to villages [Akureykirkja, Akureyri]

That apocalyptic feeling [Grabrok crater]

When a mountain looks like a church, you call it "Church Mountain" !! [Kirkjufell]

Breidafjordur bay and its islands [Stykkisholmur]

Snaefellsjokull and a foss created by it [Snaefellsjokull National Park]

Ice and Fire petrified together. [Saxholl crater - Snaefellsjokull National Park]

Snaefellsness Peninsula and Snaefellsjokull at the end [somewhere in Snaefellsness]

Came across another interesting problem on hackerrank related to range sum query in 3 dimensions.

The question goes as below -

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries.

UPDATE x y z W

updates the value of block (x,y,z) to W.

QUERY x1 y1 z1 x2 y2 z2

calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive).

We will stick to creating a fenwick tree here in case of a cube although this question has larger implication in the database world for calculating sums and averages and has much better solutions like lazy propagation of segment trees, quad trees and octet trees.

I wont go deeper into explaining fenwick trees/ binary indexed tree as there are many blogs and videos explaining the same but I highly recommend this link to visualize the workings of it for any application. A question arises as to why use Fenwick tree and not segment tree for this question and the general rule of thumb would be its easier to code Fenwick tree and any application that can be solved using that, should make use of fenwick trees as segment trees have a wide range of applications and provide more flexibility in exchange for heavy maintainability of code/application.

The central idea around creation of Fenwick trees is to affect the minimal number of nodes during an update operation and also use minimum while calculating a metric from it. The main gist around doing this is as follows :-

Populating next/child node ->

2's complement of current node index
AND it with current node index
ADD to current node index

Calculating parent node ->

2's complement of current node index
AND it with current node index
SUBTRACT it from current node index.

For a range sum query on a two dimensional space from point (1,1) to (3,3), the calculation on the Fenwick tree can be visualized as below :-

fig 2 : 2D Range sum query

which can be formulated as -

sum(row2+1, col2+1) - sum(row1, col2+1) - sum(row2+1, col1) + sum(row1,col1) = ∑(row1, col1) to (row2,col2)

Similarly, for a range sum query on a three dimensional space from point (1,1,1) to (4,4,3), the calculation on the Fenwick tree can be visualized as below :-

fig 3 : 3D Range sum query

which can be formulated as -

sum(x2+1,y2+1,z2+1) - sum(x1,y1,z1) - sum(x1,y2+1,z2+1) - sum(x2+1,y1,z2+1) - sum(x2+1,y2+1,z1) + sum(x1,y1,z2+1) + sum(x1,y2+1,z1) + sum(x2+1,y1,z1) = ∑(x1, y1, z1) to (x2, y2, z2)

Pasting the solution code in Java below. A minor confusion can be caused when submitting solution to hackerrank as for this problem, the arrays start from 1 instead of 0 and hence an array with n as 3 goes from 1,1,1 to 3,3,3.

New Document

import java.io.*;
import java.util.*;

public class Solution {
    long[][][] tree;
    long[][][] nums;
    private int dimensions = 0;
    
    public Solution(int dimensions) {
        if (dimensions == 0) return;
        this.dimensions = dimensions;
        tree = new long[dimensions+1][dimensions+1][dimensions+1];
        nums = new long[dimensions][dimensions][dimensions];
    }
    
    public void update(int x, int y, int z, int value) {
        long delta = value - nums[x][y][z];
        nums[x][y][z] = value;
        for (int i = x + 1; i <= dimensions; i += i & (-i)) {
            for (int j = y + 1; j <= dimensions; j += j & (-j)) {
                for (int k = z + 1; k <= dimensions; k += k & (-k)) {
                    tree[i][j][k] +=  delta;
                }
            }
        }
    }
    
    public void query(int x1, int y1, int z1, int x2, int y2, int z2) {
        long result = sum(x2+1,y2+1,z2+1) - sum(x1,y1,z1) - sum(x1,y2+1,z2+1) - sum(x2+1,y1,z2+1) - sum(x2+1,y2+1,z1) + sum(x1,y1,z2+1) + sum(x1,y2+1,z1) + sum(x2+1,y1,z1);
        System.out.println(result);
    }
    
    public long sum(int x, int y, int z) {
        long sum = 0l;
        for (int i = x; i > 0; i -= i & (-i)) {
            for (int j = y; j > 0; j -= j & (-j)) {
                for (int k = z; k > 0; k -= k & (-k)) {
                    sum += tree[i][j][k];
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner ob = new Scanner(System.in);
  Solution solution = null;
        int testcases = ob.nextInt();
        ob.nextLine();
        for (int i = 0; i < testcases; i++) {
            String numsLine = ob.nextLine();
            String[] numsLineParts = numsLine.trim().split(" ");
            int dimensions = Integer.valueOf(numsLineParts[0]);
            int numOperations = Integer.valueOf(numsLineParts[1]);
            solution = new Solution(dimensions);
            for (int j = 0; j < numOperations; j++) {
                String line = ob.nextLine();
                String[] lineParts = line.split(" ");
                if (lineParts[0].equals("UPDATE")) {
                    solution.update(Integer.valueOf(lineParts[1])-1, Integer.valueOf(lineParts[2])-1,             Integer.valueOf(lineParts[3])-1, Integer.valueOf(lineParts[4]));
                }
                if (lineParts[0].equals("QUERY")) {
                    solution.query(Integer.valueOf(lineParts[1])-1, Integer.valueOf(lineParts[2])-1,             Integer.valueOf(lineParts[3])-1, Integer.valueOf(lineParts[4])-1, Integer.valueOf(lineParts[5])-1, Integer.valueOf(lineParts[6])-1);
                }
            }
        }
    }
}

The time complexity of this solution is O(log(X) * log(Y) * log(Z)) = O(log(N))³