lukameladze1's blog

By lukameladze1, 5 months ago, In English

Intro

Hello, Codeforces Community!
The main concept of this blog is the Edge Divide and Conquer method, but there are other techniques that I mentioned and used to solve the example problem below.

  • Target audience: CF Rating $$$\geq 2000$$$.

  • Note: Please, feel free to suggest more problems that can be solved using any of the techniques mentioned in the blog in the comments section. You can see an easier version of my modified problem on Luogu, which can also be solved with the standard centroid decomposition method.

Prerequisites:

  • Basic tree algorithms: LCA, DFS, etc.
  • Divide and Conquer (Centroid Decomposition) on trees. If you do not know the algorithm, you can learn it here: Hybrid Tutorial

Abridged problem statement:

You're given two rooted trees($$$\text{T1}$$$ and $$$\text{T2}$$$). Each of them is rooted at vertex $$$1$$$ and has $$$n$$$ vertices and $$$n - 1$$$ weighted edges. The strange distance between two vertices is defined as: $$$val(x, y) = \text{depth1}[x] + \text{depth1}[y] - \text{depth1}[\text{lca1}(x, y)] - \text{depth2}[\text{lca2}(x, y)]$$$. You have to print two integers: the maximum value $$$\text{mx}$$$ of strange distance among all possible pairs $$$1 \leq x<y \leq n$$$ and the number of such pairs that $$$\text{val}(x, y) = mx$$$
Constraints: $$$n \leq 3 \times 10^5$$$, edges can have negative weights.

Sample input
Output
Sample explanation

Solution description:

Step 1: The equation includes four variables, two of which are dependent on $$$\text{lca1(x,y)}$$$ and $$$\text{lca2(x,y)}$$$. The depths of $$$\text{LCAs}$$$ in both trees are not easy to deal with, so by multiplying and dividing every term from the first tree by 2, we can observe the following relationship: $$$\text{depth1}[x] + \text{depth1}[y] - \text{depth1}[\text{lca1}(x, y)] = \frac{1}{2} \cdot (\text{distance1}(x, y) + \text{depth1}[x] + \text{depth1}[y])$$$, thus, from now on, $$$\text{val}(x, y) = \frac{1}{2} \cdot (\text{distance1}(x, y) + \text{depth1}[x] + \text{depth1}[y]) - \text{depth2}[\text{lca2}(x, y)]$$$

Step 2: Failing to solve the problem using the standard centroid decomposition method:
Centroid decomposition is a common approach for problems where paths between all pairs of nodes should be considered. Thus, We could first try to solve this problem with a standard centroid decomposition method, but soon, we will notice that in this way, we have some issues that can be overcome only after using another nice and less-known technique. Using the standard centroid decomposition method, we choose the centroid in the first tree, consider all the paths that go through this node, remove it, and solve the problem for the remaining subtrees recursively. Removing the centroid divides our tree into subtrees with at most half of the current size; thus, until the end of the process, each node will be considered at most $$$\log_{2}n$$$ times. However, when we consider the centroid, the tree may be divided into many subtrees(for simplicity, let's color different subtrees with different colors), and splitting a tree into many colors is an issue in this problem.

$$$\text{val}(x, y) = \frac{1}{2} \cdot (\text{distance1}(x, y) + \text{depth1}[x] + \text{depth1}[y]) - \text{depth2}[\text{lca2}(x, y)]$$$
Specifically, for each centroid vertex $$$\text{C}$$$, we need to iterate over all $$$lca2(x,y)$$$ in the second tree in order to fix this equation's fourth addend. We have two restrictions:
1. At this step, we only consider the vertices $$$x$$$ and $$$y$$$ whose connecting path goes through the vertex $$$C$$$. Thus, $$$x$$$ and $$$y$$$ must have different colors.
2. When we iterate over all $$$\text{lca2(x,y)}$$$ in the second tree, we need to distinguish the colors of vertices. If the problem asked us to find just the maximum $$$\text{val(x, y)}$$$, then for each vertex in the second tree, we could keep only the two best vertices with different colors that have maximum $$$\text{Distance}(C, x) + \text{depth1}[x] + \text{depth2}[x]$$$, but our problem is a bit harder, and you can't simply find the #number of pairs with maximum $$$\text{val}(x, y)$$$ if there are many colors because, for each vertex in the second tree, we need to maintain some information about each color. This will lead to $$$O(n \cdot \text{number of colors})$$$ time complexity, which can be $$$O(n^2)$$$. So what we would like to do is to reduce the number of colors to 2!

Step 3: We can overcome the issue of having many colors by a technique called 'Edge centroid decomposition' or 'Edge divide & conquer.' Instead of dividing the current tree into many 'small enough' parts when deleting a centroid vertex, we want to divide it into exactly two subtrees by deleting an edge, where both parts have roughly equal numbers of vertices. But there is a question: Does a 'good' centroid edge always exist? The answer is no.
Let’s consider the 'Star' tree: If we delete any edge from the tree, we will get two subtrees of sizes $$$\text{1}$$$ and $$$\text{(n–1)}$$$. Then, two subtrees with sizes $$$\text{1}$$$ and $$$\text{(n-2)}$$$ and so on. Thus, in total, we will consider vertices $$$\sim O(n^2)$$$ times, which is too much.

Binarizing the tree:

After figuring out this issue, we are trying to somehow convert the first tree, $$$\text{T1}$$$, into an equivalent tree in a way that there always exists an edge that, when removed, divides our tree into two small enough parts.
For a binary tree, we can always guarantee the existence of such an edge(the one that goes from the centroid vertex to its biggest subtree) that, when removing it, the bigger subtree has at most $$$\frac{2}{3} \cdot \text{CurSize}$$$ vertices. So if we achieve transforming $$$\text{T1}$$$ to the binary tree while preserving the distance between any two original vertices, we will consider each vertex at most $$$\log_{1.5} n$$$ times.
Step 4: We can transform any tree $$$\text{T1}$$$ into a binary tree without changing its structure in this way: (you can also read the editorial of 757G)

  • To convert the given tree T into an equivalent binary tree (degree of each node is $$$\leq3$$$), we will add at most $$$O(n)$$$ dummy nodes.

  • The dummy nodes are added in such a way that the structure of the tree and the distances between any two initial vertices are preserved.

  • To do this, consider a node $$$\text{X}$$$ with degree $$$D > 3$$$. Let $$$C_{1}, C_{2}, C_{3}, \ldots, C_{d}$$$ be its adjacent nodes. Add $$$\text{D}$$$ complementary new dummy nodes, and change the edges as in the image below. (Note that the sum of degrees of vertices whose degree $$$D>3$$$ reduces on each addition of the dummy node. Thus, we need at most $$$\sim O(n)$$$ dummy nodes).

Step 5: When we find the Centroid Edge, $$$\text{E}$$$, our current tree is divided into two parts(white and red), and at this stage, we consider paths between such vertices $$$x$$$ and $$$y$$$ that their connecting path goes through this centroid edge(the vertices $$$x$$$ and $$$y$$$ have different colors). The distance between $$$x$$$ and $$$y$$$, $$$distance1(x,y)$$$, can be split into two independent routes. We can denote $$$\text{Whitevalue}(x) = distance1(x, a) + depth1[x]$$$ for each white node and $$$\text{Redvalue}(y) = distance1(y, b) + depth1[b]$$$ for each red node. Then, when we iterate through all possible $$$\text{LCAs}$$$ in the second tree, and for every node, we need to store the value and number of best white nodes(nodes with maximum $$$\text{Whitevalue}(x)$$$) in its subtree and the value and the number of best red nodes in its subtree. These values can be calculated in $$$O(n)$$$ time by very simple dynamic programming in the second tree. However, when we consider a centroid edge E for the current subtree, no matter if, at this stage, our subtree is little or we are in the initial stage, we consume $$$O(n)$$$ operations for DP in the second tree. Consuming $$$O(n)$$$ time for each centroid edge's subtree will lead to $$$O(n^2)$$$ time complexity.

We don’t actually need to iterate through all vertices in the second tree and consider all of them as $$$\text{LCAs}$$$. To achieve $$$O(\text{CurrentSubtreeSize})$$$ time complexity for the centroid edge’s subtree, we can compress the second tree (i.e., Build Virtual / Auxiliary tree), and considering only the vertices of the Auxiliary tree will be enough.

Virtual/Auxiliary tree:

For a dive into the details of this algorithm, you can read this1 this2.
When we consider a centroid edge of a particular subtree, instead of iterating over all $$$\text{LCAs}$$$ in the second tree, we only matter the 'Key' nodes -- nodes that are in the current subtree and their pairwise $$$\text{LCAs}$$$. The virtual tree is a tree that includes only key nodes but still maintains the original tree's structure and ancestor-descendant relationships. Specifically, we only matter vertices in the current subtree and their pairwise lowest common ancestors. We can find all these pairwise lowest common ancestors by maintaining the sorted list of the vertices according to their DFS traversal order and finding LCA in $$$O(1)$$$ for each pair of adjacent vertices. Thus, we can efficiently build a virtual tree for each centroid’s component.

The overall time complexity is $$$O(n \log_{1.5} n)$$$ because we can use the $$$O(1)$$$ LCA method and Merge Sort to maintain the sorted list of vertices according to their DFS order without adding an additional log factor. This complexity is sufficiently efficient!

Full text and comments »

  • Vote: I like it
  • +152
  • Vote: I do not like it

By lukameladze1, 5 months ago, In English

Introduction:

Hi, Codeforces Community!

Initially, I thought I could cover everything I wanted to share in a single blog post since I didn't expect the story would become this long. Now, I decided to split it into two parts.

  1. In this part, I’ll share my personal IOI journey & short-term goals(free tutoring) in the world of competitive programming
  2. The second part, which I’ll publish in a few weeks, will be more technical and educational: I'll delve into the resources I've used and my approach to practicing.

Personal story

First, let me briefly introduce myself. I am Luka Meladze, from Georgia. I've been practicing competitive programming intensively for the past 3-4 years. From today’s perspective, choosing CP as the very essence of my high-school life was the best decision I could have made. From the early days of my CP journey, my ultimate goal was to participate in IOI and earn a medal, in my opinion, the best programming competition.

In 2022, I placed 5th on TST and missed getting into a national team by one spot. I had two options: give up my dream and mainly focus on preparing for national exams or take a deep breath and go all-in on my passion. Thankfully, I chose the latter one.

What "going all-in" really meant for me: I can't say I followed a strict practice schedule; I almost never forced myself to set time constraints during training. But on average, I enjoyed practicing for 8-10 hours a day during the school term, increasing the duration as the qualifying round drew nearer.

On May 24, 2023, I performed pretty well in the team selection contest and placed 1st. It felt awesome, a mix of joy and responsibility solely to myself and my dreams: the whole, and only 3 months before IOI was ahead. From that moment, my summer routine started: I dedicated ~10 hours to practice each day, almost without fail—every day except for Sundays. Throughout my preparation and many OI problem-solving, I gradually gained self-confidence. So, my initial goal of earning a medal at IOI evolved into something more ambitious.

And so, I'm in Hungary, surrounded by an incredible community of programmers, enjoying every moment to the fullest. :) I kept repeating to myself the words: “No matter what the result is, I’ve gained a lot from these years, I’ve met a lot of amazing people, and even if I performed badly, I would not be too sad…”. But deep down, I knew that anything less than success would leave me disappointed!

Nothing special happened to me during day 1 of the competition; I just finished in the Silver medal zone.

And finally, the last day of my high school programming competitions came. I woke up at 6:30, stepped outside the hotel, listened to motivational songs, and read a conclusion part of Codeforces blog: “All seconds during competition have the same value, don't waste even a single second in the contest.“. After ~1 hour from the beginning of the competition, I mind-solved problem A (based on the scoreboard, the hardest one) for 70 points. Implemented and received the Wrong Answer verdict. Although I nearly never struggled with debugging my code during training, during the competition, I spent more than 2 hours trying to find what was wrong in the code of my obviously correct idea and seemingly correct code. I had two choices: spend time on problems B and C or persist in my endless debugging of problem A. I chose the latter, believing firmly that I could crack it and find the bug.

It was a few minutes before the end of the contest, but I still had a little hope because of the words I had in my mind from the blog I read in the morning: “The competition results won't be determined until the last minutes and even the last 0.1 second. The person who doesn't give up will win.” If this were a story from a happy-ended movie or a fairy tale, I'd have definitely solved the problem, but real life sometimes goes for the unexpected plot twist! The pressure did its job pretty well, and the contest ended, and I ended up with a bronze medal.

Although I was extremely disappointed that I didn't debug my code, with the help of having conversations with great people there, I managed to not worry about it a lot. As they said: “Even though getting bronze is already a notable achievement, the process of learning must be more important than getting good medals. It’s 100% okay to perform below your expectations. What matters is how you learned and grew out of it.”

I had a lot of fun and enjoyed spending several more days with the greatest people. These 7 days will definitely stay in my mind as both one of the bitterest and sweetest high school period memories. Indeed, it was much more than 7 days!

After returning to Georgia, I knew I couldn't change the past, but a curiosity about the bug in that IOI problem kept me wondering. I reached out to the organizers, and they sent me my incorrect source code. If I had made that little adjustment, swapping the positions of two miswritten variables, Sz and Cnt... I'd have been in the top 4 in this problem and would have gotten a silver medal. But I understand that it's part of the competition, and moreover, this is exactly why I love the Olympiad. I love IOI with everything, including the preparation process, pressure, unexpected scenarios during the development of the contest, etc. I do not regret any single second I've spent in this field since it gave me more than good medals and taught me more than just problem-solving — how to set and be passionately committed to my goals, be consistent, and aim higher all the time.

Free tutoring for 8-10 competitive programmers (preferably future IOI candidates)

Now, I have some free time since I’ve taken a gap year and am applying to U.S. universities. I'm taking a short break from my intensive preparation. I'm considering giving ICPC a shot when I enter university. First, I’m gonna use this break to explore and try some other things. But before making a decision about my future Olympiad CP career, I still want to do something connected to it and make a small contribution.

For me, it was hard to choose the problemset that I should follow. During my preparation, I made a lot of time-consuming mistakes because of my lack of experience. Moreover, I did not know about some useful materials and found out about them later. So, Having had experience in CP, I've decided that I could share my knowledge the best by tutoring several students (future IOI candidates) for free. I've already started teaching younger students at my programming school, but I'd like to train several international ones. I will choose them and form 2 groups based on their motivation and provide them with personalized instructions. Please contact me on discord: lukameladze#3563 and send me a short message: CF handle, background, and motivation. UPD: I don't accept additional requests, as I already received over 50 inquiries.

  • Last but not least, big thanks to everyone from whom I learned a lot! Thank you, dear CP community, for giving me motivation. Competing with you has always been my pleasure!

Full text and comments »

  • Vote: I like it
  • +281
  • Vote: I do not like it