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

×

COG1806 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Avinash Verma
Editorialist: Avinash Verma

DIFFICULTY:

MEDIUM

PREREQUISITES:

DFS, Euler Tour and Merge Sort Tree

PROBLEM:

Calculate the maximum length of the sequence in a tree such that every node is a child of previous node and sum of the capacity of nodes in the sequence should be less than S.

QUICK EXPLANATION:

First change the nodes value i.e $A[u]+=A[parent[u]]$ ,where $parent[u]$ is parent of u,then use concept of segment tree on rooted tree and merge sort tree to find the node in the subtree of X such that A[node] is less than or equal to $ S + A[parent[X]] $, then the path between X and node that you found.

EXPLANATION:

Convert every query for node X to query for whole tree. Apply DFS on the tree to calculate depth of each node in tree and calculate cumulative sum of every node from top to bottom i.e $ A[u] = A[u] + A[parent[u]] $. So, for each query of node X and S sum.

We add value of $A[parent[X]]$ to $S$, then we want to find a node d in subtree of node X such that $A[d]$ is less than or equal to S and depth of d is maximum. So, answer is length between node X to node d. Why?

To convert subtree query to range query. We will make a Euler tour of the tree. Then for each query, we have to find the node of maximum depth in range of particular subtree range, Such that sum of capacity of path from X to that particular node is less than S.

To find a node such that $A[node]$ in subtree of node X, is less than S and have maximum depth. We will create a merge sort tree of Euler path of tree store in pair value format i.e pair of $A[node]$ and $depth[node]$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Little Appreciation Keeps us Motivated.

This question is marked "community wiki".

asked 25 Nov '18, 18:21

avi892nash's gravatar image

5★avi892nash
823
accept rate: 20%

edited 27 Nov '18, 16:56

admin's gravatar image

0★admin ♦♦
19.7k350498541


I solved this problem without Segment tree. We can store the queries for each node, and solve this problem offline in a single dfs.
In dfs, for each node, maintain a map of each depth to its minimum cumulative sum possible in that level.
This is monotonically increasing over depth, so we binary search for the maximum depth with cumulative sum $\le$ query.
Complexity is $ O((N + Q) log_2(N))$.
My solution - 0.10s.

PS: In your solution, you store $pair(cumsum, depth)$ for each subtree. How can you binary search on the largest depth with $cumsum \le query$ with this information, since for same depth, there can be multiple sums associated? @avi892nash

link

answered 26 Nov '18, 14:35

rahul_g's gravatar image

5★rahul_g
1184
accept rate: 14%

edited 26 Nov '18, 15:10

I am storing pair(cumsum, depth) for every node in the tree. So, Let's consider we want to find a sequence with starting node 1 i.e. root, then we will find the maximum depth of any node such that cumsum ≤ query. This can be done in a loop. But if we sort the pair values then make a new array P of same length as of pair values such that P[i] is equal to maximum depth of all sorted pair values from 0 to i.

So, for any value of S in query. We have to find maximum index of sorted pair values such that cumsum ≤ query, then P[index] will gives us the maximum depth of a node having cumsum ≤ query.

You have to create P[] for all sub-range in merge sort tree.

link

answered 27 Nov '18, 03:16

avi892nash's gravatar image

5★avi892nash
823
accept rate: 20%

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:

×2,559
×18

question asked: 25 Nov '18, 18:21

question was seen: 167 times

last updated: 27 Nov '18, 16:56