### Hoa_Dau_Biec's blog

By Hoa_Dau_Biec, history, 4 weeks ago,

Hi codeforces! I was trying to learn about Li-Chao tree by some blog which i can find on gg (codeforces included). But there still some issue i was encountered while I trying to understood Li-Chao tree. Fortunately! I found that there's a simpler way to understand LC tree by thinking about another approach. So, I decide to write this blog for two reason :

• Archive

• Sharing

# Prerequisite :

Did you read one of two blog ? :

### I.Which issue that me (or maybe someone) stuck in Li-Chao tree?

These question are main motivation :

• Why node on $Li-Chao$ $tree$ only store one line that is $min/max$ at point $mid$ which $mid$ is the middle point in segment $[L, R]$ which current node manage?
• Why in $Query$ function we get $max$ result on way from root to leaf instead of get a value in node which include point we want to query?

I guess that somebody maybe stuck in here, so, we will answer it later.

### II.Problemstatement

You must give a data structure which can do two following operation by the best way you can :

• Add a line $y = a*x + b$ into set $S$

• Given an integer point $x$, find $min$ value of $y$ among all line we added

Similar to $Li-Chao$ $tree$, we manage convex hull by the way maintain a segment $[L, R]$, for each intergers $x$ in $[L, R]$ we store line $y = a*x + b$ such that the line $y = a*x + b$ reach min at point with coordinate $x$ among all of line.

We can reach two observation :

• Add two line $x = -\infty$ and $x = +\infty$ into $S$. Easy to see that the convex hull look like a parabol with nagative slope. $(*)$

• If a line lie on convex hull, it will lie on a continuous interval on convex hull. $(**)$

Thicker line represent the convex hull

We can iterate over $[L, R]$ whenever we add a new line into $S$ to update the "min line" for each point in $[L, R]$

However, by two observation above, we can do ternary search to find point $x$ such that:

• $x$ $\in$ $[L, R]$

• At $x$ coordinate, the current line $y = a*x + b$ is the "min line".

Because $(**)$ then we also need a segment tree to range update (lazy propagation is recommend). Add operation is done!

Query operation : We only need get result on segment tree by go to leaf which represent point $x$. So easy, right?

### III.Basic Li-Chao tree

I will explain following code in this blog : https://codeforces.com/blog/entry/86731 (code is in Prerequistes section)

Add operation : Instead of ternary serach and range update, we will search point with x-coordinate which at $x$, line $y = a*x + b$ lie on convexhull, we can "walk on segment tree" to find such $x$.

Back to the first question in I section. By storing in such way, we can get some observation :

• If a line lie on a contiguous interval on convex hull, it will be stored in some node on $Li-Chao$ $tree$. $(***)$

• If a line $y = a*x + b$ reach min in range $[L, R]$ among all line we added, then any path from root to every leaf $x$ $\in$ $[L, R]$ on $Li-Chao$ $tree$ $(****)$ will pass over at least one times the line $y = a*x + b$.

Query operation : by $(****)$, we get min value of $y = a*x + b$ on path from root to leaf, we will get the min result we want. Which answer the second question in I section. All done!

### IV.Epilogue

That's all thing I can think about $Li-Chao$ $tree$, so this is my first time to write something i have learn on codeforces, hope that my blog will not get nagative rate. Thanks for reading! (And sorry because my English)

• +87

By Hoa_Dau_Biec, history, 3 months ago,

Hi codeforces

In some recently contest. I have found many problem with "constructive" tag. In this such problem, we solve it by the way like : "If you construct a algorithm like ... you will reach the result. We can prove that ..." Example : E and C in Global round 15 : https://codeforces.com/contest/1552/problem/E https://codeforces.com/contest/1552/problem/C

Some time I feel it's too difficult to solve constructive problem. So I want to ask you how did you figure out a solution for such that problem ?

btw// I have learnt cp for 3 years, yah, not practive so much on codeforces but many on another platform. Recently, I dicide to practice on cf more to reach at least CM on it. But, I feel it still impossible for me. But I will never give up (booyah!). Uhm, if you have any experience, pls share to me, I will damn grateful for that

Thanks for reading! (and sorry because my English).

• +15

By Hoa_Dau_Biec, history, 4 months ago,

Given N node (numbered 1 to N, It should be noted that the nodes are different from another) (N <= 300) Count the number of graph (which only contain 1 connected component) construct by N node and each node doesn't have > 2 edge

Thanks to anyone for give any idea!

_Sorry because my English_

• -1

By Hoa_Dau_Biec, history, 5 months ago,

Satement :

Give n (one dimension) array, array i have a[i] cell. n <= 1000, a[i] <= 1e6 There are two player X and Y. Player will X write number 1 down to a blank cell while player Y write number 2. A valid move is a move such that there is no adjacent cell which have same number. We know that X will have first move. Who will win ?

I can see that, the set of valid move of X difference with set of valid move of Y. And that mean it is not a impartial game. But because the statement said that it has n array, I feel we can change something in the statement to turn it into impartial game. Please help me, thank you a ton!

• +1

By Hoa_Dau_Biec, history, 6 months ago,

Hi, guy!

There is a problem which has statement :

Given n people and m job, c[i][j] represent the cost if people i match with job j. Find a max matching with minimum cost.

This problem can be solve with Hungary algorithm for max matching and minimum cost in bipartite graph. But some time, I see some problem which similar the statement below :

Given n people, c[i][j] represent the cost if people i match with people j. Find a matching and with maximum cost.

The bipartite property is not hold in this problem, but I think there's some way to modify it to bipartite graph and solve it by Hungary algorithm, but this problem also has tag "maxflow". So, I wonder how to solve this with maxflow-mincost algorithm because it must be hold that if the people i match with people j, then people i and j mustn't match with any another people.

(Sorry because my English)

• +8

By Hoa_Dau_Biec, history, 7 months ago,

Hi guy, I have been doing this problem : https://cses.fi/problemset/task/2073/

Given a string and m query which request reverse a substring. Print the final string

I solve it by Treap but I got Undefine Behavior (I run my code on my laptop and got correct answer, but on CSES is not). I was trying to fix it for six hour's but it's not better. Please tell me what was wrong in my code, thank you a ton!

Here is my code : https://cses.fi/paste/695ccf4c2fc0a9521c5235/

Update : I found some hint to continue debugging, i will comeback to fixed this blog if after I solve it

• +4

By Hoa_Dau_Biec, history, 10 months ago,

Hi guy, I was trying to solve a problem (link : http://www.usaco.org/index.php?page=viewproblem2&cpid=193〈=en)

It's a dynamic programming problem and the most difficult to solve is optimize the state of dp function.

Nearly, I found a cool solution (it's the second code in this solution : http://www.usaco.org/current/data/sol_bbreeds.html)

I don't understand how does it's work. Can you tell me the idea behind that?

Thanks you very much!

• -1

By Hoa_Dau_Biec, history, 11 months ago,

Hi guy, i am stucking in this problem : https://cses.fi/problemset/task/1735/

Here is my code : https://cses.fi/paste/567abb6bc35edc71146fae/

I have no idea why i got WA. Can anybody explain for me what was wrong in my concept ?

(Sorry because my English:"((( )

UPD : I got AC, my code has a big mistake follow smax said below.