大雪天裸体跪问关于young tableau的几道题目~~~ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

大雪天裸体跪问关于young tableau的几道题目~~~

大雪天裸体跪问关于young tableau的几道题目~~~# JobHunting - 待字闺中

e*e2011-03-08 08:03

1 楼

1. 给定M*N个不同的数，一共能生成多少个杨矩？如果允许数字有重复呢？
2. 给定杨矩，找k-th largest
（这题目我只有用最笨最蠢滴youngify 或者涂色法~~，有没有smart 的solution?)
可怜我想了好久（好久〉N天）也没想出好的solution.
那个谁谁谁，别老花精力把自己网站弄那么花哨~~~来来来。。。做题目~~

a*72011-03-08 08:03

2 楼

hehe i guess you are looking for ihave1337code
he has a post about searching in young matrix

e*e2011-03-08 08:03

3 楼

他那里只有search young tableau的~~~
就从左下角找啦~~~~~
这两题目也不知道是猴年马月哪个家伙提出来的，我郁闷了好久都没有想出方法

r*r2011-03-08 08:03

4 楼

What is "涂色法"

【在 e*****e 的大作中提到】

: 1. 给定M*N个不同的数，一共能生成多少个杨矩？如果允许数字有重复呢？
: 2. 给定杨矩，找k-th largest
: （这题目我只有用最笨最蠢滴youngify 或者涂色法~~，有没有smart 的solution?)
: 可怜我想了好久（好久〉N天）也没想出好的solution.
: 那个谁谁谁，别老花精力把自己网站弄那么花哨~~~来来来。。。做题目~~

e*e2011-03-08 08:03

5 楼

就是把当前最大的涂上黑色,下一个最大就只能在黑色区域的边上~~~

f*g2011-03-08 08:03

6 楼

2：
预备题目：已知一个数x，在young tab里面找，<=x的元素的个数。
这个是有O(n)算法的。
那么这道题，就有点类似于1-d数组找中位数的Order Statistics算法。
只不过，在一维中，用一个数字来记录当前位置。
在这里要用一个数组来记录当前位置。
以上是我的想法，以前版上也曾经有个人说过类似的思想。
从未写成代码。因为边界条件等等使这个题很复杂。

f*g2011-03-08 08:03

7 楼

如果较真的话，给你两个ref
你能看懂了，研究明白了，麻烦给我讲讲。
1. http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html
2. google this paper:
Selection in X+Y and Matrices With Sorted Rows and Columns