Author: Maksym Bevza
Tester: Arjun Arul
Editorialist: Misha Chorniy
Difficulty:
Simple
Pre-Requisites:
none
Problem Statement
You are given tree consisting N nodes. Each node i has value P_{i} assigned to it. All values P_{i} are distinct. For each node j find maximal value of node in the graph if to remove nodes adjacent to j and j.
Explanation
Subtask 1 and 2
N is less or equal than 10000. For each node will mark all nodes which are adjacent to it as dead(not usable), will find maximum value between non-marked nodes.
for i= 1..N
//Step 1
for j=1..N
alive[j] = 1; //initialize all marks as ones
//Step 2
alive[i] = 0; //mark itself as dead
for v is adjacent to i //mark all adjacent nodes
alive[v] = 0; //mark neighbours as dead
ans[i] = 0;
//Step 3
for j=1..N
if alive[j]==1 //if node j is alive
ans[i]= max(ans[i],p[j]); //find maximum value
How long it works? Obviously, the complexity of first and third step is O(N), how to find the complexity of the second step? Denote D(v) - degree of node v, for vertex i complexity of step 2 is equal to D(i), over all iterations complexity of second step is D(1)+D(2)+…+D(N), what is 2*(N-1) for trees, we see that each edge using exactly two times.
Total complexity of this algorithm is O(N*N+2*(N-2)+N*N) = O(N^2)
First and third steps are slowest in the code above, how to optimize it? We can rewrite that code a bit.
for i=1..N
alive[i]=1;
for i=1..N
alive[i]=0;
for v is adjacent to i
alive[v] = 0;
ans[i]=0;
for j=1..N
if alive[j] == 1 //if node j is non-marked
ans[i] = max(ans[i],p[j]); //update answer
alive[i]=1;
for v is adjacent to i
alive[v] = 1;
Now total complexity is O(N+2*(N-2)+N*N+2*(N-2)) = O(N^2), still O(N^2), we can make some observations, basically we have set, where the following operations can be performed:
- alive_{i}=1 is equivalent to adding in the set value of p_{i}
- alive_{i}=0 is equivalent to erasing in the set value of p_{i}
Subtask 3
Let’s use some data structure, namely in our case, the data structure which can add/erase elements, and find the maximal value in the set of these elements, but does this thing in time less than O(N).
for i=1..N
add(P[i]);
for i=1..N
erase(P[i]);
for v is adjacent to i
erase(P[v]);
ans[i] = getMaximalValue();
add(P[i]);
for v is adjacent to i
add(P[v]);
What is the best data structure for these things, in most of the modern programming languages exists built-in data structures for such things, in C++ you can use set, Java has Set, Python has similar data structures. If your language doesn’t have built-in data structures, you can read about heaps (Priority Queues) and realize it.
Let’s write code with the map in C++, the similar code can be written in Java with Map or in Python with the dictionary.
set < int > S;
for i=1..N // Step 0
S.insert(P[i]); //Initialize set
//Adding element P[i] in the set
for i=1..N
//Step 1
S.erase(P[i]); //Erase value of node i from set
for v is adjacent to i //Iterate over neighbours of node i
S.erase(P[v]) //Erase values of neighbours of i
//Step 2
if !S.empty()
ans[i] = *S.rbegin(); //Value of greatest element
//Step 3, rollback of the step 1
S.insert(P[i]); //Insert value of node i from set
for v is adjacent to i //Iterate over neighbours of node i
S.insert(P[v]) //Insert values of neighbours of i
Complexity of adding/erasing of number in such data structures is O(log N), summary complexity of the first steps is O(N log N), the same is for third steps,
Total complexity is O(N log N + N log N + N log N + N log N) = O(N log N)
The overall time complexity of this approach is O(N log N).
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.
