[help] Educational Codeforces Round 2 : E. Lomsat gelral Codeforces

help
,
1

Can Someone help me here -

Problem - http://codeforces.com/contest/600/problem/E .

Spoiler [Alert] - Proceed further only if you have done this question and submitted or You have no plan to submit this question (But want to help me :P).

If you want to give this question a try then open this only after trying the question.

Click to view

My soln - http://codeforces.com/contest/600/submission/38786344 .

Editorial -
http://codeforces.com/blog/entry/21827

Please explain me this also -
Editorial Approach - for Each moving can be done in O(logn) time And why ML/TLE will not be there in worst case.
In my opinion worst case.
n=100000.
Colors all distinct.
vertices -
i i+1 i.e. tree is bamboo . Only 1 and n has one neighbour. And 1<i<n have neighbours i-1,i+1

2

You can refer this blog on dsu on trees. This problem is the one discussed in blog and provides you with various solutions.

1 Like
3

Thanks for blog and quick response.

1 Like
4

No problem. (Although don’t mind my very late response).

1 Like
5

Here is the link to my code : https://repl.it/@NikhilAgrawal/lomsat-gelral

Basic logic is to compute the frequency of every color in the subtree of node and then find the color with maximum frequency and sum them.

But the complexity will be greater than n^2 because for every node we have perform dfs(i.e. O(n) ).

So, what can we do to reduce it’s complexity?

Every line of code seems to be normal and quite intuitive and naive at first sight. But what is special about this code???
To understand that you need to pay attention to line 20 and 21. Only these two lines contribute to reducing complexity from n^2 to n*log(n).

But question is how?

Notice that it’s always the smaller map which gets added or merged with larger map. So, let’s say there is a node A in map m. When smaller map is merged with larger map, minimum size of resulting map is 2*(size of smaller map). So, Every node at max gets added log(n) times. So the total complexity is nlog(n).*

P.S : In my piece of code I have used INF and INF+1 to store the count of max color and it’s sum respectively.

1 Like