Hoa_Dau_Biec's blog

By Hoa_Dau_Biec, history, 4 weeks ago, In English

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

If you feel interesting about this topic, welcome!

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.

Add operation :

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)

Read more »

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

By Hoa_Dau_Biec, history, 3 months ago, In English

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).

Read more »

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

By Hoa_Dau_Biec, history, 4 months ago, In English

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_

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By Hoa_Dau_Biec, history, 5 months ago, In English

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!

Read more »

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

By Hoa_Dau_Biec, history, 6 months ago, In English

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)

Read more »

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

By Hoa_Dau_Biec, history, 7 months ago, In English

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

Read more »

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

By Hoa_Dau_Biec, history, 10 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By Hoa_Dau_Biec, history, 11 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it