Link to problem.

Summary: Given $$$n$$$ segments, $$$i$$$-th segment is $$$(l_i,\ r_i)$$$. In one operation you can choose any $$$i$$$-th segment and increment or decrement both $$$l_i$$$ and $$$r_i$$$ by $$$1$$$. Find the minimum number of operations required to make each segment $$$i$$$ $$$(1 \lt i\leq n)$$$ intersect with segment $$$i - 1$$$.

I know how the dynamic programming works for this problem, and that it needs a slope-trick optimization, but I don't know how the two ideas work together (I have an AC submission but I don't actually understand how it works or the idea behind it). Please help me. Thanks for your attention — have a good day!

Today, I found a method to counting number of coprime pairs between two sets $$$A$$$ and $$$B$$$ as follows:

• Let $$$DA_x$$$ be the number of elements in set $$$A$$$ that are divisible by $$$x$$$ and $$$DB_x$$$ be the number of elements in set $$$B$$$ that are divisible by $$$x$$$.

• The number of pairs $$$a\in A$$$, $$$b\in B$$$ such that $$$gcd(a,\ b) = 1$$$ (i.e., $$$a$$$ and $$$b$$$ are coprime) is:

where $$$F_i$$$ is Mobius function in $$$i$$$.

Is this method correct ? Thanks for your attention, and have a good day (sorry for my bad English btw).

Edit: $$$U$$$ in $$$(^*)$$$ is the maximum value of all elements in $$$A$$$ and $$$B$$$.

Summary: Given an array $$$A$$$ with $$$N$$$ elements. Find the largest continous subbarray $$$(l,\ r)$$$ of $$$A$$$ that: $$$max(A_l,\ A_{l + 1},\ ...,\ A_r)\ \vdots\ min(A_l,\ A_{l + 1},\ ...,\ A_r)$$$. Print the value $$$r - l + 1$$$. constraints: $$$n\leq 6\times 10^5,\ a_i\leq 10^5$$$.

Subtasks:

• $$$n\leq 500$$$ and $$$n\leq 5000$$$: for $$$O(n^2)$$$.

• $$$a_1\leq a_2\leq ...\leq a_n$$$: for dp $$$O(n\ log\ n)$$$.

• $$$a_i\leq 1000$$$: dont know how to do.

• $$$n\leq 10^5$$$: dont know how to do.

• No additional constraints: dont know how to do.

Please help me with this problem, thanks for your help and attention. Have a good day !

Link to problem: https://mirror.codeforces.com/gym/103536/problem/B. (the statement is short so I won't write a summary)

My idea is to use a CHT with the recurrence:

(where the $$$a_i$$$ are sorted), but I dont know how to add a line to the CHT structure, is my approach possible, or is there a different way?

Thanks for your help and attention, have a good day !

Link to contest (statement in Vietnamese): https://lqdoj.edu.vn/contest/dhbb23, problem link: https://lqdoj.edu.vn/problem/dhbb23hkdata. (you must virtual join the contest before open the problem)

Summary: Given a array $$$a$$$ with $$$n$$$ elements, the cost of this array is the maximum value of $$$|\sum^{R}_{i = L}\ a_i|$$$ among all pairs $$$1\leq L\leq R\leq n$$$. There are $$$q$$$ $$$\bf {independent}$$$ updates of the form $$$l\ r\ c$$$: increase all elements from $$$l$$$ to $$$r$$$ by $$$c$$$, then calculate the cost of array after the update. $$$n,\ q\leq 10^5,\ |a_i|,\ |c|\leq 10^9$$$.

Thanks for your help and attention, have a good day.

Update: I just solved this problem using a CHT Segment Tree (code here: https://ideone.com/5BWLxX), thanks for all the help!

Statement: https://oj.uz/problem/view/JOI17_arranging_tickets

I dont know how "check function" for the binsearch work, in some solution, I saw that they use an $$$O(n\ log\ n)$$$ algorithm with heap but I'm not sure how it helps, can anyone help me with that.

Thanks for your attention and help, have a good day.

Today, I tried to solve a problem like this:

• Given $$$n$$$ convex hull, convex hull $$$i$$$ have size $$$m_i$$$, begin, you started in convex hull number $$$1$$$, then, with a operation, you can do:

1. Teleport to any points in current convex hull (with cost $$$0$$$), then use a balloon to fly to a point in another convex hull with cost is Euclid's distance between that two points.

2. Teleport to any points in any convex hull that you have visited with cost $$$0$$$.

Find minium cost to visit all the convex hull.

Input: $$$1\leq n, m_i\leq 200$$$.

My main idea to this problem is, find all edge between two convex hulls (easy to see, cost of that edge is closest distance between that two convex hulls, let call is $$$X$$$), then build the MST, answer is sum of the all cost of edge in MST.

But, I just can find the $$$X$$$ of two convex hulls in $$$O(m^2)$$$ and can't do better, can anyone help me with this. Thank you and sorry for my bad English.

Today I was try to solve this problem: https://mirror.codeforces.com/gym/100952/problem/J.

My main idea is:

• Find all point $$$X$$$s that $$$X$$$ is a node of $$$A$$$ and in $$$B$$$'s area.

• Find all point $$$X$$$s that $$$X$$$ is a node of $$$B$$$ and in $$$A$$$'s area.

• Find all intersection points of $$$A$$$ and $$$B$$$.

Let call the set of points we found is $$$S$$$, $$$S$$$ will be a convex hull, find the area of $$$S$$$ — the answer of problem.

But somehow I get WA verdict, can anyone help me to find out why, thanks all.

(This is my code: https://ideone.com/8wXu6a)

I have AC but now I have a weird problem: with the same code, sometime it AC but sometime it WA, is this a issue of Codeforces's judge or just my skill issue ;-;.

I see that dijkstra (and some shortest path algorithm) have a lot of variants like the roads have color, money and time to pass on a road,... etc. So, how to I practice them and how should I thinking for these problem.

Anyone please help me, I'm very need a help now, my national team selection contest is coming.

I'm currently learning fenwick tree and I find it quite difficult (in my opinion, it's more difficult than segment tree). As far as I know, most problems that can be solved with a fenwick tree can also be solved with a segment tree. So, in addition to memory optimization and simple usage, is there anything more optimal about fenwick tree than segment tree? And, sure, can anyone give me websites to use to learn fenwick tree? Thank you.