竞赛生涯

Qualification Round of Google Code Jam 2006

Posted on by snoopy

The funny game, Google Code Jam 2006(GCJ) is start 0:00 today, because of classes, I decided to start my qualification round this evening.

Grope(pj) said that GCJ will be easy but only 200 points can enter next round, when I meet him this noon. But I did a bad job, I got a Wrong Answer to the 750-points problem, because the algorithm I used was wrong, so, there is only 164 points I got from the 250-points problem.

I’ve see the summary and found that it’s hard to enter the next round. sigh~

个人赛,后两天

Posted on by snoopy 
编号.题目                    来源        简单说明
D3A.Bishops                 not found   简单公式题
D3B.Football Coach          not found   最大流
D3C.CLRS                    not found   DFS或者强联通分量
D3D.Sequence Again          POJ2478     筛素数法求欧拉函数
D3E.Intervals               not found   线段树
D3F.Matrix                  not found   矩阵构造+矩阵乘法

D4A.area                    not found   DP+凸包
D4B.Prime                   not found   求素数距离,筛法求素数到3*10^7
D4C.Traveling Queen Problem POJ2919     BFS+集合DP,BT题,我看标程都头大
D4D.Squares                 not found   BFS+Hash打表或双向BFS
D4E.Candies                 not found   贪心带硬搞
D4F.Card Game               POJ2062     最大匹配或者贪心

p.s.来源标注为not found均为目前还未找到来源的题,其中部分为KO原创,部分为
只改描叙的陈题

个人赛,前两天

Posted on by snoopy 
发信人: snoopy (Snoopy@T13), 信区: ACM_ICPC
标  题: 个人赛前两天题目来源
发信站: 珞珈山水BBS站 (Sat Aug 12 10:05:22 2006), 转信

非官方版本,今天早上找了一个小时找全了的
第二天的G据KO说是原创,但是和Tongji的1004防御导弹是一样的

编号.题目            来源        简单说明
D1A.dna             POJ1080     DP
D1B.Game            POJ1143     集合DP+博弈?
D1C.spell           POJ1035     直接硬搞
D1D.Frames          POJ1128     模拟?
D1E.Cable           POJ1064     转换成整数二分
D1F.2046            POJ1733     并查集+Hash
D1G.Transmitters    POJ1106     简单计算几何,算叉乘

D2A.Excel-lent      POJ2273     模拟,类进制转换
D2B.Dice            POJ1481     简单双重DFS
D2C.Rocket Height   POJ2276     初等几何,推公式
D2D.Slides          POJ1486     类匹配思想,硬搞
D2E.Lotto           POJ2193     DP,要用longlong
D2F.Optimal         POJ1480     BFS硬搞
D2G.Sequence        Tongji1004  贪心

除了第二天的G,全部都是没做过的...ft

最优匹配(Kuhn_Munkras算法)

Posted on by snoopy 
// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1

int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    fx[u]=1;
    for(v=1;v<=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret=0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i=1;i<=nx;i++) {
        lx[i]=-INF;
        for(j=1;j<=ny;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k<=nx;k++)
                if(fx[k]>0)
                    for(j=1;j<=ny;j++)
                        if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p);
            for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i<=ny;i++) ret+=w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************

最大匹配(匈牙利算法)

Posted on by snoopy 
// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1

int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    for(v=1;v<=ny;v++)
        if((mat[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((mat[u][v]...
    return(0);
} // end of int path()

int MaximumMatch()
{
    int i,ret=0;
    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++)
        if(matx[i]<0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************

KMP

Posted on by snoopy

直接抄的武大李春葆老师的数据结构上的改进KMP

// return the first matching string2 in the string1
#include <stdio.h>
#include <string.h>
#define MaxSize 1000

typedef struct
{
    char ch[MaxSize];
    int len;
} SqString;

void GetNextval(SqString t,int nextval[])
{
    int j=0,k=-1;
    nextval[0]=-1;
    while(j<t.len)
    {
        if((k==-1)||(t.ch[j]==t.ch[k]))
        {
            j++;
            k++;
            if(t.ch[j]!=t.ch[k]) nextval[j]=k;
            else nextval[j]=nextval[k];
        }
        else k=nextval[k];
    }
}

int KMP(SqString s,SqString t)
{
    int nextval[MaxSize],i=0,j=0,v;
    GetNextval(t,nextval);
    while((i<s.len)&&(j<t.len))
    {
        if((j==-1)||(s.ch[i]==t.ch[j]))
        {
            i++;
            j++;
        }
        else j=nextval[j];
    }
    if(j>=t.len) v=i-t.len;
    else v=-1;
    return(v);
}

int main()
{
//    freopen("kmp.in","r",stdin);
//    freopen("kmp.out","w",stdout);

    SqString str1,str2;
    gets(str1.ch);
    str1.len=strlen(str1.ch);
    gets(str2.ch);
    str2.len=strlen(str2.ch);
    printf("%dn",KMP(str1,str2));
    return(0);
}

RMQ

Posted on by snoopy

从whummd的blog上copy来的,加了点自己的修改,正在看,集训加油

// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];

void make_f2(int n)
{
    int i;
    for(i=0;i<=n;i++)
        f2[i]=1<<i;
    return;
}

void make_RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        r[i][0]=s[i];
    for(j=1;j<=log(n)/log(2);j++)
        for(i=1;i<=n;i++)
            r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
    return;
}

int RMQ(int i,int j)
{
    int k=int(log(j-i+1)/log(2));
    return(min(r[i][k],r[j-f2[k]+1][k]));
}

int main()
{
    freopen("rmp.in","r",stdin);
    freopen("rmp.out","w",stdout);

    int n,i,start,end;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    make_f2(20);
    make_RMQ(n);
    while(scanf("%d%d",&start,&end)!=EOF)
        printf("%dn",RMQ(start,end));
    return 0;
}

2006校赛总结

Posted on by snoopy

本来校赛结束前想把这个总结的第一句话来一句粗口的,因为实在是做很多事情太累了,knuthocean和littleken他们比我还要累,但是现在已经释然了.

首先要说一个为自己开脱责任的事情,校赛我是组织也是参赛选手,所以状态没那么好.并校赛前大约3个星期根本没碰题,校赛前一个星期去了一次上海,4天,预选赛还是队友做的.校赛做成这个样子,让很多人很失望,特别外校的,希望不要因为的的问题而让KMXS在大家的心目中地位下降…我只是KMXS最弱的一个人,还以这种状态参赛.

开始说校赛.练习赛的题都很简单,很easy的过了.不过有个小问题,因为做OJ的时候我一直在,然后知道在OJ上最后一行的空行往往被忽略的,并且前面knuthocean也说了比赛的时候Judge很人性化,不会卡空行,所以写Y的时候看中间空行就所有Case都加了个空行,所以还WA了一次.X是个判断直角三角形的问题,很多人想排序,我还是直接写了三个条件用||加上就AC了,事实证明我还是很有思维BT性的(小臭美一下 :P)

决赛当天早上6点多就起来了,和去年的两次区域赛一样,去简单吃早餐,在机房门口等开门.有一个小宣誓还是让小紧张了一下.很快比赛开始了,注意了一个细节是黄院长宣布比赛开始比9点要早一点,所以结束不是2点正,很多人有提到这个,都说是表慢了,其实不是.

在外面等的时候说了一下策略,我看后面三个,HongYi看前三个,ooeyusea看中间的.因为考虑到校赛,可能题目难度分布要照顾一下水平相对弱一点的,事实证明这个策略是对的.

进去后我一看I,好像以前做过的,然后敲,不过中间卡了一下,想证明那个距离是相加还是怎么,其实是取dx和dy的最大值,交后直接Yes,开局不错.

这时候全场就我们一个I的气球,别人都是A的,看了一下Ranklist,发现别人都过的A,然后看HongYi,她说她也是看的后三个,ft,估计赛前交流错了.然后马上看A,发现是个过于简单的题,然后上去敲,用qsort,发现无效,稍微停了10来秒决定直接用冒泡,反正才1000的数据,写好后交,Yes.

然后就开始随便看题,很多人的策略都是从前到后,我们过两个的时候很多人也是两个,不过一般是A和G.跟HongYi看G,说了一下意思,就是一个DP数塔,还是我上去写,测了一下Sample,没错,交,居然Wrong了…这下就有点急了,因为这个DP是高中就学过了,没道理WA啊,估计后面N多裁判都开始骂我了…都是看我一路过来的师兄.打印出代码,开始查错,看了看一个可能出错的地方,改了后还是WA.

到这个时候节奏已经比较乱了,因为本来我想的是我们不跟别人做题,要按自己的节奏来,这下就出问题了.跟HongYi说好意思她说她去,但是code速度比较慢,看她一直在处理3个数的最大值那个地方.我想到了可能是我的边界处理有问题,然后改了一下对边界的判断,交,继续WA.HongYi回来接着看她写的G,我在看其他题的时候一直想这个题目没道理有陷阱啊,难道是long long?不过参赛手册写清楚了啊.后来看了看我最后的判断,原来改边界判断后最后的判断没改正,修改后Yes了.

这个时候基本上都是3个了,我们算很慢的,很多队已经4个,牛一点的已经有5个了.因为我的G的问题,现在已经没办法按自己的节奏来了,把所有的题目扫了一遍.B感觉像以前看过的一个题,应该是网络流方向的,放弃或最后赌一下,C应该是贪心或DP,不知道如何处理,先放下,D乍看像数学题,不过稍微分析一下感觉就是和图论或者DP有关了(事实上最后说标准算法是图论的最短路,DP也是对的),E遍历树,没想好那个树的数据结构怎么处理,算法也没眉目,F一看就知道是凸包,不过过了一年还是不会凸包,并且HongYi说计算几何一般都容易出问题,所以都放开了,我一直都不是做计算几何的,他们两个也不会.

H一开始我就看到了,不过题目看错了,以为蚂蚁速度不一样,然后就复杂了,应该是个超级大模拟.不过这个时候ooeyusea说速度是一样的,然后立马感觉是我以前在ZOJ上做过的那个非环的题.写了很少的代码然后通过Sample,因为这个时候对罚时都比较麻木,并且这个题目也没打算过,加上队友都比较相信我,因为以前集训队内还算相对比较稳的,很多时候还是可以跟knuthocean做的(继续臭美:P),交了后WA,然后发现蚂蚁还是要交换,不会是直接硬搞,又回到初步的设想了,不过感觉是模拟的可能也不大,应该还是有公式.最后flirly说果然还是公式+调整.

在前面看B题的时候HongYi提出了一个把所有1放每行左边的想法,这样只要调整列,不过她觉得这样可能不对,那个时候就没写.在这个时候我感觉这是可行的,虽然场上还没人过B,倒是过CDE的有,C居多,分析了一下时间复杂度,O(n^3),题目说n<100,可以搞.很快将想法实践然后交,WA. 这个时候决定跟人了,因为越来越多的队开始过C,我去重新仔细看题,费老大劲看完了C前面的,然后发现是吹水,感慨一下不要被以前那些看Sample而失误吓倒就好了.大概构造了一下虽然心里认为DP的成分居多,但是还是想用贪心硬搞,先按最小时间排序,然后调整,主要是看怎么调整,应该是一个O(n^2)的算法,只是系数比较大,不过既然knuthocean说了不卡系数,就开始构造模型. HongYi上去看我的B测了一下数据,然后发现在 2 4 2 2 2 0 1 1 的时候我输出 1 1 0 0 1 1 0 0 明显错了,去Debug了一下发现没按我的构造思路走,稍微看了一下发现把一个n写成了m...果然还是自己对行列的定义跟别人不太一样引起的,自己开始写之前都提醒过自己这点的,但是还是犯错.改了后问队友是否交,队友还是很新人的说你觉得对了就交吧,交了后AC,第四个气球,粉色的,全场第二个粉球.后来看了看也只是比kk和magicpig他们慢了1min,还算好. 这个时候问队友对D和E有想法没,看RankList上貌似是D过的人比C过的人要多一点,但是大家都在攻C,自己还是想去硬搞.发现自己越来越想成为跟Grope一样的NB硬搞流选手了,比赛的时候自己看所有题也是一句话:硬搞啊~ 一开始想直接排序,然后发现这样有问题,必须要两个同时参加排序,并且不是一般的简单排,开始考虑贪心调整.这个时候没考虑好所有情况就开始上去敲,为后面的4次才过埋下隐患了.刚好这个时候午餐来了,该死,自己早上没吃饱,感觉饿着比较有灵感,事实也是如此. 看队友很Happy的吃完后自己写好code过了Sample,然后自己随便出了些想到的数据,都能完成.队友都比较相信我的让我交了,然后去吃饭,咬了两口汉堡然后返回了WA.HongYi和ooeyusea开始帮忙想数据,很快发现了几个有问题的.让他们考虑完全后我再去改,因为这个时候是准备赌题目数的,不那么在乎时间了. 其实在吃饭的时候感觉自己已经进入疲劳状态了,一直在抱怨比赛应该是3个小时的.因为自己一直都被认为是2个半小时选手,自己也认可,一直以来单挑的时间居多,跟knuthocean和MasT组成KMXS原型KMS的时候我的code量比较少,很多时候都只是在想,比较舒服,而今天几乎所有的code都是我完成的.MasT和其他人过来巡场的时候还特意说了我一下,MasT叫我不要又是那种比较散伙的消极比赛,其实已经在开玩笑跟ooeyusea说早上应该带一份报纸过来的.这个时候自己的心态已经有点不正常了,不过还是一直在改code. 在队友为我构造C题数据的时候我还看了看E,感觉应该做减法而不是加法,应该是把所有边的权值乘2后然后减去不重复的.这个时候发现我C的错误,去改了后反倒以前的数据不对了,然后对贪心的排序修正,没完全重写,只是小的修补.后来证明这是明显的拆西墙补东墙的事情...交了后继续WA. 自己有点放弃的意思了,都打算看别人了,在不停的刷排名.把所有没开的题目重新看了一遍,讨论了一下后觉得还是应该先把这个开了的题目过了,其他的都还没什么好的思路呢,就是E可能在靠近正确答案.HongYi继续在构造C的数据,我也在构造大数据看错误,找到了一个bug后把贪心的排序部分重写了一下,然后考虑了一些边界值,通过自己的所有数据,交,WA. 这个时候已经近乎抓狂了,不过对外的表情还是比较坦然的,不想让队友也放弃.这个时候因为网络负担太重,网络打印已经垮了,让Staff拿U盘拷出去把代码打出来后慢慢看.考虑了一下那个贪心到底对哪里有问题,然后感觉还是会有问题.重新构造后再通过全部的Sample,抱着死猪不怕开水烫的心情交了一遍,然后开始考虑E的遍历. 开始得出E的算法,不过在疑惑那么大的数据如何处理,特别是边的关系,用容器自己还是不会,本来都准备看看STL的,结果都被其他事在拖住.直接DFS考虑特殊情况是30000的数据铁定堆栈溢出,没敢下手,一直在纸上画图分析情况.这个时候C的提交返回了Yes,第五个气球来了. 看Rank现在是第八还是多少吧,过C前Galaxy过了第五题,这时候刚好超过他们,没有被大一的给bs...和队友说已经算圆满了,这么久没做题能这样也还算好了. 最后看了看感觉F和H是没希望了,D让两个队友去看,我只是知道大概是方差,要么DP要么图论,绝对不会是简单的数学.E的思路已经清楚了,就是去找一个最长的单链,这个单链只要走一遍.本来算法出来了应该很容易写code了,偏偏对这个该死的题目感觉有些无从下手了,因为如何存储那个树,邻接表是绝对不行的,链表感觉也不是很好处理,最好的应该是用容器,又是该死的STL... 还有大概不到一个小时,自己感觉是没题可以做的了,看队友讨论D,我上去写E看能不能在写code的过程中突然爆灵感(YY啊...).写E的时候感觉是在等死,就是在不停的刷Rank,然后看别人过题...自己已经没体力继续了.看了看在我们前面的都是外校的区域赛队伍,后面我们学校的估计也都不行了,能这样不错了,看Galaxy还在攻B,在比较频繁的提交,跟队友说估计他们一件抓狂了,站起来看他们也的确差不多了,不过还是感觉他们应该能在最后一个小时搞定的,在希望他们能给武大留一点最后的面子的同时也希望我们该死的T13队名能给别人带来坏运气(这都什么思维啊...). 最后真的是在放弃,HongYi对D给出了一个大概的公式,然后说后面很多还没想清楚,我也没仔细看和帮忙想,说你觉得可以就上去敲吧.260min的时候Neptune过了D,以过题多从后面超了上去.排我们前面的由此确定了队伍,剩下的只是他们之间的交换.最后20min左右校内的Dolaamo过了C,一阵欢呼,HongYi说她们在跟我们做,现在回头看summary也的确是这样的,刷Rank的时候看到cowork也上来到5题了,然后说幸好他们还不是那么散伙,让别人对武大看轻.HongYi也在放弃继续想D,让ooeyusea去看的F他一直也不敢写,策略失误让我们最弱的队友一直在看难题,后来他看的题我们一个也没开...MasT在最后还多给了一份午餐,在最后几十分钟内无聊的时间内填饱了肚子. 在pc^2上刷到最后5min的时候在站起来看别人了,HappyFish宣布还剩下几分钟的时候看了看只剩下1min,索性都跑后面去看Judge那边判最后的疯狂提交. 比赛结束了,散场~跟出题的和外校的交换了一下对题目的理解,E果然是找最长单链,存储也是用链表或者STL,只是我怀疑DFS会堆栈溢出的那个部分没人跟我说一个比较清楚的思路,现在想来和Galaxy还是谁说的用BFS实现就可以了,队列只要开到30000,做两次.D出题的说是图论最短路(跟前一天晚上跟ZSU的吃饭时MagicPig说HUST上某题有差不多的出题意图),做出来的很多人说就是DP就好了,现在还没去好好想这个.F是凸包没错,但是很奇怪为什么全场也没人过这个,现在回头看最后summary前面的也就是Australis,fish and bear,Afflatus开了这个题,后面是cowork开了,真正一直在做的应该只是fish and bear.H也果然是本次比赛最BT的题,flirly说还是得找公式然后调整,O(n)或者O(nlogn)吧,我记不清了 :P 比赛结束了,和大家一样,也列一个感谢名单吧. 感谢众多兄弟院校过来捧场并给我们一场如此精彩的比赛,希望大家能一起加油进步,场上的对手场下会是非常好的朋友. 感谢knuthocean,littleken,flirly,MasT等人给我们提供了一套非常好的题,感谢技术Staff和Judge,那么多来帮忙的老队员,感谢协助组织比赛累的半死的KongHui,感谢武大计算机学院学生会组织部和实践部的各位同学帮忙打了接近1k个气球并布置好了如此pp的现场,感谢KongHui等pp的气球MM. p.s.1.总结over了,说一个小插曲,本来是打算周一晚上写完就发的,看时间不够想上BBS上说一下我可能今天晚上搞不定了的时候结果还是被无情的停电了,BBS上都没发出消息,幸亏我还没事ctrl+s了一下这个总结. p.s.2.今天早上写最后一点的时候ooeyusea过来说H只要找到第一只蚂蚁的最后位置就可以了,因为全体蚂蚁的相对位置是没变的,感觉这样就靠近或者是最后思路了,赞~