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

×

ABX03 - EDITORIAL

3
1

PROBLEM LINK:

Practice
Contest

Setter : Mohammad Salik
Tester : Hasan Jaddouh
Editorialist : Mohammad Salik

Difficulty

Medium-Hard

Prerequisites

Square root decomposition on trees, DFS, LCA(Lowest Common Ancestor ), Inclusion-Exclusion, Binary Search

Problem

Given a tree with $N$ nodes and each edge having a cost and $Q$ queries on it.All the queries are to be answered online. Query is described by eight integers $U,V,X_{1},Y_{1},X_{2},Y_{2},X_{3},Y_{3}$. The answer to each query is the sum of all such costs $C$ which are encountered in the unique path from $U$ to $V$ and which satisfy the following conditions :

  • If C is a multiple of 2, C must be between X1 and Y1 inclusive.
  • If C is a multiple of 3, C must be between X2 and Y2 inclusive.
  • If C is a multiple of 5, C must be between X3 and Y3 inclusive.
  • C must be a multiple of 2, 3 or 5.

Explanation

Let us root the tree at $1$. Throughout the editorial we will assume the tree to be rooted at $1$.

For Subtask 1

The constraints for this subtask are low enough for brute force to pass. One can simply trace the path from $U$ to $V$ and decide for each cost whether to include it or not based on the four given conditions. This solution works in $O(Q*N)$ i.e $O(N)$ time for each query.

For Subtask 2

Lets make some crucial observations which will help us in solving the problem :

  • There are no updates i.e the edge weights are constant throughout all the queries.
  • The path between $U$ and $V$ in a tree can be broken down into two paths i. the path from $U$ to $LCA(U,V)$ and from $LCA(U,V)$ to $V$. You can read more about $LCA$ and its fast computation methods from here.
  • Let $answer(X)$ denote the answer when we move from node $X$ to $root$ for any particular query. Let $L=LCA(U,V)$ for any given query with $U$ as start point and $V$ as end point. If we find the answer for each of the three nodes $U,V$ and $L$ till the root then the answer for the current query will be simply $answer(U)+answer(V)- 2*answer(L)$.It is because when we move from $U$ to $root$ we encounter the path $L$ to $root$.And when we move from $V$ to $root$ we again encounter the path $L$ to $root$. Hence the path $L$ to $root$ is added twice.This needs to be subtracted which is simply $2*answer(L)$
  • So now the problem is to find for each query $answer(U)$,$answer(V)$ and $answer(L)$
  • How to Compute answer(X) for a node X for any current query with the parameters $X_{1},Y_{1},X_{2},Y_{2},X_{3},Y_{3}$ ?

    We will have to first do some precomputation i.e before any queries. Let us first define $blocksize$.Just for now assume $blocksize=500$. Let us now find all the nodes $i$ for which $depth[i]\%blocksize==R$ (Assume $R=1$ just for now for the sake of simplicity) where $depth[i]$ is the distance of the node from the root.Let us call all such nodes special nodes i.e for which the condition $depth[i]\%blocksize==1$ is true.For all such nodes maintain $7$ vectors.Let $V[i][x]$ denote the vector for special node $i$ such that it stores all the multiples of $x$ along the path from that node to the root.vectors will store the costs for $7$ values of $x$ i.e $2,3,5,6(2*3),10(2*5),15(3*5),30(2*3*5)$. Now we will sort all these vectors for all the special nodes and for all the seven values for these special nodes.We will maintain a prefix sum array $pre[i][x]$ also to get the prefix sum for any of the 7 multiples of any special node. $pre[i][x][k] (k < pre[i][x].size())$

    Now suppose we wish to find $answer(X)$ for any query.Let $Res$ denote the final answer.$Res=0$ initially.Now two cases arise :

  • $X$ is a special node
  • $X$ is not a special node : In this case we can trace the path from this node towards the root while adding the answer to $Res$ by applying the conditions mentioned until we encounter a special node or the root itself.Note that this will take less than $blocksize$ steps.
  • Now once we reach a special node $P$ we have to find the answer from this node to root and add it to $Res$.Now we have to find the $answer(P)$ for special node $P$. Here comes the inclusion-exclusion.

    $answer(P)$= Sum of multiples of 2 in range $X_{1}$ to $Y_{1}$ in $V[P][2]$ + Sum of multiples of 3 in range $X_{2}$ to $Y_{2}$ in $V[P][3]$ + Sum of multiples of 5 in range $X_{3}$ to $Y_{3}$ in $V[P][5]$ - sum of multiples of 6 in union of ranges $[X_{1},Y_{1}]$ & $[X_{2},Y_{2}]$ in $V[P][6]$- sum of multiples of 10 in union of ranges $[X_{1},Y_{1}]$ & $[X_{3},Y_{3}]$ in $V[P][10]$ - sum of multiples of 15 in union of ranges $[X_{2},Y_{2}]$ & $[X_{3},Y_{3}]$ in $V[P][15]$ + sum of multiples of 30 in union of all the 3 ranges in $V[P][30]$.

    Now sum of multiples of 2 in range $X_{1}$ to $Y_{1}$ in $ V[P][2] $ can be calculated by using binary search on the $V[P][2]$ vector and by using the prefix sum vector $pre[P][2]$ to calculate the sum.Similarly all the other values can be calculated using binary search. So the query takes approx $O(blocksize)$ time.

    In the above appropriate value of blocksize can be set to $blocksize= sqrtN$. Also above $R$ was taken to be $1$ for the condition of special node. In fact this value should be calculated by running an initial dfs and finding the frequency of $depth[i]\%blocksize$ for all $i$ and hence calculating an appropriate $R$ such that number of nodes satisfying $depth[i]\%blocksize==R$ is as minimum as possible. This is done to minimize the number of special nodes and save both memory and time.

    Time Complexity

    $O(Q*sqrtN)$

    AUTHOR'S AND TESTER'S SOLUTIONS:

    Author's solution can be found here.
    Tester's solution can be found here.

    This question is marked "community wiki".

    asked 30 Dec '17, 21:53

    abx_2109's gravatar image

    4★abx_2109
    275111
    accept rate: 0%

    edited 31 Dec '17, 00:02

    meooow's gravatar image

    6★meooow ♦
    7.3k720

    Please improve formatting of expression. It's not readable.

    PS: Nice problem

    (30 Dec '17, 23:20) taran_14076★

    @taran_1407 Hey,It seems fine to me. Can you tell which line is unclear?

    (31 Dec '17, 00:25) abx_21094★

    @abx_2109 I just fixed it :P
    Probably should have added a comment.

    (31 Dec '17, 00:29) meooow ♦6★

    Thanks @meooow . Also,Is there a problem with latex formatting, because in the preview it shows differently.

    (31 Dec '17, 00:30) abx_21094★

    Yes it happens sometimes that the preview comes up as intended but the main article appears messy. Putting extra spaces helps sometimes and at other times usually it is caused by something like array[1] to be linked to the hyperlink labeled [1].

    (31 Dec '17, 00:33) meooow ♦6★

    Well, It's readable now @abx2109, Because @meooow fixed it.

    By the way, can this problem be solved using Heavy Light Decomposition??

    (31 Dec '17, 00:37) taran_14076★

    Yes, one of the participant solved it using HLD.Check this out - https://www.codechef.com/viewsolution/16712166

    (31 Dec '17, 00:46) abx_21094★
    showing 5 of 7 show all

    PS : Probably most of the contestants solved this problem using persistent segment trees which I hadn't anticipated at all. To avoid getting solutions by segment trees accepted we decided to force online queries.But unfortunately most of the contestants did this problem by handling queries using persistence :p. I think there is probably no solution by the method mentioned in the editorial above.

    link

    answered 31 Dec '17, 00:34

    abx_2109's gravatar image

    4★abx_2109
    275111
    accept rate: 0%

    Too many solutions for single problem: Segment Tree, HLD, editorial one.

    (31 Dec '17, 00:53) taran_14076★

    Any idea, why https://www.codechef.com/viewsolution/16719850 this didn't pass even the first subtask?

    link

    answered 31 Dec '17, 00:27

    mathecodician's gravatar image

    6★mathecodician
    2.6k11034
    accept rate: 7%

    Not sure if this is the reason, but I see you're not clearing path before every query.

    (31 Dec '17, 00:34) meooow ♦6★

    oh my god fml

    (31 Dec '17, 00:46) mathecodician6★

    Haha, I feel you :P I made an equally retarded mistake on the 3rd problem

    (31 Dec '17, 00:48) meooow ♦6★

    got AC on the first subtask atleast :p

    (31 Dec '17, 00:48) mathecodician6★

    Oh by god!!!

    I too feel you. I did something similar on cf yesterday.

    (31 Dec '17, 00:51) taran_14076★

    How do we solve it using hld?

    link

    answered 31 Dec '17, 01:25

    vivek_1998299's gravatar image

    6★vivek_1998299
    1.6k29
    accept rate: 23%

    Need help with my RE (here).

    link

    answered 31 Dec '17, 10:42

    scaly_raptor's gravatar image

    3★scaly_raptor
    11
    accept rate: 0%

    Somebody please help.

    (03 Jan '18, 15:27) scaly_raptor3★
    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,302
    ×1,056
    ×733
    ×258
    ×140
    ×57
    ×14

    question asked: 30 Dec '17, 21:53

    question was seen: 1,873 times

    last updated: 03 Jan '18, 15:27