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

×

RAJAPR0 - Editorial

Contest: ICO 2018 Practice Contest 1
Practice: Practice Link
Author: Shashwat Goel
Tester: Udit Sanghi
Editorialist: Shashwat Goel

Problem Statement

Given a graph with $N$ vertices and $N-1$ edges and $Q$ queries, you have to find the parity of path length from a node $A$ to node $B$ for each query.

Explanation

Theorem: Any connected graph with $N$ vertices and $N−1$ edges is a tree. Proof Let $G$ be a connected graph with $N$ vertices and $N − 1$ edges. We show that $G$ contains no cycles. Assume to the contrary that $G$ contains cycles. Remove an edge from a cycle so that the resulting graph is again connected. Continue this process of removing one edge from one cycle at a time till the resulting graph $H$ is a tree. As $H$ has $N$ vertices, so number of edges in $H$ is $N−1$. Now, the number of edges in $G$ is greater than the number of edges in $H$. So $N−1 > N−1$, which is not possible. Hence, $G$ has no cycles and therefore is a tree.
Therefore the given graph is a tree (note that the above proof is a basic property of a tree and questions like these assume you know this).

Now, since it's a tree, the shortest path between 2 nodes can be calculated by dfs/bfs. This gives you an $O(NQ)$ solution, which solves the first subtask.

Now moving for the second subtask, one must notice that the distance between 2 nodes of a tree is given by
(FORMULA 1): $$\text{Depth of starting node} + \text{Depth of Final node} - 2 \times \text{Depth of Lowest Common Ancestor}$$ This is evident if you draw some trees. The depth is the distance of a node from the root.

In this question, we can fix any node as the root (because the tree is bidirectional, if you change the root the orientation of the tree changes but everything else remains the same). So we fix a root and pre compute the LCA of all pairs of vertices (in $O(N)$ or $O(LogN)$). Then we can answer the Queries in $O(1)$ by checking the parity of Formula 1. This solution takes $O(N^2)$ time for precomputation and $O(1)$ for the queries. It therefore works on Subtask 2. This however doesnt work for subtask 1.Now notice that subtask 1 and 2 are exclusive, one has a low number of nodes and high number of queries while the other has a high number of nodes and low number of queries. So we use them exclusively in our code, that is check if $N>10^3$, then do the first method otherwise second.

Now, there is an algorithm for computing the LCA: Link

Now if you can code the $O(LogN)$ computation in the above link, You can simply find the LCA for every query without having to precompute anything. This solution works for all of the above, subtask 1 2 and 3. But here is the fun part. The actual solution is much easier, and does not require computation of the LCA in this particular problem. There is just one clever observation: Notice formula 1 again. $$\text{Length of Path}=D[U]+D[V]-2*D[LCA]$$ Notice that $2*D[LCA]$ is always even. Also notice that when an even number is subtracted/added from a number, it does not change the numbers parity, i.e. Odd+-Even = Odd and Even+- Even=Even. So we can eliminate this term. THUS, the answer is independent of the LCA and WE DO NOT NEED TO COMPUTE IT! You simply find the parity of $D[U] + D[V]$ and you're done!

So conclusion: The final algorithm requires a single DFS precomputation to compute the depth of each node. Then taken the queries and just check if $D[U]+D[V]$ is odd or even and output it.

Tester Solution: here

asked 13 Oct '17, 23:20

ista2000's gravatar image

4★ista2000 ♦
2.4k621
accept rate: 20%

edited 14 Oct '17, 17:00

vijju123's gravatar image

5★vijju123 ♦
14.9k11856

@ista2000 , please wikify it yourself. Server glitches are a pain -_-

(13 Oct '17, 23:53) vijju123 ♦5★

@vijju123 Sorry I forgot :P I wikified all others.

(14 Oct '17, 08:32) ista2000 ♦4★

I wikified it twice ;_; Doesn't work

(14 Oct '17, 08:32) ista2000 ♦4★
1

Even @admin faced the problem I guess. If she couldn't do it, who are we :3

(14 Oct '17, 10:30) vijju123 ♦5★

I did it in easier way.dfs of node.colored by 0 and 1.if xor value of two node is 1 then odd otherwise even (By observation).My code got AC.tell me if i'm wrong!! @ista @mathecodician

solution

link

answered 14 Oct '17, 00:35

doramon's gravatar image

1★doramon
865
accept rate: 5%

edited 14 Oct '17, 00:37

You did the same thing. We are storing the distances and finding the parity of their sum, you are storing parity and xoring; both are equivalent. Also, Both solutions are one pass dfs preprocessing.

(14 Oct '17, 08:31) ista2000 ♦4★

where is practice section link????????//

link

answered 14 Oct '17, 15:36

amit88265's gravatar image

2★amit88265
121
accept rate: 0%

https://www.codechef.com/problems/RAJAPR0

You just go to the contest link, then to the problem page and remove the contest code from the URL. :/

(14 Oct '17, 15:45) ista2000 ♦4★

He meant "if contest link is given, then why not practice link which is more relevant"

(14 Oct '17, 15:47) vijju123 ♦5★

Because when I posted the editorial, that time the practice link was not live :3

(14 Oct '17, 16:05) ista2000 ♦4★

Can't we find the depth of each node by one bfs precomputation instead of dfs ?

link

answered 26 Oct '17, 11:53

rajdeep2001's gravatar image

4★rajdeep2001
-2
accept rate: 0%

we can do the same, bfs or dfs doesnt matters much here, both works fine!

(09 Nov, 00:15) jvjplus3★
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,130

question asked: 13 Oct '17, 23:20

question was seen: 551 times

last updated: 09 Nov, 00:15