CMPE250-Data Structures and Algorithms Project 5 Solved

Introduction
Year 2045... Humanity has gone through lots of global disasters: epidemics, wars, famines, climate change... Now, the world is different from the one humans remember. The Earth is becoming a more and more uninhabitable place for the human-kind, as the scientists declare. But, if there is science, there is always hope! Always!

The visionary scientists had already started to seek solutions to save humanity and discovered a new species in space. This new species has been the dominant species of its planet for hundreds of millions of years, whereas we, the human-kind, are about to become extinct only in two million years. The scientists investigated the reason behind this and found a simple, yet striking answer: altruism.

The members of this species are all altruistic and care about each other as much as they care about themselves. They behave as a single unit and seek a global maximum for the community, as opposed to seeking self-maximums, which inevitably cause global disasters. Then the question arises: why did they evolve so differently from the human-kind?

The research revealed surprising answers. Similar to human-kind, the members of this species were also too self-oriented initially and cared about only themselves and their close relatives. This resulted in global “disasters” which eventually made them lose the ability to recognize their loved ones, except for their parents. First, they could not know how to treat others as they could not tell if an individual was a part of their family. But then, they have come up with an excellent idea: if we cannot recognize our close ones, why not treat everyone as if they are family?

They internalized this notion so much that they transformed this into an altruistic culture of sharing and caring, and built a sustainable world. They still would love to remember their family members though, and this may be our way to establish communication with them!

We know that each member knows only its parent and would love to learn its greater ancestors. Since there are a lot of individuals in this society, they need an efficient way to find out their ancestors. Luckily, we can design an algorithm to help them, and then hope that, they would teach us to secrets to happy and long cohabitation...

1

The scientists gathered further information about the species that we can utilize to tackle the problem.

The individuals in this society have exactly one parent, except for the first individual that has no parent, the root.
Each individual derives from the same root.
The individuals might have an arbitrary number of children.
Each individual remembers only its parent and does not know further information about its family. The root knows that it has no parent.
We learned all parent-child relations and now they are dying to learn who their nthancestors are. Thus, we need an efficient way to answer their queries. Luckily, we are aware that this problem is a slightly different version of the Level Ancestor problem and know an algorithm[1]for the solution. The world desperately needs you to implement this algorithm... Would you help us? Would you save the world?

2             Input & Output
Your code must read the name of the input and output files from the command line. We will run your code as follows:

g++ *.cpp *.h -std=c++11 -o project5.out

./project5.out inputFile outputFile

If you do not use any “.h” file. Your code will be compiled as follows: g++ *.cpp -std=c++11

-o project5.out

Make sure that your final submission compiles and runs with these commands

2.1           Input
The first line of the input file states the number of individuals I (1 ≤ I ≤ 1000000) and the second line contains the parent id of each individual. Here, the id of an individual is equal to its zero-based index in this line and the root has the parent -1. The third line comprises the number of queries Q and is followed by Q lines (1 ≤ Q ≤ 500000), in which the individuals ask who their nth ancestors are. Each query line contains two integers: the id of the individual and n, separated by a space. The input is guaranteed to form a tree of parent-child relations. Below is the input template; Table 1 displays an example input file on the left and Figure 1 illustrates the example input as a tree.

2

Input
Output
9
0
-1 0 1 0 3 2 4 1 0
3
4
0
1 1

4 1

4 2

6 4
-1
Table 1: Sample input and output files

Query-1 (1 1)
The query asks the first ancestor (parent) of the individual 1. The tree in Figure 1 displays that the first ancestor of the individual 1 is the individual 0, and thus the answer is also 0.
Query-2 (4 1)
The query asks the first ancestor of the individual 4, which is the individual 3.
Query-3 (4 2)
The query asks the second ancestor (parent of its parent, or grand-parent) of the individual 4. Figure 1 shows that the parent of the individual 4 is the individual 3 and its parent is the individual 0. Thus, the answer is also 0.
Query-4 (6 4)
The query asks fourth ancestor of the individual 6, which does not exist. Thus the answer is -1.
Table 2: Explanations for the expected output file.

[1] Here is a link to a simple algorithm: https://arxiv.org/abs/1903.01387. The manuscript contains a small mistake in its Section 2.3 though. The second item of this section should start with “Look up the largest element ssmaller than l”