Tasks Details
medium
In how many ways can you split a kingdom into two parts, so that the parts contain equal number of gold mines?
Task Score
100%
Correctness
100%
Performance
100%
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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 16 minutes
Notes
not defined yet
Code: 06:42:08 UTC,
java,
autosave
Code: 06:52:29 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
}
}
}
Code: 06:52:59 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int med_
}
}
}
Code: 06:53:25 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
}
}
}
Code: 06:53:36 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
X = Arrays.
}
}
}
Code: 06:54:06 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
X = Arrays.sort(X);
Y = Arrays.sort(Y);
int ret =
}
}
}
Code: 06:54:28 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
X = Arrays.sort(X);
Y = Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) +
}
}
}
Code: 06:54:45 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
X = Arrays.sort(X);
Y = Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Code: 06:54:49 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
X = Arrays.sort(X);
Y = Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Analysis
Compile error
Solution.java:16: error: cannot find symbol
X = Arrays.sort(X);
^
symbol: variable Arrays
location: class Solution
Solution.java:17: error: cannot find symbol
Y = Arrays.sort(Y);
^
symbol: variable Arrays
location: class Solution
2 errors
Code: 06:55:17 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Arrays.sort(X);
Y = Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Code: 06:55:18 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Arrays.sort(X);
Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Analysis
Compile error
Solution.java:16: error: cannot find symbol
Arrays.sort(X);
^
symbol: variable Arrays
location: class Solution
Solution.java:17: error: cannot find symbol
Arrays.sort(Y);
^
symbol: variable Arrays
location: class Solution
2 errors
Code: 06:55:31 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Array.sort(X);
Array.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Analysis
Compile error
Solution.java:16: error: cannot find symbol
Array.sort(X);
^
symbol: variable Array
location: class Solution
Solution.java:17: error: cannot find symbol
Array.sort(Y);
^
symbol: variable Array
location: class Solution
2 errors
Code: 06:56:12 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Array.sort(X);
Array.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Code: 06:56:15 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Arrays.sort(X);
Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Analysis
Code: 06:57:20 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Arrays.sort(X);
Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}
Analysis
Code: 06:57:24 UTC,
java,
final,
score:
100
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int M, int[] X, int[] Y) {
// write your code in Java SE 8
if(X.length % 2 > 0) return 0;
else
{
int mid_x = X.length / 2;
int mid_y = Y.length / 2;
Arrays.sort(X);
Arrays.sort(Y);
int ret = (X[mid_x] - X[mid_x - 1]) + (Y[mid_y] - Y[mid_y - 1]);
return ret;
}
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N+M+K)
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
8.
0.004 s
OK
9.
0.008 s
OK
10.
0.008 s
OK
11.
0.004 s
OK
12.
0.004 s
OK
13.
0.004 s
OK
14.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
expand all
Performance tests
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.432 s
OK
1.
0.004 s
OK
2.
0.088 s
OK
1.
0.004 s
OK
2.
0.576 s
OK
1.
0.004 s
OK