Tasks Details
hard
1.
OddNetwork
Given a tree graph, find the number of pairs of vertices whose distance is odd.
Task Score
100%
Correctness
100%
Performance
100%
You analyze the performance of a computer network. The network comprises nodes connected by peer-to-peer links. There are N links and N + 1 nodes. All pairs of nodes are (directly or indirectly) connected by links, and links don't form cycles. In other words, the network has a tree topology.
Your analysis shows that communication between two nodes performs much better if the number of links on the (shortest) route between the nodes is odd. Of course, the communication is fastest when the two nodes are connected by a direct link. But, amazingly, if the nodes communicate via 3, 5, 7, etc. links, communication is much faster than if the number of links to pass is even.
Now you wonder how this influences the overall network performance. There are N * (N + 1) / 2 different pairs of nodes. You need to compute how many of them are pairs of nodes connected via an odd number of links.
Nodes are numbered from 0 to N. Links are described by two arrays of integers, A and B, each containing N integers. For each 0 ≤ I < N, there is a link between nodes A[I] and B[I].
Write a function:
class Solution { public int solution(int[] A, int[] B); }
that, given two arrays, A and B, consisting of N integers and describing the links, computes the number of pairs of nodes X and Y, such that 0 ≤ X < Y ≤ N, and X and Y are connected via an odd number of links.
For example, given N = 6 and the following arrays:
A[0] = 0 B[0] = 3 A[1] = 3 B[1] = 1 A[2] = 4 B[2] = 3 A[3] = 2 B[3] = 3 A[4] = 6 B[4] = 3 A[5] = 3 B[5] = 5
the function should return 6, since:
- there are six pairs of nodes connected by direct links, and
- all other pairs of nodes are connected via two links.
Given N = 5 and the following arrays:
A[0] = 0 B[0] = 1 A[1] = 4 B[1] = 3 A[2] = 2 B[2] = 1 A[3] = 2 B[3] = 3 A[4] = 4 B[4] = 5
the function should return 9, since:
- there are five pairs of nodes connected by direct links,
- there are three pairs of nodes connected via three links, and
- there is one pair of nodes connected via five links.
Given N = 7 and the following arrays:
A[0] = 0 B[0] = 3 A[1] = 4 B[1] = 5 A[2] = 4 B[2] = 1 A[3] = 2 B[3] = 3 A[4] = 7 B[4] = 4 A[5] = 6 B[5] = 3 A[6] = 3 B[6] = 4
the function should return 16, since:
- there are seven pairs of nodes connected by direct links, and
- there are nine pairs of nodes connected via three links.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..90,000];
- each element of arrays A and B is an integer within the range [0..N];
- the network has a tree topology;
- any pair of nodes is connected via no more than 1000 links.
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 11 minutes
Notes
not defined yet
Code: 06:43:53 UTC,
java,
autosave
Code: 06:51:25 UTC,
java,
autosave
Code: 06:51:55 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int)
}
}
Code: 06:52:26 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int) i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
}
}
Code: 06:52:54 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int) i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!)
}
}
Code: 06:53:22 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int) i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int node = q.poll();
for(int i : map[node]){
if(dist[i] != -1){
continue;
}
dist[i] = (1 + dist[node])%2;
}
}
}
}
Code: 06:53:51 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int) i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int node = q.poll();
for(int i : map[node]){
if(dist[i] != -1){
continue;
}
dist[i] = (1 + dist[node])%2;
q.add(i);
}
}
int odd = 0;
for(int i : dist){
odd += i;
}
return (n - odd)*odd;
}
}
Analysis
Compile error
Solution.java:15: error: not a statement
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: ';' expected
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: ';' expected
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: illegal start of expression
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: ')' expected
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: > expected
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: not a statement
for(int) i = 0; i < A.length; i++){
^
Solution.java:15: error: ';' expected
for(int) i = 0; i < A.length; i++){
^
8 errors
Code: 06:54:01 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int node = q.poll();
for(int i : map[node]){
if(dist[i] != -1){
continue;
}
dist[i] = (1 + dist[node])%2;
q.add(i);
}
}
int odd = 0;
for(int i : dist){
odd += i;
}
return (n - odd)*odd;
}
}
Code: 06:54:02 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int node = q.poll();
for(int i : map[node]){
if(dist[i] != -1){
continue;
}
dist[i] = (1 + dist[node])%2;
q.add(i);
}
}
int odd = 0;
for(int i : dist){
odd += i;
}
return (n - odd)*odd;
}
}
Analysis
Code: 06:54:10 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int node = q.poll();
for(int i : map[node]){
if(dist[i] != -1){
continue;
}
dist[i] = (1 + dist[node])%2;
q.add(i);
}
}
int odd = 0;
for(int i : dist){
odd += i;
}
return (n - odd)*odd;
}
}
Analysis
Code: 06:54:17 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[] A, int[] B) {
// write your code in Java SE 8
int n = A.length + 1;
ArrayList<Integer>[]map = new ArrayList[n];
for(int i = 0; i < n; i++){
map[i] = new ArrayList<>();
}
for(int i = 0; i < A.length; i++){
map[A[i]].add(B[i]);
map[B[i]].add(A[i]);
}
int[]dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int node = q.poll();
for(int i : map[node]){
if(dist[i] != -1){
continue;
}
dist[i] = (1 + dist[node])%2;
q.add(i);
}
}
int odd = 0;
for(int i : dist){
odd += i;
}
return (n - odd)*odd;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.012 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
1.
0.012 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
expand all
Correctness/performance tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
4.
0.012 s
OK
1.
1.080 s
OK
expand all
Performance tests
1.
0.028 s
OK
2.
0.032 s
OK
3.
0.032 s
OK
4.
0.032 s
OK
1.
0.052 s
OK
2.
0.052 s
OK
3.
0.052 s
OK
4.
0.040 s
OK
1.
1.096 s
OK
1.
1.148 s
OK
2.
1.212 s
OK
1.
1.144 s
OK
2.
1.144 s
OK