You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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.

View Content

asked 31 May '18, 04:39

aryanc403's gravatar image

5★aryanc403
2.2k1516
accept rate: 10%

closed 18 Oct '18, 03:45

The question has been closed for the following reason "The question is answered, right answer was accepted" by aryanc403 18 Oct '18, 03:45


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

link

answered 31 May '18, 04:47

taran_1407's gravatar image

6★taran_1407
3.8k2383
accept rate: 22%

1

Thanks for blog and quick response.

(31 May '18, 04:53) aryanc4035★
1

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

(01 Jun '18, 14:48) taran_14076★

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.

link

answered 01 Jun '18, 17:42

kaneki13's gravatar image

4★kaneki13
645
accept rate: 16%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×2,698
×655

question asked: 31 May '18, 04:39

question was seen: 328 times

last updated: 18 Oct '18, 03:45