×

# CAPIMOVE - Editorial

Author: Maksym Bevza
Tester: Arjun Arul
Editorialist: Misha Chorniy

Simple

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

$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}$

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 (http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html) 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.

This question is marked "community wiki".

7★mgch
125314
accept rate: 7%

 1 I would like to share my approach : First I sorted the population and stored its index using structure. Then I sorted the list of connected planets in the increasing order of planets and decreasing order of the population of the planets they are connected . Plus , each planet is connected to itself. It gave AC in 0.19 s. You can have a look on my solution here : https://www.codechef.com/viewsolution/12589162 It just requires simple pre-requisite knowledge of ability to sort structures. :) answered 18 Jan, 16:58 754●9 accept rate: 15%
 1 what is the use of maintaining frequency when it is given that P is distinct answered 20 Jan, 01:07 44●4●4●11 accept rate: 0% Yes, it's my fault. We can solve it with simple set. You are absolutely right, thanks! (20 Jan, 01:51) mgch7★
 1 @csk111165 You can take help from Hackerrank C++ domain which have specific section of STL! You can prefer cplusplus website also that will explore you in deep concept! You should also see Topcoder tutorial! answered 20 Jan, 12:44 2.6k●1●10 accept rate: 16%
 0 can this be solved using DP on Trees? answered 18 Jan, 17:13 1 accept rate: 0% I guess this problem hasn't the solution with DP on trees. (18 Jan, 20:18) mgch7★
 0 not able to understand why multiset ideology is used. and why do we need this piece of code?(or) why do we need to maintain the frequency of element? for i=1..N // Step 0 F[P[i]] += 1; //Initialize multiset //Add element P[i] into mutliset, F[i] -MAINTAIN FREQUENCY OF ELEMENT i in mutliset answered 18 Jan, 22:02 1 accept rate: 0% We are maintaining multiset in pairs (x, cx), where cx denoting frequency of the number x in multiset. {4, 2, 4, 3, 4} = {(2, 1), (3, 1), (4, 3)} (19 Jan, 04:38) mgch7★ so as you mentioned above this can be solved by simple set also, thanks for clearing that up. (20 Jan, 20:06)
 0 Can NyOne Tell from where to excel programming in STL using CPP . I am just a beginner.Kindly Reply.. answered 20 Jan, 11:05 1 accept rate: 0%
 0 can it be done using 2d matrix or 2d vector? answered 21 Jan, 00:00 72●6 accept rate: 0% 1 it wouldn't work for subtask 3 , as we cannot create a vector or array of 50000 * 50000 array due to memory constraint (22 Jan, 11:39) smsubham3★
 0 I tried to solve this problem using adjacency list and set, and I use map iterator for finding index of maximum value. here is my implementation that takes 0.52 sec to give AC. https://www.codechef.com/viewsolution/12614486 tag used: Adjacency list, set, map, iterator answered 21 Jan, 11:38 14●1 accept rate: 0% @priyanshu789, what logic did you applied logic.? (27 Feb, 15:29)
 0 @arjunarul Whats the approach to solve this problem using Segment Tree ? and whats the complexity? answered 25 Feb, 14:03 1 accept rate: 0%
 0 link text I have used very simple logic still runtime error for subtask 3 plz help me problem:- link text answered 14 Jun, 16:39 2★code_man 17●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,106
×780
×535
×511
×123
×122
×113
×10