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

×

SUBWAY - Editorial

PROBLEM LINK:

Div 1 Div 2 Practice

Author: Full name Tester: Full name Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Sparse tables, lca

PROBLEM:

You are given undirected graph with $N$ vertices and $M$ edges. If we ignore multiplicity of edges, graph will form a tree. Each edge has some color. You are given $Q$ pairs $(u,v)$. For each pair you should calculate cost of the longest path from $u$ to $v$ where cost is measured as amount of color changes along the path.

QUICK EXPLANATION:

Leave at most $3$ colors in each edge. After that use sparse tables like in lca to calculate cost of ascending path with fixed first and last edge. If you have these costs for ascending pathes $(u,w)$ and $(v,w)$, you can easily merge them into costs of path $(u,v)$.

EXPLANATION:

Let's choose vertex $1$ as the root of our tree and erase repeating colors on the same edge. Now we can assume that while answering each query we will first go from $u$ to $w=lca(u,v)$ and then to $v$.

We should note now that if any edge has multiplicity which exceeds $3$, we can assume that it's equal $3$ since that will be enough to choose color which won't be equal neither preceeding color nor succeeding one in the path, giving maximum possible contribution from this particular edge. Let's denote $d(u,v,l,r)$ as the maximum cost to go from $u$ to $v$ choosing first edge in the path to be of color $l$ and last edge in the path to be of color $r$. Here we actually should make $l$ and $r$ be from $1$ to $3$, i.e. we will use order of color among those possible on first and last edge.

Assume you know $d(u,w,l_1,r_1)$ and $d(w,v,l_2,r_2)=d(v,w,r_2,l_2)$ for every possible $l_1,r_1,l_2,r_2$. This will give you an opportunity to count maximum possible cost of path from $u$ to $v$: $$d(u,v) = \max\limits_{l_1,r_1,l_2,r_2}[d(u,w,l_1,r_1)+d(w,v,l_2,r_2)+(color_{r_1} \neq color_{l_2})]$$

Now we reduced the problem to calculating $d(u,w,l_1,r_1)$ and $d(v,w,r_2,l_2)$. Since $w$ is ancestor of poth $u$ and $v$, we can do it with sparse table (like the ones you use to find lca in the tree). You'll use quite same formulas as the one above for $d(u,v)$ but will have to make some wrapper so you can iterate through possible colors quickly. This can be done for several ways, for example, you can keep in each vertex array of posssible colors to get from this vertex to its ancestor and also to use some sparse tables to answer level ancestor queries to find vertex preceeding $v$ in ascending path from $u$ to $v$ so you can iterate through possible $r$ easily.

This is quite technical task, please refer to author's solution for implementation details.

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 20 Jul '18, 07:04

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 22 Jul '18, 17:19

admin's gravatar image

0★admin ♦♦
19.7k350498541

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,498
×1,237
×120

question asked: 20 Jul '18, 07:04

question was seen: 743 times

last updated: 22 Jul '18, 17:19