How optimal is Mo's algorithm?

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

What Mo's algorithm essentially does is this:

Given a set of q points in the plane, where the i-th point is (x_i, y_i) and 1 ≤ x_i ≤ y_i ≤ n, find a permutation of those points such that $\text{[math]}$ is minimized. So, the first question is this:
Does Mo's algorithm give us the optimal solution for this problem, or just an approximation of the optimal solution? The first problem is somewhat similar to the rectilinear (Manhattan distance) travelling salesman problem.
The second question is this: If Mo's algorithm actually gives us an approximation of the optimal solution (which seems to be the case), how much better is the optimal solution? (i.e. let's assume that the total distance in Mo's algorithm is x, and the total distance in the optimal solution for some set of points is y. What is the greatest value of y - x or $\text{[math]}$ ?) Also, what are some interesting observations about the optimal solution?
Question 3: What's the best algorithm that gives an exact solution to the first problem?

Комментарии (6)

Написать комментарий?

f2lk6wf90d

7 лет назад, # |

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

→ Ответить

Kallaseldor

I'm not sure on how to apply Mo's algorithm to this problem. I believe the classical application is to find the most frequent element in an interval. As for the problem you described, I can't think of any solutions other than the TSP... maybe there is a solution similar to the JOI 2016 — Skyscraper problem, though I'm not so sure.

7 лет назад, # ^ |

By Mo's algorithm, I mean the well-known comparator return (l1 / BLOCK_SIZE) < (l2 / BLOCK_SIZE) || ((l1 / BLOCK_SIZE) == (l2 / BLOCK_SIZE) && r1 < r2);. It is obvious how this gives an approximation to the solution to the first problem.

vintage_Vlad_Makeev

It gives optimal solution for worst instance of given problem. Consider O(n) points with coordinates of form $\text{[math]}$ . Distance shortest distance between pair of points is $\text{[math]}$ , so minimum value of the function above is $\text{[math]}$ and MO will find solution like that. In other cases MO will find permutation with cost that not worse than optimal solution for worst case, but maybe worse that optimal solution for given case.

Danial

← Rev. 2 →

if you change your compare function to bellow, you will get answer about 2 times faster:

bool cmp ( pair < int , int > p , pair < int , int > q )
{
	if ( p . first / BLOCK_SIZE != q . first / BLOCK_SIZE )
		return p < q ;
	return ( p . first / BLOCK_SIZE ) & 1 ) ^ ( p . Y < q . Y ) ; 
}

you can see this with compare this submissions

1.35150789 : 1216 ms

2.23682619 : 2246 ms

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