Блог пользователя OtterZ

Codeforces Round 1087 (Div. 2) Announcement
Автор OtterZ, история, 7 недель назад, По-английски

Hello, Codeforces!

Alt text here

__baozii__ and I are glad to invite you to participate in Codeforces Round 1087 (Div. 2). The round will take place at Mar/21/2026 17:35 (Moscow time). There will be $$$6$$$ problems, and you will have $$$2$$$ hours to solve them. The round will be held according to the Codeforces rules and will be rated for division $$$2$$$.

At least one problem will be interactive, so we highly recommend you to read guide for interactive problems before the contest.

UPD: score distribution:$$$500 - 750 - 1500 - 1750 - 2250 - 3000$$$.
UPD:editorial

We would like to thank:

Wishing everyone good luck and high ratings!

upd:

top $$$10$$$:

  1. bismispis
  2. 415411
  3. TripleM5da
  4. StarSilk
  5. undefined_Ryan
  6. maspy
  7. Cody473
  8. antontrygubO_o
  9. YuukiS
  10. potato167

top $$$10$$$ rated:

  1. bismispis
  2. undefined_Ryan
  3. Cody473
  4. qwertyuiojhygtfdfg
  5. AJ123496
  6. pixelcoder20
  7. Ravnik
  8. Khai2007
  9. ixumqwq
  10. _annhien_ruby22

Notes that there will be an update about the top $$$10$$$ after roll-back.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +147
  • Проголосовать: не нравится

Border Theory:There's a fast approach to bruteforce on borders
Автор OtterZ, история, 4 месяца назад, По-английски

UPD:Thanks to comment from arvindf232 and pajenegod,I rewrote parts of this post to improve clarity with the help of Chatgpt. I hope it reads more smoothly now.

Preface

In this blog, I want to share Border Theory, a useful and elegant insight about string borders that often appears in competitive programming. Although this idea deserves to be as well-known as the KMP algorithm, many people today aren’t aware of it or how to use it to speed up their solutions.

Main Theoretical Result of Border Theory

Main Result

For a string $$$S$$$, a border is a substring that is both a prefix of $$$S$$$ and a suffix of $$$S$$$.

For a string $$$S$$$, we define that:

$$$ \{b_i\}_{i=1}^n$$$

is the sequence of all lengths of the border of $$$S$$$, sorted in increasing order.

According to the theory,it's garenteed that for all possible $$$S$$$, $$${B_i}_{i = 1}^n$$$ can be partitioned into $$$\operatorname{O}(\log |S|)$$$ continuous subsequences where each subsequence forms an arthmetic progressions.

Proof

First of all,if a string $$$T$$$ is a border of $$$S$$$ and $$$2|T| \ge |S|$$$, Then all positions where $$$T$$$ occurs in $$$S$$$ form an arthmetic progression.

proof

Second, All border lengths satisfying $$$2 \cdot length \ge |S|$$$ also appear in an arithmetic sequence:

proof

Using the two observations, we can show that for every two border length $$$x,y(x \lt y)$$$ do not lie in the same arithmetic subsequence, then $$$2x \lt y$$$, making the theory right.

Practical Use: The Series-Link (shlink) Trick

A practical formulation of this theory is the series link (often written shlink), which groups borders into arithmetic sequences so they can be processed efficiently.

We compute shlink[i] as the start of the next arithmetic progression. (Here link[i] is the usual border/failure link in KMP-style structures, len[i] is the length of the represented substring, and diff[i] is the differance of length between i and link[i].) Now $$$shlink_i$$$ can be calculated like this:

//define shlink[i]
//define link[i] as the maxinum border of i like fail pointers in KMP or PAM
//define len[i] as the length
//define diff[i] as the differance of length between i and link[i]
shlink[i] = link[i];
diff[i] = len[i] - len[link[i]];
if(diff[i] == diff[link[i]])
    shlink[i] = shlink[link[i]];

When we tries to analyze on borders,we found that:

When analyzing borders through these links, we observe: within an arithmetic progression of border lengths for a prefix of length $$$i$$$, the difference between consecutive border values (shifted by $$$diff_i$$$) corresponds to a border of length $$$i - diff_i$$$ and the corresponding occurrence position $$$i - len_{shlink_i} - diff_i$$$. This allows us to jump across long chains of borders in limited steps.

One example

Link

Given up to $$$5$$$ test cases,each with a string $$$S(1 \le |S| \le 5 \times 10 ^ 5)$$$ and an integer $$$w(1 \le w \le 10 ^ {18})$$$, when we have a string $$$T$$$ we can construct a new string $$$Y$$$ in the two ways: - Append the full string $$$T$$$ and $$$S$$$ and form a string with length $$$|T| + |S|$$$; - If a suffix $$$A$$$ in $$$T$$$ is also a prefix of $$$S$$$, you can overlap them and construct a string of length $$$|T| - |A| + |S|$$$.

Find the number of distinct length of strings in the range $$$[1,w]$$$ that can result from the process.

solution
code

Extention to palindromic suffixes

A string $$$s$$$ is called a palindrome if it equals its reverse. A palindromic suffix of a string is a suffix that is also a palindrome.

As we found that The borders of palindormes are also the palindromic suffixes of a palindrome, then we can say that for a string $$$S$$$, the sequence of the lengths of all palindromic suffixes in increasing order(which can be computed using PAM) can be partitioned into $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions. We can also say that the sequence of the lengths of all even-length palindromic suffixes in increasing order can be partitioned into $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions.

Tasks

In 932G - Палиндромное разбиение we can construct a string $$$T$$$ by:

  • $$$t_{2k - 1} = s_{k}$$$
  • $$$t_{2k} = s_{n - k + 1}$$$

Then the task turns to the number of ways to divide $$$T$$$ into several even-length palindromes, it's solvable for dynamic planning as $$$dp_i$$$ is the answer when the string is the prefix of length $$$i$$$ in the string $$$T$$$, with series link to speed it up.

code

These are similar to the solution to 906E - Перевороты,which constructs a string $$$T$$$ in this way:

  • $$$t_{2k - 1} = x_k$$$
  • $$$t_{2k} = y_k$$$

Then it's solvable for dynamic programming to find a partition of the string into even-length palindromes, minimizing the total count while allowing palindromes of length $$$2$$$ but excluding them from the count.

code

Summary

Though bruteforce on borders is slow, we can approach the algorithm using border theory,that shows that border lengths cluster into structured arithmetic sequences bounded in number by $$$\operatorname{O}(\log |S|)$$$ to make it much faster.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +129
  • Проголосовать: не нравится

Can anyone give a hand about the code?
Автор OtterZ, история, 6 месяцев назад, По-английски

I was using the code to solve 258E - Little Elephant and Tree:

#include<cstdio>
#include<set>
#include<vector>
using namespace std;
int n,dfs[100009],dfscnt,ot[100009],ots[100009];
vector<int>e[100009];
void tree_srh(int nk,int l){
	dfs[nk]=++dfscnt;
	for(int i=0;i<e[nk].size();i++){
		if(e[nk][i]==l)continue; 
		tree_srh(e[nk][i],nk);
	}
	ot[nk]=ots[dfs[nk]]=dfscnt;
} 
vector<int>seg_tree[(1<<21)];
int m,a,b;
multiset<int>s;
int ans[100009];
void add(int k,int l,int r,const int lq,const int rq,const int n_val){
//printf("%d %d %d %d %d\n",k,l,r,lq,rq);
	if(l>rq||r<lq)return;
	if(l>=lq&&r<=rq){
		seg_tree[k].push_back(n_val); 
		return;
	}
	int m=(l+r)>>1;
	add((k<<1),l,m,lq,rq,n_val);
	add((k<<1)|1,m+1,r,lq,rq,n_val);
} 
int tamp(){
	int u=1,ats=0;
	while(u<=n){
		multiset<int>::iterator it=s.lower_bound(u);
		if(it==s.end())break;
		ats+=ots[*it]-*it+1;
		u=ots[*it]+1;
	}
	return ats;
}
void solve(int k,int l,int r){
	//printf("%d %d %d\n",k,l,r); 
	for(int i=0;i<seg_tree[k].size();i++)s.insert(seg_tree[k][i]);
	if(l==r){
		ans[l]=tamp();
		if(!s.empty())ans[l]--;
	} 
	else{
		int m=(l+r)>>1;
		solve((k<<1),l,m);
		solve((k<<1)|1,m+1,r);
	}
	for(int i=0;i<seg_tree[k].size();i++)s.erase(s.find(seg_tree[k][i]));
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d %d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	tree_srh(1,0);
	/*for(int i=1;i<=n;i++){
		printf("%d ",dfs[i]);
	}
	putchar('\n');*/
	for(int i=1;i<=m;i++){
		scanf("%d %d",&a,&b);
		add(1,1,n,dfs[a],ot[a],dfs[a]);
		add(1,1,n,dfs[a],ot[a],dfs[b]);
		add(1,1,n,dfs[b],ot[b],dfs[a]);
		add(1,1,n,dfs[b],ot[b],dfs[b]);
	}
	solve(1,1,n);
	for(int i=1;i<=n;i++){
		printf("%d ",ans[dfs[i]]);
	}
	return 0;
}

The code passed the task quickly but I couldn't prove it was at the right time complexy.Could anyone tell me how to prove the time complexy of the code that is enough to pass the task or hack it? waiting for your answer.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

What to do if you found your code with right time complexy but too slow
Автор OtterZ, 6 месяцев назад, По-английски

1.Belief

Remember that most problemsetter ans coordinator don't like to hack right solution by the shortage of time.Most tasks are easy for right code to pass.

2.Simplified ways

There are simple ways to make your code fast,like a faster input or output,you can find out them while practising.

3.Reduce operations

Find out what is useless and delete them.Maybe it's slow because they are done while running but not make sence.

4.Merge calculations

Some calculation can be done together,then put them together.

5.Faster calculations

Some calculations are slow,try to replace them with faster ones.

6.Make use of precalculations

precalculate more before core calculation can make the code faster.Sometimes return value of functions can be precalcutated by just a small range,but can make the code fast.It can even make time complexy better.

7.Maybe we need a better algorithm

Sometimes a task can be solved by a faster algorithm,this may leads to unfriendliness of slower solutions.So if you found another faster algorithm,you can rewrite the code of it and then see if it's enough fast.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

maths for mincut problem:Do we really need to use Dinic to get mincut?
Автор OtterZ, 6 месяцев назад, По-английски

Introduction

The max-flow min-cut theorem is a cornerstone of combinatorial optimization, providing a powerful framework for modeling a wide range of problems. While algorithms like Dinic’s are standard for computing maximum flows, their time complexity—often bounded by $$$\operatorname{O}({|V|}^2|E|)$$$ or $$$\operatorname{O}(|E|\sqrt{|E|})$$$ can become prohibitive for large-scale or specially structured graphs.

This article explores an alternative strategy: instead of applying a generic flow algorithm, we directly analyze the min-cut formulation. The min-cut problem seeks the minimum total capacity of edges whose removal disconnects the source $$$s$$$ from the sink $$$t$$$. Formally, this is expressed as:

$$$ \min_{P,s\in P\land t\notin P}\{\sum_{u\in P,v\notin P}C(u,v)\} $$$

By reformulating this combinatorial problem as a mathematical optimization task, we can often exploit the specific structure of the graph to derive highly efficient, custom-tailored solutions. This approach transforms a graph algorithm problem into a mathematical one, which can be significantly faster for certain problem classes.

Examples

ABC332G

At first I'd like to say ABC332G is the task that made me think if I can solve mincut problems in this way.

In the task we make a graph for example $$$1$$$ like this,and similar for others:

we are tasked with a distribution problem that can be modeled as a min-cut. The constraints are too large for a direct application of Dinic’s algorithm, necessitating a more analytical approach.So we try to use maths and get($$$SETA$$$ for the nodes that represents balls and $$$SETB$$$ for boxes,$$$u_i$$$ as node for $$$i$$$-th colour,$$$v_i$$$ for $$$i$$$-th box):

$$$ \begin{aligned} \operatorname{maxflow}(G) &= \operatorname{mincut}(G)\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i + sum_{v_i \in P\cup SETB}B_i + sum_{u_i\in P\cup SETA,v_j \in \complement_V P \cup SETB}{i \cdot j}\}\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i + sum_j \min\{B_j,sum_{u_i\in P\cup SETA}{i \cdot j}\}\}\\

&= \min_k\{\min_{P,\sum_{u_i \in P} i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i\} + sum_j \min\{B_j,k \cdot j\}\}\\ \end{aligned} $$$

As

$$$\sum_j \min\{B_j,k \cdot j\}$$$

can be calculated using prefix sum,and

$$$\min_{P,\sum_{u_i \in P} i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i\}$$$

can be calculated using dynamic planning,so the task is then solved in $$$\operatorname{O}(n^3 + m)$$$.

code

2.ARC125E

For ARC125E,the graph is constructed like this:

and found the task presents another scenario where a direct max-flow computation is infeasible due to large values of $$$N,M,A_i,B_i,C_i$$$, which we has to calculate the mincut:

$$$ \begin{aligned} \operatorname{maxflow}(G) &= \operatorname{mincut}(G)\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i + sum_{v_i \in P\cup SETB}A_i + sum_{u_i\in P\cup SETA,v_j \in \complement_V P \cup SETB}{B_i}\}\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i + sum_j \min\{A_j,sum_{u_i\in P\cup SETA}{B_i}\}\}\\

&= \min_k\{\min_{P,\sum_{u_i \in P} B_i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i\} + sum_j \min\{A_j,k\}\}\\ \end{aligned} $$$

There,

$$$\operatorname{F}(x) = \sum_j\{\min \{A_j,x\} \}$$$

can be deem as an convex function that can be calculated using prefix sums and binary search in $$$\operatorname{O}(n) - \operatorname{O}(\log n)$$$,and

$$$\operatorname{G}(x) = \operatorname{F}(\sum B_i) -\operatorname{F}(\sum B_i — x)$$$

is an lower convex function. And for

$$$\operatorname{H}(k) = \min_{P,\sum_{u_i \in P} B_i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i\}$$$

,it's proven that we can just calculate

$$$\operatorname{H}(k) + \operatorname{F}(\sum B_i — k)$$$

just on the turning point of the low convex by adjustment.

prove

At last,the convex can be found by sorting the children in a non-decreasing order of $$$\frac{C_i}{B_i}$$$ and adding up the children one by one and solve the task in $$$\operatorname{O}(n\log n)$$$.

code

CF903G

In 903G - Yet Another Maxflow Problem, we are asked to compute a max-flow value in a dynamic graph. Again, a direct flow algorithm is too slow, but the min-cut formulation reveals a tractable mathematical structure:

$$$ min_{i,j}\{A_i + B_j + \sum_{x_k \le i,y_k \ge j}z_k\} = min_i \{a_i + min_j\{B_j + \sum_{x_k \le i,y_k \ge j}z_k\}\} $$$

The $$$j$$$ for getting the $$$\min{B_j + \sum_{x_k \le i,y_k \ge j}z_k}$$$ of each $$$i$$$ is non-decreasing,making it solvable using divide and consequer in $$$\operatorname{O}(n\log^2n)$$$,then for furthur things,we use segment tree and solve it easily.

code

At last

Полный текст и комментарии »

  • Проголосовать: нравится
  • +80
  • Проголосовать: не нравится

I have to say if you are not a LLM,please add "{}" after "if",this is very important
Автор OtterZ, история, 7 месяцев назад, По-английски

In fact,I don't want to use this to detect LLMs,but it's very important to say that because something wrong might happen if you don't do that.

In fact when I trying to find a mistake in a code,I saw:

for(int i = 1; i <= n; i ++){
	if(p[i].x > p[i - 1].x)
		if(p[i - 1].x != 0)
			f2 ++;
	else{
                dt2 ++;
		if(!gt[dt2 + cnt1])
			f2 ++;
	}
}

And found the code with same result is this:

for(int i = 1; i <= n; i ++){
	if(p[i].x > p[i - 1].x){
		if(p[i - 1].x != 0)
			f2 ++;
	        else{
                        dt2 ++;
		        if(!gt[dt2 + cnt1])
			        f2 ++;
	        }
        }
}

This will lead to WA and make you cost a long time to find mistake.So please write like this:

for(int i = 1; i <= n; i ++){
	if(p[i].x > p[i - 1].x){
		if(p[i - 1].x != 0){
			f2 ++;
                }
        }
	else{
                dt2 ++;
		if(!gt[dt2 + cnt1]){
			f2 ++;
                }
	}
}

To make sure the structure is right.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

[Tutorial] Compare different spanning trees on graphs
Автор OtterZ, история, 12 месяцев назад, По-английски

When I was trying to solve ABC419G in the contest,I found myself wrongly use BFS tree instead of DFS tree and failed,that day I found it might be important to write a tutorial about different spanning trees to make it easier to know how to choose right spanning trees while we're managing to solve graphs problems especailly the creative problems nowadays.I'll write down what I know and might extend the blog due to comments.

DFS tree

The reason I write about DFS trees first is that DFS trees arethe most common for simple graphs problem.When The code tries to run dfs algorithm on a graph starting with a node,the edges that was used to visit new nodes appears to be a tree.

On undirected graphs,the edges is garenteed to connect from a node to its ancesters(back edges) or its sons(tree edges),making it easier to study undirected graphs problems.

And on directed paths,the edges turns to four kinds:

  1. tree edges:edges from father nodes to its son;
  2. back edges:edges from a node to its ancesters;
  3. forward edges:edges from a node to its subtrees but not a tree edge;
  4. bridges:edges from a node to another node,neither its ancesters or in its subtrees,but visited before the nodes.

it appears that dfs trees divides edges to at most four types,making it easier to study graphs.

Mininum/Maxinum Spanning Trees

Such spanning tree is another useful one, and there are multiple problems just let you to find out the tree.

On undirected graphs with weights on edges,Mininum Spanning trees are constructed using greedy algorithms,with two core features:

  1. Mininum spanning trees leads to adding smaller edges first,and for all edges with weight smaller than a number $$$k$$$,such tree get most edges than other spanning trees.
  2. Any edges out of mininum spanning trees can make a circle with the edges on trees,and the edge is the maxinum in the cycle.

Contractions and Block Forests

In an undirected graph,if you contract edge biconnected components,you will get a tree,if you found some useful features on edge bitconnected components,just think of what to do on trees and then it's easy for you to get the algorithms for all undircted graphs.

And for Block forest,while nodes connect with the virtual nodes that stands to verticle bitconnected components, makes a tree,that is also used to study catcus when all verticle bitconnected components are garenteed to be an edge or a cycle.

Center trees

Some problem might be easy if we do divide and conquer on a tree.But sometimes we have to make it an online algorithm.But when we make a center trees,things turns to be similar as divide and conquer on a tree.Just find a center and divides the tree into parts to build trees,then you will find the max depth on a center tree is $$$\operatorname{O}(\log n)$$$.

virtual trees

Virtual trees is a spanning tree on trees,which just contain significant nodes for some problems,making yourself focus on a similar tree with less nodes.

shortest paths tree

Merging shortest paths from one node to others can make a tree.The edges out of the tree is garenteed not to make the path shorter.

write at last

Main author: OtterZ

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

I don't know if there is a way to deal with long queue sometimes.
Автор OtterZ, 12 месяцев назад, По-английски

Sometimes on codeforces,I submit a solution and found that I have to wait for a long queue to wait for result.If it is on contest,it will affect a lot on my performance even though I've got used to OI rules.I don't know how to make it fast to relieve long queue and keep participants from waiting too long.Please send something here about the solution. I hope Mike will use your idea afterwards.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Two simple ways to find the maxinum or mininum value of formula of straight line
Автор OtterZ, история, 14 месяцев назад, По-английски

When finding the contribution of a straight line in a problem and seeking the maximum or minimum value, some targeted algorithms are usually used to solve it. If you find a contribution formula related to the straight line formula and need to find the maximum or minimum value among the contribution values, consider the following algorithms.

1. Li Chao Segment Tree

1. Algorithm Explanation

The Li Chao segment tree is a data structure for handling straight line problems derived from the segment tree. The operations it can handle are:

  • Query the maximum or minimum value at a single point;
  • Add a straight line to an interval.

We build a segment tree for the interval (a segment tree with dynamic node creation is more common). Each node stores only one straight line (slope + intercept). For a single-point query, we traverse the points on the path from the root to the leaf node corresponding to the subscript, calculate the results corresponding to the stored straight lines, and make contributions. For adding a straight line, first find the corresponding nodes on the segment tree for the interval where the straight line is located, and then update a single node to be updated according to the following operations:

  • This node retains the straight line with the better value at the midpoint of the interval and passes the other straight line down.
  • If the straight line to be passed down is better at the left boundary of the interval, it is used to update the left child.

  • If the straight line to be passed down is better at the right boundary of the interval, it is used to update the right child.

  • If a vertically upward straight line appears, it is generally processed as a straight line with a slope of 0 and an intercept equal to the optimal point on the straight line.

It can be found that at most one of the operations in $$$2$$$ and $$$3$$$ will update the child. It can be concluded that the worst-case time complexity for a single-point update is $$$\operatorname{O}(\log_2 n)$$$. Any interval will correspond to $$$\operatorname{O}(\log_2 n)$$$ nodes, and the time complexity for adding a straight line to any interval is $$$\operatorname{O}(\log_2^2 n)$$$. However, when optimizing the straight line transfer, mostly only global addition is used, and only the root node needs to be updated, resulting in a time complexity of $$$\operatorname{O}(\log_2 n)$$$.

2. Advantages

  • Easy to use: Optimizing the straight line transfer with the Li Chao segment tree does not require ensuring the monotonicity of the straight line slope. It is straightforward to apply in implementation and supports persistence, merging, and splitting of the segment tree. When the number of operations is limited, it can be brutally cleared, which is very useful.
  • Code difficulty: The template of the Li Chao segment tree is similar to that of the segment tree. It is very simple for contestants who have mastered the segment tree proficiently. And the segment tree is a high-frequency knowledge point in competitions at the advanced level and above. Therefore, the code difficulty is not high for many contestants.
  • Efficiency: Compared with the CDQ divide-and-conquer method, the Li Chao segment tree is in most cases $$$\operatorname{O}(\log_2 n)$$$ times faster in efficiency.

3. Limitations

Using the Li Chao segment tree requires ensuring that the number of points for which the optimal value is sought is limited when the straight line formula makes contributions, and it cannot support deletion.

4. Problem

CodeForces1179D

2. Monotonic Queue and Convex Hull

1. Algorithm Explanation

For the situation where the slopes of the straight lines added are monotonically non-deteriorating in the order of addition and the query coordinates are monotonically increasing, consider using a monotonic queue to obtain:

  • When adding to the end of the queue, consider the magnitude of the abscissa of the intersection point of the added straight line and the last straight line and the abscissa of the intersection point of the last straight line and the previous straight line. If the former is smaller, delete the last straight line.
  • If the contribution of the straight line at the head of the queue is worse than that of the next one, delete the head of the queue.

Operation $$$1$$$ is continuously performed before insertion until the last element does not meet the deletion condition. Operation $$$2$$$ is continuously performed before insertion until the head of the queue does not meet the addition condition. In this way, we obtain a linear solution for this type of straight line transfer problem. If we explain the problem in another way: - Insert nodes, and the abscissas are monotonically increasing; - Query the intercept of the straight line with the largest slope passing through one of the points.

Then the solution is the convex hull. Also, maintain a double-ended queue. When inserting, delete the end of the queue when it is found to turn upward.

The two methods have different explanations but the same essence. You can choose according to your preference. For the situation where the query points are not necessarily monotonically increasing, consider not deleting the head of the queue and perform a binary search during the query, which will add an additional $$$\operatorname{O}(\log_2 n)$$$. For the situation where the slopes of the straight lines are not necessarily monotonically increasing, consider adding the CDQ divide-and-conquer method. Sort the left half according to the slope each time to update the right half, and the time complexity is $$$\operatorname{O}(n\log_2^2 n)$$$.

2.Advantages

  • Code difficulty: The queue part is easy to write, and the CDQ divide-and-conquer is not difficult to write either;
  • Efficiency: The insertion and deletion of the queue are amortized linearly.

3.Disadvantages

For the situation that requires the CDQ divide-and-conquer method, it needs to be offline, and it may be inconvenient to apply for complex problems.

4.Example Problem

SPOJ2940

3.Summary

Different algorithms have different advantages and disadvantages, and different algorithms should be used for different situations. In the problem of the maximum or minimum contribution of a straight line, we find that the Li Chao segment tree and the monotonic queue can help us solve this problem quickly and further handle more complex dynamic programming problems.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

I've spotted something wrong
Автор OtterZ, история, 15 месяцев назад, По-английски

I'm calling MikeMirzayanov to solve that.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

I'm wondering whether there's something to do to prevent UB
Автор OtterZ, история, 19 месяцев назад, По-английски

UB(short form of "Undefined Behavior",means something not lead to compile error but not defined) is easy to be ignored. In Codeforces the judge will report UB but in some contest UB may lead to running in a right way in DEVC++ or other local compilor,making it harder to prevent.

I've found that -Wall -Wextra won't report them all and '-fsanitize=undefined',which was mentioned and recommanded in articles I can find in Bing,is not supported in original Devc++(report "Cannot find '-lubsan'") or g++ in Linux,making it unable to be used in contests like CNOI or even CSP.I want to know if there's any other way to prevent in original local compilor.(Huge thanks if there's someone who can provide me with his experience about preventing UB in CNOI or CSP or NOIP).

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Some useful conclutions for some naive algorithms to solve number theory problem
Автор OtterZ, 19 месяцев назад, По-английски

Here are some useful conclutions for naive algorithms to solve number theory problem,I hope you can know something about it and solve number theory problems more easily.

1.The number of prime factors of an integer

It's sure that the number of prime factors of an integer is very small,and an integer $$$v$$$ can be the product of at most $$$\log_2(v)$$$ primes ($$$2 ^ k$$$ the worst).This can be used for bruteforce and State compression.

Thanks AkiLotus to remind me that for the number of distinct prime factors of a integer $$$\operatorname{w}(n)$$$,$$$\sum_{i = 1}^n \operatorname{w}(n)$$$ is $$$\operatorname{O}(n \log \log n)$$$.

example:510D,1422F - Boring Queries.

2.The number of factors of an integer

First of all,$$$\sum_{i = 1} ^ n \operatorname{d}(n) = \sum_{i = 1} ^ n [\frac{n}{i}] \approx n \ln n$$$.

Then I've found out that the number of factors of an integer($$$\operatorname{d}(n)$$$) is usually small,and to make sure,I made a code to get the maxinum number of the number of factors,and get:

  1. For $$$n \le 10 ^ 4,\operatorname{d}(n) \lt = 64$$$;
  2. For $$$n \le 5 \times 10 ^ 4,\operatorname{d}(n) \lt = 100$$$;
  3. For $$$n \le 10 ^ 5,\operatorname{d}(n) \lt = 128$$$;
  4. For $$$n \le 2 \times 10 ^ 5,\operatorname{d}(n) \lt = 160$$$;
  5. For $$$n \le 3 \times 10 ^ 5,\operatorname{d}(n) \lt = 180$$$;
  6. For $$$n \le 5 \times 10 ^ 5,\operatorname{d}(n) \lt = 200$$$;
  7. For $$$n \le 10 ^ 6,\operatorname{d}(n) \lt = 240$$$;
  8. For $$$n \le 5 \times 10 ^ 6,\operatorname{d}(n) \lt = 384$$$;
  9. For $$$n \le 10 ^ 7,\operatorname{d}(n) \lt = 448$$$;

So if your solution of a problem is $$$\operatorname{O}(n\max \operatorname{d}(a_i))$$$ or $$$\operatorname{O}(\sum \operatorname{d}(a_i))$$$,it might be correct because for $$$a_i \le 10 ^ 7$$$,it's sure that $$$\operatorname{d}(a_i) \le 500$$$.

examples:

3.Euler's Function: $$$\operatorname{O}(\log_2 n)$$$ times to $$$1$$$.

It's sure that $$$\phi(n) \le \frac{n}{2}$$$ for $$$2 | n$$$,and $$$2 | \phi(n)$$$ for $$$n \gt 1$$$.So if you use operation $$$x = \phi(x)$$$ for $$$x = n$$$ initially,it will become $$$1$$$ in $$$\operatorname{O}(\log_2 n)$$$ times.

In fact,it can be related to problems about power,when we try to solve the problem using Euler's Theorem or Extend Euler's Theorem.

example:

4.Prefixes: $$$\operatorname{O}(\log_2 n)$$$ distinct prefix great common diverse/and/or

Thanks Ghulam_Junaid and Timosh to remind me about the feature.

For $$$\gcd(a_1,a_2,...,a_k)$$$,We can add a new integer $$$a_{k + 1}$$$ and found:

  • If $$$\gcd(a_1,a_2,...,a_k) | a_{k + 1}$$$,it's sure that $$$\gcd(a_1,a_2,...,a_k,a_{k + 1}) = \gcd(a_1,a_2,...,a_k)$$$.
  • Otherwise,$$$\gcd(a_1,a_2,...,a_k,a_{k + 1}) \le [\frac{\gcd(a_1,a_2,...,a_k)}{2}]$$$.

So there are at most $$$\log_2 n$$$ distinct prefix great common diverse.

For operator and or or,every integers can be written by $$$\log_2 n$$$ digits,and:

  • For operator and,the number of "1" in the digits decreases;
  • And for operator or,the numbr of "1" increases;

So there are at most $$$\log_2 n$$$ prefixes and suffixes.

example:

5.At most $$$[2\sqrt{n}]$$$ distinct integers of $$$[\frac{n}{i}],1 \le i \le n$$$.

Known as number theory chunking in public,we can proof that $$$[\frac{n}{i}] = [\frac{n}{[\frac{n}{i}]}]$$$,and then split $$$[1,n]$$$ to $$$\operatorname{O}(\sqrt n)$$$ sections like $$$[l,r = [\frac{n}{l}]]$$$,it's really useful while calculating $$$\sum_{i = 1}^n \operatorname{f}([\frac{n}{i}])$$$ or it's easy to consider several integer $$$v_1,v_2,...,v_k$$$ together when $$$[\frac{n}{v_i}],1 \le i \le k$$$ is the same.

If we use Möbius inversion first,we might found that we have to calculate $$$\operatorname{f}(\frac{x}{d})$$$,using the feature we can found out that we can calculate the function just $$$[2\sqrt{n}]$$$ times for distinct numbers.

example:

6.Special fraction sums

Thanks hydra_cody.

  • $$$\sum_{i = 1}^n \frac{1}{i} \approx \ln n$$$
  • $$$\lim_{n \to \inf}\sum_{i = 1} ^ n \frac{1}{i ^ 2} = \frac{\pi ^ 2}{6}$$$
  • $$$\lim_{n \to \inf}\sum_{i = 0} ^ n \frac{1}{2 ^ i} = 2$$$

Last:written in the end:

I would like to thank:

Полный текст и комментарии »

  • Проголосовать: нравится
  • +147
  • Проголосовать: не нравится

Some bugs and features looks weird but really exists
Автор OtterZ, история, 19 месяцев назад, По-английски

There are some bugs and features exists while compiling a c++ code,it looks weird but really exists on standard c++ compiler.I'll write down the bugs and features here to remind you to aware of them.

1.stl::vector:fail to use operator "=".

I was trying to implent the merge function of segment tree while solving the task,and the initial code is

here

and found that it will get WA on test #6 using the language C++14(GCC 6-32).Then I found out that the

code

might got wrong.That because the location of lc[u] changed after using lc.push_back() and the same as rc[u],so the operator "=" might not work.

The bug have been fixed since C++17(GCC 7-32),but if you compile your code using language C++ and the previous version before C++17(GCC 7-32),the bug still exists.

2.vector:Can vector be compiled by head file ?

I've participated on a school contest and found that a code with stl :: vector ran successfully without head file <vector>,after that,I made some testing and found something miraculous:

If the compiler is on Windows system (on codeforces,Dev c++ on Windows,etc),you can use <algorithm> instead of <vector> to compile stl :: vector,but if the compiler is on Linux system (Luogu,and so on),<algorithm> is unable to compile stl :: vector.Also, in Windows <iostream> is able to compile stl :: vector and it's invalid to use <iostream> to compile stl :: vector in Linux.So,for participants,especially for Chinese who is willing to engage on Olympics in informatics,please be aware of this.

3.Have to trun __int128 to long long or int by hand

When I was writting codes,I found that:

__int128 I = 1;
fx[i] = I * (I * s1 * mod * fx2[i] + I * s2 * mod2 * fx[i]) % (mod * mod2) % 1000000007;

The code goes wrong due to __int128 goes wrong when turning to int or long long while printing or setting int or long long varibles.It should be:

__int128 I = 1;
fx[i] = (long long)(I * (I * s1 * mod * fx2[i] + I * s2 * mod2 * fx[i]) % (mod * mod2)) % 1000000007;

instead.

For more such bugs and features,you can reply to the comment and I'll put some of them that sometimes exists but not well-known here.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

Binary grouping
Автор OtterZ, 19 месяцев назад, По-английски

1.Introduction

Binary grouping is a way to implent dynamic insertion.If you found that the query for a data structure constructed by inserted elements from set $$$s$$$ can be answered online and be solved by uniting querys from a set of data structures built on a partition of $$$S$$$ in $$$O(h(n,m))$$$ as $$$m$$$ is the number of subsets in the partition and you can construct a data structure in $$$O(\operatorname{f}(n))$$$,It means that you can divide the elements in groups,for $$$n = \sum 2 ^ {a_i}(a_i \gt a_{i + 1})$$$,We can divide $$$n$$$ elements into groups,each group has $$$2^{a_k}$$$ elements,in this way we divided elements to $$$\log_2{n}$$$ groups.Then we build a data structure for each group of insertions using the construct algorithm.

When we insert a new element,we divide it in a group,and when we found a group that its size is the same as the new group,we merge the two groups into one group and rebuild a data structure with the elements in the group.Using the method,we get a way to implent dynamic insertion and the method to construct is $$$O(\sum {f(x)})(\sum x = n \log_2 n) \approx O(f(n)\log_2 n)$$$ in total and $$$O(h(n,\log_2 n))$$$ for each query.

2.Examples

It can be used for kd-tree,but I haven't found an example on the site,so please leave a comment if you found the example.

The example of using the method on kd-tree is P4148 on luogu,in the problem,the elements is the points in the first operation and we can use kd-tree to deal with the elements and answer the query online.But we have to implent dynamic insertion,so we use this method.

code

In CF710F,we use the method on AC-Automation.In the task,we use a group to deal with the inserted string and an another group for deleted strings.In both of the groups,we devide the strings into groups and deal with insertions using the method and make ACAM for each group. When we insert a string,we insert it to the group of inserted strings and insert it to the group of deleted string when we delete it.For querys,if $$$x_i$$$ means that How many string is concluded if we arrive index $$$i$$$ while running the ACAM,$$$y_i$$$ is how many string ends here in the trie,we get $$$x_i = y_i + x_{fail_i}$$$,and the way to get answer is:

  1. Run all the ACAMs in the group of inserted strings and add $$$x_i$$$ to answer while arriving index $$$i$$$.
  2. Run all the ACAMs in the group of deleted strings and minus answer by $$$x_i$$$ while arriving index $$$i$$$.

Here is the Accepted submission.

written at the end of the blog

We would like to thank:

  1. Computer scientists who invent the method;
  2. OtterZ edit the blog;
  3. DNR to give advice and make the blog better.
  4. adamant suggest a good problem as an example of using the trick.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится