某岛

… : "…アッカリ~ン . .. . " .. .
November 12, 2012

CodeChef November Challenge 2012

Level 1
Coin Flip: 签到
Delicious Dishes: 签到
Sridhar Likes Travelling:签到
Level 2
A Wonderful Chocolate:SCDP + 矩阵
Candy Collecting Game:DP Lucky Balance:组合
Jam Board:并查集 ( 注意卡 scanf()… 使用 getchar() .. .
Level 3
Arithmetic Progressions:链表优化暴力 ( 快速 FFT
Martial Arts:费用流 || KM ??
Many Left:卡时 + 启发式贪心

。。。考试周。。各种忙爆。。 himehime 做掉了 3 道签到题。。我做了中间 5 道题。。附加题中间交了 1 次。。。最后一天又改了改。。。。。。(。再次对 ACRush 深表敬佩。。真完美主义者!。跪烂!。

.. 本月最有价值的题是 Martial Arts
“给定一个 n 阶带权二分完全图。。求一个完备匹配。。使得该完备匹配去掉一组权值最大的边后。。权值最大。”。。。 ( n <= 100 .. )
。。(如果如果是求 n-1 条边的最优匹配的话可以直接费用流。。但是题目中问题的定义略有不同。。二分答案的话似乎这个题只是局部单调。。 已知最大权完备匹配(多解时取最大值最短的那组)。。减去权值最大的一条边是一个 “潜在解”。。(除此潜在解之外。。还有哪些是潜在解?。。如何通过增广转移过去?。。

————

。。。。也就是说我这个 SB 一开始就把题目抽象错了。。。实际上 tie-breaking 的情况是需要仔细处理的。(同样是因为 tie-breaking 的原因。。使得解只是局部单调。。无法直接二分答案。。)。我开始以为标程被 cha。。后来发现只是写解题报告的人也没有完全理解清楚。。评论的地方 anton_lunyov 给了极好的描述。。。总之直接看 Editorial 吧。。。

(也就是说可以理解成有两个玩家。。玩家 A(防御方)确定一个完备匹配。。之后玩家 B ( 进攻方)会干掉一个最优边。。注意这个和 k 部最优匹配之间的不同。这个问题要难很多。。)。。

。。唔。。。问题的关键是表述成 “a function of the weight of the highest weighted edge” 。。。之后拍 “Dynamic Assignment Problem” 。。( 只有单边修改操作。。)。。。一般情况下玩家 A 和玩家 B 朝相反方向决策。。而在 tie-breaking 的情况。。玩家 A 和 玩家 B 的目标又变得一致了。。这样直接向题解里开始说的 “To handle this we can consider each edge’s weight as pair (score difference, score to home team)” 是不行的。。我们需要这个结构设计两个比较函数。。

。。。基本融合了 标程anton_lunyov 的写法。。(anton_lunyov 是排序后正向插入边表。。标程是逆序删除。 … (。这样可以得到一个 5s 左右的剪枝。。

struct rec{

    LL x, y;

	rec(LL _x = 0):x(_x),y(_x){}
	rec(LL x, LL y):x(x),y(y){}

	rec  operator+ (const rec &rhs) const {return rec(x+rhs.x, y+rhs.y);}
	void operator+=(const rec &rhs) {x+=rhs.x, y+=rhs.y;}
	rec  operator- (const rec &rhs) const {return rec(x-rhs.x, y-rhs.y);}
	void operator-=(const rec &rhs) {x-=rhs.x, y-=rhs.y;}
	rec  operator-() const {return rec(-x, -y);}
	bool operator==(const rec &rhs) const {return x==rhs.x && y==rhs.y;}
    bool operator< (const rec &rhs) const {return x<rhs.x || x==rhs.x && y<rhs.y;}
    bool operator<=(const rec &rhs) const {return x<rhs.x || x==rhs.x && y<=rhs.y;}

    bool isZero() const {return (*this) == rec();}
    bool operator!() const {return isZero();}
    void output(){
        printf("%lld %lld\n", y, y - x);
    }

} W[N][N], lx[N], ly[N], slack[N];

inline bool comp(const rec &lhs, const rec &rhs){ //Player B perspective .. .
    return lhs.x < rhs.x || lhs.x == rhs.x && lhs.y > rhs.y;
}

。。权值对象。。以 pair 的形式存储 G-S 和 G 。。(。。。支持两个比较函数。。默认的小于。。和在 tie-breaking 下。。玩家 B 为视角的小于。。
。之后紧接一个 动态匈牙利 算法的模板。。。

int  px[N], py[N], pxx[N], ps[N], Q[N], op, cz;
bool vx[N], vy[N];
int n;

#define w(x, y) (lx[x] + ly[y] - W[x][y])

void add_to_tree(int x, int xx){
    vx[Q[op++] = x] = true, pxx[x] = xx;
    REP(y, n) if (w(x, y) < slack[y])
        slack[y] = w(x, y), ps[y] = x;
}

void augment(int root){ // 1. Designate each exposed (unmatched) node in V as the root of a Hungarian tree.

    int x, y; RST(vx, vy), op = cz = 0;
    pxx[x = root] = -1, add_to_tree(x, -1);
    REP_N(y, n) slack[y] = w(x, y), ps[y] = x;

    while (true){

        while (cz < op){ // 2. Grow the Hungarian trees rooted at the exposed nodes in the equality subgraph.
            x = Q[cz++]; REP_N(y, n) if (w(x, y).isZero() && !vy[y]){
                if (py[y] == -1) goto Augment;
                vy[y] = true, add_to_tree(py[y], x);
            }
        }

        rec delta = rec(INFF); // 3. Modify the dual variables lx and ly as follows to add new edges to the equality subgraph.
        REP(i, n) if (!vy[i]) checkMin(delta, slack[i]);
        REP(i, n){
            if (vx[i]) lx[i] -= delta;
            if (vy[i]) ly[i] += delta; else slack[i] -= delta;
        }

        REP_N(y, n) if (!vy[y] && slack[y].isZero()){ // 2.' Grow the Hungarian trees directely by the new edges in the equality subgraph.
            if (py[y] == -1){
                x = ps[y];
                goto Augment;
            }
            else {
                vy[y] = true; if (!vx])
                    add_to_tree(py[y], ps[y]);
            }
        }
    }

    assert(0); // !! Impossible Position !!..

    Augment: for (int t;x!=-1;x=pxx[x],y=t) // 4. Augment the current matching by flipping matched and unmatched edges along the selected augmenting path.
        t = px[x], py[y] = x, px[x] = y;
}


void KM(){

    static bool first_time = true;

    if (first_time){

        first_time = false;

        FLC(px, py, -1), RST(lx, ly);
        REP_2(i, j, n, n) checkMax(lx[i], W[i][j]);

        REP(root, n) augment(root);
    }
    else {
        // .. .
    }
}
#define y px[x]

rec maximum_match(){
	rec res = rec(); REP(x, n) res += W[x][y];
	return res;
}

rec secondary_match(){
	rec del = rec(0); REP(x, n) checkMax(del, W[x][y], comp);
	return maximum_match() - del;
}

#undef y

。。。此处的两个小函数。。分别是返回完备匹配。。和被删除一条边后的完备匹配。(下称亏格为 1 的匹配。。。。

vector<pair<PLL,PLL> > E;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

	RD(n); REP_2(i, j, n, n){
        LL p1, p2; RD(p1, p2);
        W[i][j] = rec(p1-p2, p1);
        E.PB(MP(MP(W[i][j].x, -W[i][j].y), MP(i,j)));
	}

	KM(), SRT(E);
	rec res = rec(-N*V);

	DWN(i, SZ(E), 0){

		int x = E[i].se.fi, y = E[i].se.se;

		int yy = px[x]; if (yy != y){
			W[x][y] = rec(V), px[x] = py[yy] = -1;
			checkMax(lx[x], W[x][y] - ly[y]);
			augment(x);
		}

		checkMax(res, secondary_match());

		W[x][y] = rec(-N*V);
		if (px[x]==y) {
			px[x] = py[y]=-1;
			augment(x);
		}

		if (maximum_match() <= res) break; // Cut .. .
	}

	res.output();
}

。。主函数。。(主要是排序边表。。以及逆序挨个删边。。。。
枚举每条边。。将该边的权值设置成最大(保证其一定被选中。增广一次后取解。。(此时求出的解此边的函数。。
。。。之后在设置成负无穷大。(。。表示删边。。删边不会导致可行顶标的修改。。但是也要增广一次。。

动态匹配。。O(n4).. .

其次是 Arithmetic Progressions 。。
“给定一个长度为 n 数列 {an},求所有满足 i < j < k,且 a[j] – a[i] = a[k] – a[j] 的三元组数。。”
( n <= 1e6, 1 <= ai <= 3e4 .. . )

。。开始的想法是链表优化的暴力算法。。。。然后是觉得正解应该是分块后使用 FFT。但是一交 TLE 。(当时猜测是常数写渣了。。后来发现确实是这样 T T。。。
。。。后来这个题就被搁置了。。直到期中考试前夕在评论区里看到姿势帝 anton_lunyov 说他姿势过了这题。。(。无限仰慕。。。。

“@kunalgaurav18 Because of the condition i < j < k. Well, for me this condition ruins very beautiful solution. Currently to handle this condition I have very bad solution that pass the TL which were very surprisingly for me.”

。。。然后我揣测了一下他这个思路。。回来写了一发居然过了。。 。。(。。大概是把分成前面一半和后面一半。。注意处理左边一半时要先插入进去然后逆序 Resume。。。(类似对 Dance Link 的处理。。

(最有仰慕一下 Rank I 的 CPU 并行的神犇。。标程已被撸爆!。)

————– PS :
… 给 SB Codechef 的 UI 跪了啊。。。每次进去要载入一个 Facebook 按钮。。然后呵呵呵你懂的。结果页面右边出来一大片白。。把各种按钮什么的全遮住了。。
。。。。每次都要用 审查元素 Kill 掉。。。。)

External link:

http://www.codechef.com/NOV12/