CAPIMOVE - Editorial

general
, , , , , , ,
3

can this be solved using DP on Trees?

4

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

5

what is the use of maintaining frequency when it is given that P is distinct

1 Like
6

Can NyOne Tell from where to excel programming in STL using CPP . I am just a beginner.Kindly Reply…

7

@csk111165 You can take help from Hackerrank C++ domain which have specific section of STL!

  1. You can prefer cplusplus website also that will explore you in deep concept!

  2. You should also see Topcoder tutorial!

1 Like
8

can it be done using 2d matrix or 2d vector?

9

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

10

@arjunarul Whats the approach to solve this problem using Segment Tree ? and whats the complexity?

11

link text

I have used very simple logic still runtime error for subtask 3 plz help me

problem:- link text

12

  • 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

13

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.

Link- CodeChef: Practical coding for everyone

Click to view

PS- Is it really brute force? Can we, put certain restrictions on number of operations using the fact that “It is a tree” and observations on degree of nodes? IDK, thats for you to decide~

14

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.
15

I guess this problem hasn’t the solution with DP on trees.

16

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

17

Yes, it’s my fault. We can solve it with simple set. You are absolutely right, thanks!

18

so as you mentioned above this can be solved by simple set also, thanks for clearing that up.

19

it wouldn’t work for subtask 3 , as we cannot create a vector or array of 50000 * 50000 array due to memory constraint

1 Like
20

@priyanshu789, what logic did you applied logic.?

21

no it can be solved using dp on trees !

22

practice and practice and get to know through experience… that will help