Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE LESSONS:

Lesson 1

Iterations

Lesson 2

Arrays

Lesson 3

Time Complexity

Lesson 4

Counting Elements

Lesson 5

Prefix Sums

Lesson 6

Sorting

Lesson 7

Stacks and Queues

Lesson 8

Leader

Lesson 9

Maximum slice problem

Lesson 10

Prime and composite numbers

Lesson 11

Sieve of Eratosthenes

Lesson 12

Euclidean algorithm

Lesson 13

Fibonacci numbers

Lesson 14

Binary search algorithm

Lesson 15

Caterpillar method

Lesson 16

Greedy algorithms

Lesson 17

Dynamic programming

Lesson 90

Tasks from Indeed Prime 2015 challenge

Lesson 91

Tasks from Indeed Prime 2016 challenge

Lesson 92

Tasks from Indeed Prime 2016 College Coders challenge

Lesson 99

Future training

ambitious

Remove at most two edges from a tree graph to maximize the product of the components' sizes.

Programming language:
Spoken language:

Elves in the forest of Glandishar are preparing for an Orc invasion. They have a network of N + 1 guard posts located on the open platforms in the treetops. The posts are numbered from 0 to N and are connected by N bridges, so that one can get from any one guard post to any other guard post in a unique way. In other words, guard posts and bridges form a tree graph.

The Elves are afraid that if the Orcs manage to get hold of one of the guard posts, then they will have easy access to all the other guard posts. Therefore, the Elves have decided to destroy at most two bridges and split the guard posts into at most three separate areas, so that the guards can move within each area but it's not possible to move between the areas.

In each area there will be one guard who will move from guard post to guard post during the night. If the Orcs attack, the guards will raise an alarm. However, if the Orcs manage to guess the guard post in which the guards are currently located, they may manage to take out the guards without raising the alarm. The Elves want to avoid the situation that all guard posts fail this way, by maximizing:

- X * Y * Z, if the guard posts have been divided into three areas consisting of X, Y and Z guard posts, respectively;
- X * Y, if the guard posts have been divided into two areas consisting of X and Y posts, respectively;
- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

You are given a map of the network in the form of two arrays A, B of length N. For each K (0 ≤ K < N) there is a bridge between posts A[K] and B[K].

Write a function:

char * solution(int A[], int B[], int N);

that, given two arrays A and B of N integers, returns the largest possible result. Since the result can be large, you should return it as a string.

For example, given the following arrays:

the function should return "`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Elves in the forest of Glandishar are preparing for an Orc invasion. They have a network of N + 1 guard posts located on the open platforms in the treetops. The posts are numbered from 0 to N and are connected by N bridges, so that one can get from any one guard post to any other guard post in a unique way. In other words, guard posts and bridges form a tree graph.

The Elves are afraid that if the Orcs manage to get hold of one of the guard posts, then they will have easy access to all the other guard posts. Therefore, the Elves have decided to destroy at most two bridges and split the guard posts into at most three separate areas, so that the guards can move within each area but it's not possible to move between the areas.

In each area there will be one guard who will move from guard post to guard post during the night. If the Orcs attack, the guards will raise an alarm. However, if the Orcs manage to guess the guard post in which the guards are currently located, they may manage to take out the guards without raising the alarm. The Elves want to avoid the situation that all guard posts fail this way, by maximizing:

- X * Y * Z, if the guard posts have been divided into three areas consisting of X, Y and Z guard posts, respectively;
- X * Y, if the guard posts have been divided into two areas consisting of X and Y posts, respectively;
- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

You are given a map of the network in the form of two arrays A, B of length N. For each K (0 ≤ K < N) there is a bridge between posts A[K] and B[K].

Write a function:

string solution(vector<int> &A, vector<int> &B);

that, given two arrays A and B of N integers, returns the largest possible result. Since the result can be large, you should return it as a string.

For example, given the following arrays:

the function should return "`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Elves in the forest of Glandishar are preparing for an Orc invasion. They have a network of N + 1 guard posts located on the open platforms in the treetops. The posts are numbered from 0 to N and are connected by N bridges, so that one can get from any one guard post to any other guard post in a unique way. In other words, guard posts and bridges form a tree graph.

The Elves are afraid that if the Orcs manage to get hold of one of the guard posts, then they will have easy access to all the other guard posts. Therefore, the Elves have decided to destroy at most two bridges and split the guard posts into at most three separate areas, so that the guards can move within each area but it's not possible to move between the areas.

In each area there will be one guard who will move from guard post to guard post during the night. If the Orcs attack, the guards will raise an alarm. However, if the Orcs manage to guess the guard post in which the guards are currently located, they may manage to take out the guards without raising the alarm. The Elves want to avoid the situation that all guard posts fail this way, by maximizing:

- X * Y * Z, if the guard posts have been divided into three areas consisting of X, Y and Z guard posts, respectively;
- X * Y, if the guard posts have been divided into two areas consisting of X and Y posts, respectively;
- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

You are given a map of the network in the form of two arrays A, B of length N. For each K (0 ≤ K < N) there is a bridge between posts A[K] and B[K].

Write a function:

class Solution { public string solution(int[] A, int[] B); }

that, given two arrays A and B of N integers, returns the largest possible result. Since the result can be large, you should return it as a string.

For example, given the following arrays:

the function should return "`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

func Solution(A []int, B []int) string

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

class Solution { public String solution(int[] A, int[] B); }

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

function solution(A, B);

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

function solution(A, B)

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

Note: All arrays in this task are zero-indexed, unlike the common Lua convention. You can use `#A` to get the length of the array A.

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

NSString * solution(NSMutableArray *A, NSMutableArray *B);

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

function solution(A: array of longint; B: array of longint; N: longint): PChar;

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

function solution($A, $B);

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

sub solution { my ($A, $B)=@_; my @A=@$A; my @B=@$B; ... }

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

def solution(A, B)

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

def solution(a, b)

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

public func solution(inout A : [Int], inout _ B : [Int]) -> String

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

public func solution(_ A : inout [Int], _ B : inout [Int]) -> String

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

- N + 1, if the guard posts haven't been divided;

depending on which option gives the largest result.

Write a function:

Private Function solution(A As Integer(), B As Integer()) As String

For example, given the following arrays:

`18`" since the Elves can destroy bridges 1−3 and 3−5 (marked as dashed lines in the image above). The created areas consist of 3, 3 and 2 guard posts.

Therefore, the result is 3 * 3 * 2 = 18. It is not possible to obtain a better result.

Given the following arrays:

the function should return "`3`" (it is optimal not to destroy any bridge).

Assume that:

- N is an integer within the range [1..50,000];
- each element of arrays A, B is an integer within the range [0..N];
- distance from guard post 0 to any other post is not greater than 900 bridges.

Complexity:

- expected worst-case time complexity is O(N*log(N));

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN