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

×

TSUM2- Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Haotian Yuan
Tester- Jakub Safin
Editorialist- Abhishek Pandey

DIFFICULTY:

HARD

PRE-REQUISITES:

Centroid Decomposition, Lines in 2-D Geometry, Convex Hull

PROBLEM:

Given a weighted tree with $N$ nodes, we have to maximize the expression $\large \sum_{i=1}^{k} i*W_{v_i}$ where $\large |W_{v_i}|$ can also be negative.

QUICK EXPLANATION:

Key Strategy- The first part hinting at usage of centroid decomposition or a similar strategy is intuitive. The solution is completed by correlating the reduced sub-problem (obtained after centroid decomposition) with Convex hull and lines in $2-D$ plane. Other implementations/correlations are possible.

We will use the divide and conquer concept of centroid decomposition first. Using this, along with some transformation, the tester reduced the problem to one of "For a given set of lines $y=kx+b$, which line has maximum $y$ for a given value of $x$. This is easily solved by maintaining a convex hull (upper convex hull, to be more specific) and Binary search on the set of lines.

EXPLANATION:

This was the hardest problem of the set. It is expected that you'd go through the concept of centroid decomposition to understand the editorial. Also, if you are aware of how clever transformations can literally change the dimension of problem, then its a plus :)

The editorial will mainly discuss setter's solution. You can open his code in another tab and correlate it with parts of editorials if you want. The idea of tester is also same.

This editorial is divided into a two sections. The first will discuss setter's idea of the problem, and other will discuss various parts of his implementation. Some questions/hand-exercises will be left for you to enjoy as well :). Any exercise whose solution I feel should be given, will be at Chef Vijju's Corner at the end of editorial.

1. Setter/Tester's Idea-

The first thing to note is, there are a total of ${N}^{2}$ possible paths (any of the $N$ can be the source and any of the $N$ can be the destination. Hence $Total$ $Paths=N*N={N}^{2}$). This is one of the key hints that a technique like centroid decomposition should be used. However, unlike centroid decomposition's algorithm, it can be done without needing to "actually" modify the given tree.

Now, he correlated the problem to $2-D$ geometry using the given transformation. Please make sure you thoroughly try to understand this part. I will explain the idea of transformation. You should then try to derive the exact transformation used by setter.

$Answer=$ $\large max(\sum_{i=1}^{i=k} i*W_{v_i})$ for any path. Say, $i=c$ is centroid (i.e. centroid is the $c'th$ vertex in path.) $W_c$ is weight of centroid.

Now-

$Ans=\large max(\sum_{i=1}^{i=k} i*W_{v_i})=W_{v_1}+2*W_{v_2}....+c*W_c+(c+1)*W_{v_{c+1}}...k*W_{v_k}$

$=Sum \space of\space contribution\space of\space paths\space up\space to\space centroid\space+\space Contribution\space of\space path\space down\space from\space centroid\space$

$\large = \underbrace{\sum_{i=1}^{i=c} {i*W_{v_i}} } _ {Path \space to \space centroid}+\underbrace{{(\sum_{i=c+1}^{i=k} {i*W_{v_i}})}}_{Path \space down \space from \space centroid}$

Let me denote $W_{v_i}$ as $W_i$ from here. Remember that our equation of line is $y=kx+b$. Now, we will split terms as-

$\large =\underbrace {\underbrace {c} _ {k}*\underbrace{ \sum_{i=c}^{i=k}W_{v_i} } _ {x}+\underbrace{\sum_{i=c,j=1}^{i=k,j=(k-c)}j*W_{v_i}} _ {b}} _ {Line}+\underbrace{\sum_{i=1}^{i=c} i*W_{v_i}} _ {Calculated \space using \space DFS}$

In simpler terms, the line's equation will look like-

$y=kx+b=c*(W_1+W_2+W_3....)+((k-c)*W_1+(k-c-1)*W_2.....)$

This is nothing but the latter half of the path. Now, what we can do is, for each of the $NlogN$ paths TOWARDS the centroid, we query for the line which gives maximum value for the bottom part.

We will have to deal with cases where path begins from root/centroid separately.

Now, what remains is, to solve the problem of "Given a set of lines, which line will give maximum value for a given $x$"

A good time to pause. Can you look at setter's code, and look at functions $dfs1$ and $dfs2$ and deduce his transformation? Is it exactly same as I described or is it a little different?

Now, transformation done, we are yet to solve this reduced problem.What geometrical data structure can you think of, which can support insertion of new lines, removal of unwanted lines, and querying for line with highest value of $y$ (for a given $x$) in atmost $logN$ time?

The setter used a (upper) convex hull. Can you think a moment for the proof of correctness of choosing this structure? Answer will be in Chef Vijju's corner. :). However, to help you, I have an image to give (only hints, not full answer) :)

The image below will also describe the steps setter used to max the hull. It goes without saying that, any unwanted or useless lines are removed from the set. You can refer to setter's code $Line$ $37-53$

alt text

The image in fourth quadrant is a open question to you guys. Check out setter's code and see if it allows that or not :)

It is very important to maintain useful lines and eliminating the useless ones from set (for memory and time efficiency).

Once the hull is made and maintained, querying is very simple. A simple use of lower_bound() function will help you get the line giving maximum $y$ at $x$ as we have assigned the lines a variable pos which means "This line gives greatest $y$ till $x=pos$"

And with that, we are done with the hardest problem of the lunchtime!

SOLUTIONS

For immediate availability of setter and tester's solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them.

Setter

View Content

Tester

View Content

Editorialist's Solution will be put up on demand, as setter's code is sufficiently clean and commented enough to be understood.

$Time$ $Complexity-$ Setter's solution runs in $O(N{Log}^{2}N)$

CHEF VIJJU'S CORNER

1. Regarding the validity of hull

View Content

2. I used "Convex hull" at some point of editorial. Am I correct in saying so? Look at quadrant 4 of image of hull and think a little :)

3. Misc. fact.

View Content

4. BEWARE!! There is a difference between set data structure's lower_bound and typical lower_bound function. Read it here

5. Tester's Notes-

View Content

6. Intended approaches for various subtask, other than the final one-

View Content

7. Some problems to practice Centroid Decomposition-

This question is marked "community wiki".

asked 25 May '18, 17:57

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 12 Jun '18, 17:55

admin's gravatar image

0★admin ♦♦
19.8k350498541


We can avoid centroid decomposition and use dsu on trees.Here is link to my solution

link

answered 27 May '18, 02:57

teja349's gravatar image

6★teja349
656
accept rate: 14%

Thanks for the alternate.

(27 May '18, 15:10) vijju123 ♦♦5★

Can you please see my solution and tell me why it is giving tle for subtask 1 and 2. I have implemented convex hull trick without centroid decomposition.

https://www.codechef.com/viewsolution/18668769

link

answered 26 May '18, 23:48

yash_chandnani's gravatar image

7★yash_chandnani
112
accept rate: 0%

edited 26 May '18, 23:49

I loved your code. I think it should have passed subtask 2 at least. I will confirm my sub-task notes with setter once to see if he meant "both sub-task1 and 2" or only subtask 2. But yes, before that, is this the most optimized version you have? Try optimizing it a bit more if not. I feel the time taken for sub-task 2 last case should be close.

(27 May '18, 00:07) vijju123 ♦♦5★

For subtask 1, shouldn't the Complexity be nlog^2n as each nodes has logn parents at worst so each line is added to at max logn hulls?

(27 May '18, 00:50) yash_chandnani7★
toggle preview
Preview

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:

×15,852
×1,359
×647
×192
×153
×116
×63

question asked: 25 May '18, 17:57

question was seen: 636 times

last updated: 12 Jun '18, 17:55