×

# 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".

6★mgch
3451128
accept rate: 23%

 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 '17, 16:58 1.2k●10 accept rate: 15%
 1 what is the use of maintaining frequency when it is given that P is distinct answered 20 Jan '17, 01:07 44●4●4●12 accept rate: 0% Yes, it's my fault. We can solve it with simple set. You are absolutely right, thanks! (20 Jan '17, 01:51) mgch6★ no it can be solved using dp on trees ! (01 Nov '17, 20:30) pk3013★
 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 '17, 12:44 2.8k●1●4●18 accept rate: 16%
 0 can this be solved using DP on Trees? answered 18 Jan '17, 17:13 1 accept rate: 0% I guess this problem hasn't the solution with DP on trees. (18 Jan '17, 20:18) mgch6★
 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 '17, 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 '17, 04:38) mgch6★ so as you mentioned above this can be solved by simple set also, thanks for clearing that up. (20 Jan '17, 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 '17, 11:05 1 accept rate: 0%
 0 can it be done using 2d matrix or 2d vector? answered 21 Jan '17, 00:00 163●9 accept rate: 4% 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 '17, 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 '17, 11:38 15●2 accept rate: 0% @priyanshu789, what logic did you applied logic.? (27 Feb '17, 15:29)
 0 @arjunarul Whats the approach to solve this problem using Segment Tree ? and whats the complexity? answered 25 Feb '17, 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 '17, 16:39 3★code_man 4●6 accept rate: 8%
 0 This can be done using 2 heaps too if one isn't familiar with sets. Maintain 2 max heaps 1 of all the Pi's Other of the Pi's of V and it's neighbours Check if the top element (max element) of 1st queue is greater than that of 2nd, if yes stop If not, check if they're equal, if yes, pop both of them out of the heap If 1st is less than 2nd, pop the max element of 2nd heap Do this recursively until you exit from the first case. Add the deleted elements back in the 1st heap. Do this recursively for all nodes. Complexity is O(nlogn). Link to my solution : https://www.codechef.com/submit/complete/17494602 answered 21 Feb '18, 01:55 11●1 accept rate: 0%
 0 Seeing so many people happy with their solutions passing in 0.16-0.19 seconds....I am feeling weird coz my brute force passed in 0.09 seconds xD. That too, unoptimized :p. View Content answered 27 Jun '18, 02:11 15.2k●1●18●60 accept rate: 18%
 0 As an interesting aside: because the network is a tree, there can only be at most three alternative capitals, one of which is of course the next most populous planet NxtPop: case 1: NxtPop is directly connected to the capital; then you need at most two more planets, drawn from three groups: the other capital neighbours, the other NxtPop neighbours, and all other planets case 2: NxtPop and the capital have a common neighbour; then you need one more planet that is not adjacent to that common neighbour case 3: NxtPop and the capital have no common neighbours; then you do not need any other planet. answered 07 Aug '18, 04:35 5★joffan 948●8 accept rate: 13%
 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,391
×1,164
×775
×699
×155
×138
×125
×10

question asked: 18 Jan '17, 03:50

question was seen: 4,581 times

last updated: 07 Aug '18, 04:46