July 12, 2011

SGU 102 – GCD

 
/* The simplest GCD function.
 * but not eGCD.
 * Need to change to LL sometimes
 */
int gcd(int a, int b)
{
	return b?gcd(b,a%b):a;
}

July 12, 2011

SGU 101 – Euler Path

/* Find euler path or circle function
 * g[][] is the bi-directional graph
 * 0->6 are all the node
 * stack[] store the nodes in the path
 * adjacent nodes in stack[] form an edge
 * Function Call: euler(startNode x)
 */
void euler(int x)
{	
	for(int i=0;i<=6;i++)
		if(g[x][i]) // or "while(g[x][i])" both accepted
		{
			g[x][i]--; g[i][x]--;
			euler(i);
		}
	stack[++top]=x;
}

September 10, 2010

SRM481D1 500 (Greedy + Math)

一晃好多年，我终于爬回了D1，可是今天这场不怎么好过……NA LIB的无线果然不好使……断了两次……
其实250没做出来也不怪它……逻辑性好强……我没想清楚……唉……不早了，明天再想……

唯一值得庆幸的是最后过了500，虽然比赛规定时间内没完成，不过思路差不多对了，只是算法细节上要注意好多……

500是道概率题

问题是给你一条流水线，有n个job要做，但只有一台机器，每次只能做一个job。每个job都有需要的时间以及请求这个job的人。这个系统很聪明，他会schedule一套方案来让所有请求job的人（注意是人）等的时间的平均值最少。如果有几种方案，取任意一种。求的却是每个job完成时间的期望。

好了，首先我们要知道的是，这个机器是怎么schedule的。如果没有“人”这个条件的限制，很明显就是一个greedy，先做时间最少的。但问题这里是minimize人的平均等待时间。如果还是照之前的greedy，就出问题了。题目的Case1就是例子。稍微推一下就可以发现，schedule的方法是把每个人的job都合并起来，对总时间排序，先把一个人的做完了，再做下一个人的。但一个人的工作中间的次序是任意的，谁前谁后这就是要算期望了。推出这个期望跟杨辉三角很有关系~嗯~但是还没完，如果几个人的工作总时间相同，他们之间的顺序也任意，这又是一层期望。所以要算两层，外面这层还是跟杨辉三角有关……推出公式就发现很简单了，剩下的就是仔细code了。

code的时候因为时间最大是10^9，所以int超了，fail一次……改long long，有两个小地方没改过来，又fail一次，最后过的很顺利。印象中第一次做出D1 500，再接再厉。

贴code：

#include "cmath"
#include "ctime"
#include "iostream"
#include "string"
#include "vector"
#include "map"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
#include "queue"
using namespace std;
typedef long long LL;
LL t[55];
 
bool cmp(const int i,const int j)
{
    return t[i]&lt;t[j];
}
 
class BatchSystemRoulette {
public:
    vector &lt;double&gt; expectedFinishTimes( vector &lt;int&gt; duration, vector &lt;string&gt; user ) {
        int n=duration.size();
        map&lt;string,int&gt; m;
        vector&lt;int&gt; v[55];
        int id[55];
        vector&lt;double&gt; ret;
        memset(t,0,sizeof(t));
        int nu=0;
        for(int i=0;i&lt;n;i++)
            if(m.find(user[i])==m.end()) { m[user[i]]=nu++; }
        for(int i=0;i&lt;n;i++)
        {
            ret.push_back(0);
            t[m[user[i]]]+=duration[i];
            v[m[user[i]]].push_back(i);
        }
        for(int i=0;i&lt;nu;i++) id[i]=i;
        sort(id,id+nu,cmp);
        for(int i=0;i&lt;nu;i++)
        {
            int p=v[id[i]].size();
            for(int j=0;j&lt;p;j++)
            {
                ret[v[id[i]][j]]=duration[v[id[i]][j]]+(t[id[i]]-duration[v[id[i]][j]])/2.0;
            }
        }
        LL now=0,pre=t[id[0]],cnt=1;
        for(int i=1;i&lt;=nu;i++)
        {
            if(i==nu||t[id[i]]!=pre) {
                for(int j=i-1;j&gt;=i-cnt;j--)
                {
                    int p=v[id[j]].size();
                    double tmp=(now*2.0+(cnt-1)*pre)/2.0;
                    for(int k=0;k&lt;p;k++)
                    ret[v[id[j]][k]]+=tmp;
                }
                if(i!=nu)
                {
                    now+=cnt*pre;
                    cnt=1; pre=t[id[i]];
                }
            }
            else cnt++;
        }
        return ret;
    }
};

September 9, 2010

UVA 11813 Shopping(SPFA+DP)

以前从来没真正写过SPFA，难怪training的时候做不出来了……大悲剧啊……题目的意思就是说在一个很大很大的图中从一个固定的点开始访问其中一些点并最终回到起点，求最短的路径。一些点的数量不多过10个。很容易想到状态dp。
设dp[i][j]表示的是当前在i点并且已经访问了点的状态为j。转移方程为
dp[i][j]=dp[p][k]+dis[p][i] if( (j^k)==(1<<i) && (1<<p)&(k)==true )
其中j的已访问节点数比k大1。所以做bottom-up的DP，以已访问的节点数来做。

最后最麻烦的就是SPFA的写法，参照百度百科写了一个。效率还不错。

int n,m,s,st[11];
int next[200010],ev[200010],ew[200010],nbs[100005];
int used[100005],q[100005],dis[11][100005];
void spfa(int s,int id)
{
    int head=0,tail=1,u,v,w;
    for(int i=0;i&lt;n;i++) { used[i]=q[i]=0; dis[id][i]=inf; }
    dis[id][s]=0;
    q[tail]=s; used[s]=1;
    while(head!=tail)
    {
        head=(head+1)%(n+1);
        u=q[head];
        used[u]=0;
        for(int i=nbs[u];i;i=next[i])
        {
            v=ev[i]; w=ew[i];
            if(dis[id][v]-w&gt;dis[id][u])
            {
                dis[id][v]=dis[id][u]+w;
                if(!used[v])
                {
                    tail=(tail+1)%(n+1);
                    q[tail]=v; used[v]=1;
                }
            }
        }
    }
}

要加油了。

June 11, 2010

ACM Summer Training June 10,2010 – POJ2018 + IPCP 4477,4478,4479

唉，原本准备每次training完就写report的，结果你看……还是拖了这么久，而且上个星期的那套题目还没有补上，我这是多么的懒啊……

今天是GAG GUY 讲题目，这是我目前为止见过的最nb的acmer……因为他只是个高中生（中七），水平比我高……跟阿joe，Leo，Kn有的一拼，这让我再次明白了一个道理，那就是……没有谁是不能被替代的，长江后浪推前浪啊~~

（好困……）

May 28, 2010

ACM Summer Training May 27,2010 – SRM 470 DIV1 500

歇了好几个月的blog终于重见天日了。时间总是过得如此之快，一眨眼，3个月就这么过去了，期间发生的事情太多太多，而我又突然变得又忙又懒……于是，悲剧就这样产生，很多事情，我已然不是记得很清楚了。

然而我总是该写些什么的。

本来不想把这里变成一个技术blog的啊啊啊啊啊啊~~~

好了，言归正传。

下周开始星期一、二、四Training，星期一老队员讲课，星期二老队员打code，星期四老队员Seminar。这个暑假我负责讲DP……DP……一个又爱又恨的东西……

昨天敲定了这些事情，接着Gary讲了一道SRM470 D1 500的题目。

题目在这:http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153

一道关于概率的题目……不由得让我想起了327的final，最后就差一个概率题没做出来，不由得感叹数学是多么的重要。（这是后话）

题目的大概意思是说，有上下两排点，分别由N个，我现在告诉你其中一些pair已经连起来了，还有剩下的没有连起来的点随机的组合相连，问得是这N个pairs相交的数量的期望是多少。注意题目说的是Number of Crosses, 不是Number of intersection points。所以不需要考虑交于一点的可能。

然后……这个题目该怎么做呢？

我们知道期望是线性关系的，所以可以拆分……Totally我们一共有N条线，对于其中任意的两条，假设叫line X 和 Y。（且line X 的top point index 小于line Y的index），那么我们的总期望就是每一个这种pair的期望的和。对于line X 和 Y，一共有4种可能。两条都是fix的，两条都不是fix的，X是fix的而Y不是，Y是fix而X不是。对每种情况都可以计算。

1）对于两条都fix的，那么就直接判定它们相交与否。top[i]<top[j] && bottom[i]>bottom[j]

2）对于两条都不fix，期望是0.5。这个需要推算一下，应该不难，用CTLi的话说，应该好直观= =||

3）对于一条fix一条不fix的，统计下相交的点的数目再算出概率就行。

贴贴代码……这是O（N^2）的算法，ZQ有O（m^2）的算法，就不是挨个统计而是集体算= =||对于N很大的话可以瞬秒

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10005
#define clr(a) memset(a,0,sizeof(a))
class DrawingLines{
	public:
	double countLineCrossings(int n,vector up,vector down)
	{
		bool top[maxn],bottom[maxn];
		int  sa[maxn],sb[maxn],match[maxn];
		double ans=0;
		clr(top); clr(bottom); clr(sa); clr(sb);
		for(int i=0;imatch[j]) ans+=1;
				}else
				if(!top[i]&amp;&amp;top[j]) {
					ans+=((double)(n-match[j]-up.size()+sb[match[j]]))/(n-up.size());
				}else
				if(top[i]&amp;&amp;!top[j]) {
					ans+=((double)(match[i]-sb[match[i]]))/(n-up.size());
				}else {
					ans+=0.5;
				}
		return ans;
	}
};

Be With You

bearytale

Category Archives: ACM