search

henix / blog

some notes
0 stars 0 forks source link

Algorithm notes #22

Open henix opened 10 years ago

henix commented 10 years ago

stack with max

http://en.wikipedia.org/wiki/Dutch_national_flag_problem

find cycle in linked-list

duplicate linked list with random pointer

henix commented 10 years ago

egg-drop problem

henix commented 10 years ago

How to improve merge sort (poj 2299):

LaMarca, A.; Ladner, R. E. (1997). The influence of caches on the performance of sorting 一些 cache miss 的基本度量放方法，cache miss 的分类。

Engineering a Cache-Oblivious Sorting Algorithm 介绍了大量的 cache-oblivious 算法

henix commented 10 years ago

Counting Inversions problem:

Counting Inversions and Related Problems

Counting inversions, offline orthogonal range counting, and related problems

Paul F. Dietz(1989): Optimal Algorithms for List Indexing and Subset Rank

太复杂，又到 succinct 去了

henix commented 10 years ago

很多用树状数组解决的 inversion couning 问题都可以用 mergesort 解决。

poj 2299 Ultra-QuickSort 纯的求逆序数

poj 3067 Japan 交叉点也即逆序数，考虑到矩阵比较稠密，继续使用树状数组 + bitmap

poj 2352 Stars 矩阵相当稀疏，故可以 mergesort ，但最后还有一步统计。

Inversions Counting 可以转换成二维的 Dominace Point Counting 问题。

当矩阵稀疏的时候，用 mergesort 解决，当矩阵稠密的时候，用树状数组解决。