Golden award for dividing The Kingdom

In the last few months I didn’t have much spare time for writing posts on this blog or maybe I was just being lazy. But that doesn’t mean that nothing interesting was happening during this period. So the next few post will be some “retro” stuff from the previous months and I think deserve to be published here. This post will be about the “Digital Gold” Codility challenge.

DivideTheKingdom

I got a “Golden Award” for this solution so here are the details about the challenge task:

An old king wants to divide his kingdom between his two sons. He is well known for his justness and wisdom, and he plans to make a good use of both of these attributes while dividing his kingdom.

The kingdom is administratively split into square boroughs that form an N × M grid. Some of the boroughs contain gold mines. The king knows that his sons do not care as much about the land as they do about gold, so he wants both parts of the kingdom to contain exactly the same number of mines. Moreover, he wants to split the kingdom with either a horizontal or a vertical line that goes along the borders of the boroughs (splitting no borough into two parts).

The goal is to count how many ways he can split the kingdom.

Write a function:

class Solution { public int solution(int N, int M, int[] X, int[] Y); }

that, given two arrays of K integers X and Y, denoting coordinates of boroughs containing the gold mines, will compute the number of fair divisions of the kingdom.

For example, given N = 5, M = 5, X = [0, 4, 2, 0] and Y = [0, 0, 1, 4], the function should return 3. The king can divide his land in three different ways shown on the picture below.

Write an efficient algorithm for the following assumptions:

  • N and M are integers within the range [1..100,000];
  • K is an integer within the range [1..100,000];
  • each element of array X is an integer within the range [0..N−1];
  • each element of array Y is an integer within the range [0..M−1].

And here is my award certificate:

DigitalGoldChallengeAward.png

This was my last Codility challenge for 2018, but my hunger for algorithms is back again and I’m planning tackle new Codility challenges in 2019 and even try some other contests.

Happy coding,

J.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s