Tuesday, May 29, 2007

07年5月29日 在复旦大学的topcoder比赛

先是匹萨,棒约翰的,还不错,我和肖各吃了两块,就饱了,其实是不太好意思吃多 ^_^

然后是比赛,感觉脑子的转速要比在家里做快得多,时间也貌似比一般的一个半小时长得多(因为单位时间的思考能力强了,所以感觉时间就多了)。算是三校联赛吧,被复旦踩是必然的,目标是踩东华。最后338.31,是room2的第7,divsion的第13,还是被两个东华的踩了。

很久没写tc报告了,因为很久不关心算法。但今天还是满有意思的,写一下,纪念一下:

总得来说DIV2的题目就是比较简单的呀。

problem 250:
一个Set包括0-9个数字,其中6和9可以互用,隐含的意思就是可以表示 66 或 99 或 69。
然后给个门牌号,问至少买多少Set能够摆出这个门牌号。

算法很简单,统计一下门牌号中出现过的数字个数。因为6和9可以互用,所以把6的个数和9的个数平均一下,有两个写法:


// method one, after counting
count[6]=count[9]=(count[6]+count[9]+1)/2; // forget add one will be chanllenged

// method two, in counting iteration
if(count[6]<count[9]) count[6]++;
else count[9]++;


看到两个人用第一种写法忘记+1,cha之~,HOHO,赚100分。

problem 500:
有金G银S铜B三种钱币,去银行转换的规则如下:
11 S -> 1 G
11 B -> 1 S
1 G -> 9 S
1 S -> 9 B
问从G1 S1 B1换到 G2 S2 B2的最少交换次数,或-1表示不可能

与其说是贪心,不如说是逻辑题,只要依存简单的逻辑,就能既保证代码清晰,又可保证准确率:
step 1. 如果B不够,只能用S换B
step 2. 如果G不够,只能用S换G
step 3. B和G都够了,若S不够,先用G换S,再用B换S。因为G换S一次可以满足的S多,所以先G换S。

5555,前面的代码都是好好的,可惜最后在B换S的地方,忘记减去B,加上S了。。。好粗心啊 >.<
一开始沈发现了,但他给的cha数据没能把我cha掉~,洋洋得意地笑沈时,忽然某人把我cha了~ 瞬间郁闷

problem 1000:
比赛的时候想了n套方案,结果还是没能决定用什么方法解之。
题目意思是给出一个序列,要求用最小的cost排序,将i放到某个值后面/前面,花费的cost是i。

大大的程序千奇百怪,有STL库牛人的,有搜索解的,有DP的,不过最欣赏的是这个解法:
可以把问题转换为, 求顺序的最大cost的序列,然后用总cost减一下就行了。

例如sample 中的 6 4 5 3 8 2 7 2 11 2 2,顺序序列可以是 4 5 8 11,也可以是4 5 7 11,对于一个顺序序列,剩余的部分便是待移动的数,为了保证待移动的数的cost尽可能小,就是保证顺序序列的cost尽可能大,所以取 4 5 8 11 的cost和为28,所以只需要用最少52-28=24来完成排序。按照这个思路,有程序:


public int calcMinimalCost(int[] arr){
int total=0,len=arr.length,maxCost=0;
int[] cost=new int[len];

for(int i=0;i<len;++i){
cost[i]=arr[i];
total+=arr[i];

for(int j=0;j<i;++j){
if(arr[j]<=arr[i] && cost[j]+arr[i]>cost[i]){
cost[i]=cost[j]+arr[i];
}
}
maxCost=Math.max(cost[i],maxCost);
}

return total-maxCost;
}

Tuesday, May 22, 2007

Portlet with Ajax Tech (Jetspeed)

I was required to upload a large file via portlet with the process message displaying in the client side, and ajax would be the best choice. In order to ease the job, prototype was included first, so that the Ajax instance would do me a great help.

I've referred so many articles about the ajax application in portal, mostly work for WebSphere Portal rather than Jetspeed, tomcat-based portal. At last, I solved this problem, and as a conclude, I found that the problem could be broken down into three problem:

  1. Understanding the principle of the ajax application in portal, JSR-168 would be the most helpful reference. And here is a well-spread diagram to show this principle:

    As JSR168 said, portlet session could share the data with servlet session, so render the page via portlet and request the update from servlet, which makes the ajax realizable. Here is the article where the above diagram from.

  2. Share the data between portlet and servlet. Of cause, there are some applications do not need the servlet and portlet bundled, there would be unnecessary to consider this problem in such cases. But as to my problem, portlet and servlet should bundled together. As the articles I have read, I found it maybe was not a problem for WebSphere, but it's really a problem for tomcat based portal. The solution was so easy, just configure the server.xml like this, I mean to add emptySessionPath="true" attribute:

    <connector port="8080"
    maxthreads="150" minsparethreads="25" maxsparethreads="75"
    enablelookups="false" redirectport="8443" acceptcount="100"
    connectiontimeout="20000" disableuploadtimeout="true"
    emptysessionpath="true" />

    And read this article to know what the session identifier do to make such tricky problem.

  3. Last work is to write the codes and test it. So the last problem is about the coding.
    Most of these coding barriers could be taken easily via careful reading JSR168 Spec. Such as, portlet and servlet share data in APPLICATION_SCOPE, so using APPLICATION_SCOPE to store session. Url and javascript debuging would also cost a lot of time.


A good article about Ajax with WebSphere Portal:
http://www-128.ibm.com/developerworks/websphere/library/techarticles/0606_bishop/0606_bishop.html?ca=dgr-lnxw03AjaxPortals

So, it's really fun to work with portal, especially that using the ajax tech to make the portal more vivid. Hope this article help you solve your problem, thanks.

Sunday, May 06, 2007

DataTypes in PostgreSQL

It's quit a different world of PostgreSQL from MySQL. Before I began to use PostgreSQL, I thought all the relational DB are the same, just be familiar with ANSI SQL, and everything will be done. PostgreSQL proved me that it's a ludicrous thought, as an advance object-relational DB, PostgreSQL has guide me a new idea of DB world. It's not just a dull warehouse,where I put and get, but an amazing technology that with so many smart and fashion thoughts.

I learned two new tips of PostgreSQL's datatype today:

First is a notational convenience for unique identifier columns. In other relational DB, I am so familiar with the command

CREATE TABLE sometable (some_id INT(8) AUTO_INCREMENT, PRIMARY KEY(some_id));

but it was replaced by a notational type -- SERIAL or BIGSERIAL, just like the serialization in Java :)

CREATE TABLE sometable (some_id SERIAL, PRIMARY KEY(some_id));

then it will equal to:

CREATE TABLE sometable (some_id integer NOT NULL DEFAULT nextval('sometable_some_id::regclass')
, PRIMARY KEY(some_id));

Click here to see more.

Another tip is more useful, it's about the enum type in PostgreSQL, (MySQL support Enum, as I know, but it was still convenient to simulate enum type in PostgreSQL):
Here is a good article about it.

Three methods available:
Both 1st and 2nd methods use check constraint to the field, while 3rd use foreign key
Both 2nd and 3rd methods define a new DataType.
As to me, I prefered 2nd.

1st:

CREATE TABLE average_temperature
(
year INTEGER,
temp REAL,
season TEXT (CHECK season IN ('spring', 'summer', 'autumn', 'winter'))
);


2nd:

CREATE DOMAIN season_type
AS TEXT
CHECK (VALUE IN ('spring', 'summer', 'autumn', 'winter'));

CREATE TABLE average_temperature
(
year INTEGER,
temp REAL,
season season_type
);


3rd: (since every value based on an integer key, it will be able to sort and compare values)

CREATE TABLE season_lookup
(
code INT PRIMARY KEY,
value TEXT NOT NULL
);
INSERT INTO season_lookup VALUES(1,'spring');
INSERT INTO season_lookup VALUES(2,'summer');
INSERT INTO season_lookup VALUES(3,'autumn');
INSERT INTO season_lookup VALUES(4,'winter');
CREATE TABLE average_temperature
(
year INTEGER,
temp REAL,
season INT REFERENCES season_lookup(code)
);