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)
);

Thursday, April 19, 2007

C++学习

发现很多公司要求C++,虽然工作已经有一个了。但7月上班,实在难耐,所以最近想着试几家大一点的公司,看看有没有更好的机会。由于强项在Java,很多大公司都只能望而却步。为了第一份工作一搏!决定重拾C++,发一帖学习日记,一是标出一些重点、难懂的东东;二是记录学习历程;三是可以给google友们多一个找答案的选择。
学习的书是问陈胖子借的,虽然不喜欢中文书,但听说翻译还可以,而且赶时间(就两个月了呀),呵呵,就不计较了。工具是VS2005,-_-b,可能要被小青年鄙视了,因为我整天就唠叨不要用VS,要用GCC。但确实,就业需求所逼,改吧。

Question 1: const
const很复杂,跟指针和引用混在一起更复杂。先两个概念,常量指针和指常量的指针:
int a=0;
const int *p1=&a; //指常量的指针,此处a可以是常量也可以不是,但结果是(*p1)不能再修改
int *const p2=&a; //常量指针,不可以改变p的指向,功能类似引用(但有区别)
const int *const p3=&a; //指常量的常量指针,上面两个特点综合一下

谈到指针和引用,说一下区别,引用是引对象,而指针就是地址。举些例子:
double a=0.0;
const int &b=a; //其实是先 int tmp=a;然后 const int &b=tmp; 因为b要引一个int对象,所以临时创建了一个
const int &c=0; //其实是先 int tmp=0;然后 const int &c=tmp; 同上,先创建一个对象


常量只可以用指常量的指针指。另有书上一例:
int *const &p=a; // 经检验,效果等同 int *const p=a;


Question 2: 陌生关键字
volatile : 表示变量是易变的,Java中也有。但C++中的含义是,编译器不能随意对该变量进行优化处理。即变量在编译器无法察觉的情况下可能改变。
sizeof : sizeof本身并不陌生,只上他有一点比较特殊,,sizeof是编译时刻计算的,因此被看作是常量表达式。


Question 3: 常用STL类型
vector 首当其冲,最好的替代数组的类型。有数组式的使用习惯和STL式的使用习惯,不能随意互用啊:
// 数组习惯
vector<int> vct(10);
for(int i=0 ; i<vct.size() ; ++i)
vct[i]=i;

// STL 习惯
vector<int> vct;
for(int i=0 ; i<10; ++i)
vct.push_back(i);
for(vector<int>::iterator iter=vct.begin() ; iter!=vct.end() ; ++iter)
cout<< *iter << endl;

complex 复数类型,可以用complex<double> 或者 complex<long double>等。
pair 关联两种类型的值。
bitset 向量类型,用 bitset<32>构造向量长度为32。
list,deque,map/multimap, set/multiset
stack 栈,其中与一般栈不同之处是普通栈的 pop删除头并返回头元素,而stl栈只删除不返回,它使用top返回头。
queue和priority_queue,队列和优先队列,priority_queue在Java下满好用的 ^_^。

Question 4: 自己写类
写一个完整的类不容易啊,首先分为三个基本步骤(自己总结的,不知道对不对):
1 类定义,常定义在.h文件中
2 函数、变量定义,.cpp文件的部分
3 添加其他会使用到该类的其他类中的方法,典型的如 istream& operator >>( istream&,类&) 等。

在定义时也能定义部分类函数和变量,在类定义中定义的函数的都是缺省为inline的(使用频率高的,短小的代码可以考虑声明为inline)。在类外定义的需要显示声明inline。

类定义基本结构:

#include <iostream> //包含需要使用的头文件

class Sample; // 先声明一下类

// 声明一些会使用到该类的函数
istream& operator >( istream&, Sample&amp;);

// 类定义
class Sample
{
public:
Sample(); //默认构造函数及其他构造函数
Sample( const Sample&); //拷贝构造函数,如果需要

~Sample(); //析构

Sample& operator = (const Sample&amp;); //重载操作符

void setValue(int); //定义成员函数
private:
int _value; //定义成员变量
};

Question 5: 显式转换
新式(标准C++)强制类型转换: static_cast,dynamic_cast,const_cast,reinterpret_cast
任何非const数据类型的指针都可以被赋值给void* 指针。
const_cast< type >( expression ) 用于转换掉表达式的常量性 (以及volatile对象的volatile性)。
static_cast< type >( expression ) 编译器隐式执行的任何类型转换都可以由它显式完成。
reinterpret_cast< type >( expression) 对于操作数的位模式执行一个比较低层次的重新解释,它的正确性很大程度上依赖于程序员的主动管理。
dynamic_cast<type>( expression )支持运行时刻识别由指针或引用指向的对象。


旧式(标准C++前)强制类型转换:可以替代static_cast、const_cast、reinterpret_cast。

Question 6: 容器
抽象容器类型{
顺序容器(sequence container): list,vector,deque
关联容器(associative container):map,set
}

每个容器支持一组关系操作符,可以用来比较两个容器。第一个不相等元素的比较决定了两个容器的大小关系。
容器的类型有三个限制
  • 元素类型必须支持等于操作符
  • 元素类型必须支持小于操作符
  • 元素类型必须支持一个缺省值
所有预定义数据类型,包括指针,都满足这些限制,C++标准库给出的所有类型也一样。

Question 6: 迭代器
除了iterator类型,还定义了一个const_iterator类型,后者对于遍历const容器是必需的。 iterator算术运算只适用于vector或deque,而不适用于list。

Question 7: 函数
参数为数组,数组确实满麻烦的,首先数组参数绝不会传值,传的是指针。举以下五个例子,前三者相同:

void putValues(int*);
void putValues(int[]);
void putValues(int[ 10 ]);
void putValues(int (&arr)[10]); //参数为10个int的数组,因为参数是引用的,即数组长度成为参数的一部分
void putValues(int matrix[][10], int rowSize); // 第一维长度为rowSize,第二维长度是10
void putValues( vector<int> &vec ); //vector是替代数组的最好类型


指定函数的缺省实参:

int func1(int a,int b=0,int c=0);

int func2(int a,int b,int c=0); // 初始化最右边参数
int func2(int a,int b=0,int c); //可以!此时b c都有缺省参数
int func2(int a,int b=0,int c=0); //错误,bc已经有缺省参数

int func3(int a,int b,int c=func1(1)); //缺省实参可以是任意表达式

int func4(...); // ellipsis 省略号,告知编译器,函数调用时,可以有0或多个实参,而类型未知


命名返回值优化,易犯错误:
1 返回一个指向局部对象的引用。局部对象的生命周期随函数的结束而结束。

Matrix& func()
{
Matrix a;
return a; // 错误,结果将指向一个错误的位置
}



2 函数返回一个左值,对返回值的任何修改都将改变被返回的实际对象。

int& get_val( vector<int> &vi, int ix)
{
return vi[ix];
}

int ai[4] = {0,1,2,3};

vector vec(ai, ai+4);

int main()
{
get_val(vec,0)++;
}


正确使用命名返回值优化:

Matrix& get(Matrix *p)
{
Matrix *res = new Matrix(); //动态分配的,函数结束不会结束
*res=*p;
return *res;
}

函数指针(指向函数的指针类型):

int cmp1(const string &s1, const string &s2)
{
return 1;
}

int cmp2(const string &s1, const string &s2)
{
return 0;
}

int *pf(const string&, const string&amp;amp;amp;amp;amp;amp;); // 错误,返回类型指针
int (*pv)(const string&, const string&amp;amp;amp;amp;amp;amp;) = 0; //初始化,不指向任何东西
int (*pf)(const string&, const string&amp;amp;amp;amp;amp;amp;) = cmp1; //正确,pf 是指向函数的指针
pf=cmp2; //赋值,可以
pf=&cmp1; //可以,同上

cmp1("a","b");
pf("a","b");
(*pf)("a","b"); //三个效果相同,返回1


函数指针的数组(so...神奇):

int func1(const int &a,const int &amp;amp;amp;amp;amp;amp;b);
int func2(const int &a,const int &amp;amp;amp;amp;amp;amp;b);

typedef int (*PFV)(); //定义函数类型指针的typedef
PFV tc1[10]; // 函数指针数组长度为10
PFV tc2 = { func1, func2 }; // 初始化
tc1[0] = &func1; // 赋值
tc1[0](10,20); //调用
((*tc1)[0])(10,20); // 显式调用


函数指针可以作为返回类型,但是函数不能做为返回类型:

int (*func(int))(int, int); // ff为函数,有一个int参数,返回一个指向函数的指针,该指针类型为 int (*)(int, int);

typedef int (*PF)(int, int);
PF ff( int ); //更优雅

typedef int func(int, int);
func ff(int); // 错误,返回类型不能是函数类型



Question 8: extern
链接指示符 extern "C" / extern "Ada" / extern "FORTRAN"
告诉编译器,该函数是使用其他语言编写的:

extern "C" void exit(int);

extern "C"
{
int printf( const char* ...);
int scanf(const char* ...);
}

extern "C"
{
#include <cmath>
}

Question 9: 头文件
头文件为所有extern对象声明、函数声明以及inline函数定义提供了一个集中的位置。
预编译头文件而不是普通头文件可以大大降低应用程序的编译时间。
头文件不应该含有非inline函数或对象的定义。否则将可能使同一程序的两个或多个文件中包含,就会产生重复定义的编译错误。


Question 10: 域和生命期
局部对象:自动对象、寄存器对象、局部静态对象

自动对象地址不应该被用作函数的返回值,因为函数一旦结束了,该地址就指向一个无效的存储区。当一个自动变量的地址被存储在一个生命周期长于它的指针时,该指针被称为空悬指针(dangling pointer)。

寄存器自动对象:在函数中频繁被使用的自动变量可以用register声明。

for( register int ix=0; ix


静态局部对象:未初始化的静态局部对象会被程序自动初始化为0,相反,自动对象的值是任意的,除非它被显式初始化。

动态分配的对象:空闲存储区被耗尽时,new表达式失败,所以抛出一个bad_alloc异常。delete会调用操作符delete(), C++保证若指针被设置为0,则不会调用delete(),故之前没必要测试指针是否为0。但delete之后,并不会把指针赋值为0。

auto_ptr
auto_ptr可以帮助程序员自动管理用new表达式动态分配的单个对象,不支持数组。


#include
auto_ptr< type_pointed_to > identifier( ptr_allocated_bynew );
auto_ptr< type_pointed_to > identifier( auto_ptr_of_same_type );
auto_ptr< type_pointed_to > identifier;

auto_ptr< int > pi(new int(1024));

由于操作支持都是内联的,所以效率不比直接使用指针代价高。ptr相关操作:
reset: 初始化后,就只能用reset再对auto_ptr赋值了。
get: 返回auto_ptr对象内部的底层指针。
release:允许将一个auto_ptr对象的底层对象初始化或赋值给第二个对象,而不会使两个auto_ptr对象同时拥有同一对象的所有权。

定位new表达式:

new ( place_address ) type-specifier // 表达式格式

class Foo{};
char *buf = new char [ 1024 ];
Foo *pb = new ( buf ) Foo; //无须delete
delete[] buf;

韩片《无道里》

最近看了几部电影:《忍者神龟》(美)、《汉江怪物》(韩)、《博物馆之夜》(美)、《无道里》(韩)。发觉韩片真的相当地出色,拍摄手法啊这些专业的东西我是不清楚,但是剧情确实相当有看头的。《无道里》我是今天看的,虽然是喜剧,但却折射出了一些内心的东西。最后,剧情的巧妙给了我一个意外地冲击,流了两滴泪。



这里是“无道里”,除非你想跳崖,不然不会到这里来。一日,在悬崖边的小村庄里居住的三个老头发现悬崖边上留着一双鞋。不久,跳崖者的家属来到了小村庄,当老头把鞋递给跳崖者家属的时候,家属留了笔钱给三老头以表示感谢。于是,一边是跳崖(自杀)胜地的扬名,另一边是老头们商量着如何靠跳崖发财。
再看首尔,一名女记者因为找不到够爆的新闻,正在发愁的时候,在一家网吧意外发现了一名准自杀者留下的〈自杀者天堂〉网页。女记者意识到发财的机会来了!于是出动吧。

大家齐聚“无道里”,晚上开开自杀讨论会,第二天早上去自杀,未遂,晚上再开会,早上再自杀,未遂...... 老头们也在想尽办法催大家赶快自杀...... 你急我也急...... 最后...... 想知道最后怎么着了?自己看电影吧。(注意海报最左边的老头~ 很色的哦 ^_^)

Install Jetspeed with PostgreSQL

Since my graduation design request PostgreSQL, I have to give up MySql. PostgreSQL is quit different from MySql, as most extension commands of MySql, like SHOW TABLES , does not work in Postgre, and the structure of Postgre is entirely unfamiliar for me.

Although the installation of Jetspeed's DB is so simple that just three steps:
1 create a database
2 grant the privilege
3 download the JDBC
which still took me almost two hours to accomplish it, for the account and network configuration is some bit complex.

First of all, write a test java file, which is of great help, the following code (replace 'testdb') should be included in the file:
Class.forName("org.postgresql.Driver");
Connection db = DriverManager.getConnection("jdbc:postgresql://localhost:5432/jetspeed", "jetspeed", "jetspeed");

Compile it, JDBC file was not necessary during compilation phase, but it should be appended to the classpath before executing the test program.

Second, install PostgreSQL if it was not installed before. Source installation would be a better choice, and here is the link of PostgreSQL official site. Install via apt would be the most convenient way, I like apt and ubuntu :) .

Third, initialize a DB cluster(apt installation has already initialize one), like the following command:
$ initdb -D /usr/local/pgsql/data

Find pg_hba.conf and postgresql.conf in the directory of DB cluster. Login the cli environment of PostgreSQL (notice: there are two databases already exist, template0 and template1):
$ postmaster -S -D /usr/local/pgsql/data  #start the db server background
$ psql template0


Fourth, assure that the TCP/IP connection was available. Modify postgresql.conf as below:
listen_addresses='*'
port=5432
tcpip_socket=true


Fifth, modify pg_hba.conf (refer to this):
local all    password
host all all 127.0.0.1/32 password

Caution: Start a new line at the end of file. And restart the server after the configuration completed.

Sixth, create a user and create the database, then grant the control privilege to the user. There're several ways to do it, just like this one:
$ createuser -d -P  # create a user with the privilege of database create and a prompt for the password of the new userd
... # input the user info,like username is 'jetspeed' and password is 'jetspeed'
$ createdb jetspeed -U jetspeed -W # create a new db and the creator is 'jetspeed'
# if error reported, maybe pg_hba.conf was incorrected configured.


Seventh, run the JDBC test. If the test succeed, there would be no problem of Jetspeed installation.

Saturday, April 14, 2007

2007年4月的第二周

这一周很忙,也很闲。
首先是上周五,毕业设计需要我去合作的那家单位走一趟。早早地我就起床了,按着昨日网上找好的路线找了2个半小时左右,后来与老师电话后才知道,我找错单位了 -_-b 。随后老师让我不用去了,他们谈好了再通知我。心中一边抱怨着这个不知道在瞎忙什么的毕业设计,一边
低着头沮丧得走着那2小时的回家路。

周一、周二,我奉献给了学校,也就是我那毕业设计。因为了是签了合同的项目,老师又希望我冲优,所以我一直也不敢怠慢。但是,那个单位不懂装懂的一套莫名的号称“创新”的设计实在是把我惹得对该项目厌恶之极。两天的下午,我就坐在那里(傻傻地),装着一些我认为几乎没有价值的,至少对我的毕设而言是没价值的,却又是相当复杂的系统(globus toolkit)。而我要做的那部分(portal),已经完全被搁置了,写完前端后一直等那个单位给我接口,但最后等到的,除了“下周给”还是“下周给”。不是说他们不干事,真的,为什么这么一家还算不错的公司竟然效率这么低呢。

周三,topcoder的marathon结束了。由于浪费了太多时间在毕设上,周三想恶补一下tc的,但最后还是没能如愿,反而最后一次提交的成绩还不如之前的那次好。说实话,这次的marathon是很有趣的,我真的满想静下心来认真做一下。但是除了毕设,周四还有一个相当重要的面试。

周三早5点,我起床,为了周四不知道,周三先去摸摸情况。2小时的路程将我整得相当疲惫,又是2小时的回程,回到家里人像一滩泥,散在椅子上了。不过我硬撑着,如果现在睡了,那么晚上我一定睡不着,所以为了明天早起,不能睡!

周四早5点,起床,准备就绪,出门。今天有个大面试,之所以如此重视它,除了公司名气相当大之外,还有两个原因: 一是已经有我的两个好伙伴收到了公司offer(就是他们推荐我的),为了我们能一起在这家公司里闯事业,我很希望能够进这家公司;二是该公司的面试十分专业,除了让我感受到了公司招人的诚心之外,公司的办事效率也相当值得称赞。面试要持续到下午,做了10道左右的题目,其中写了完整程序的有5道好像。有一道卡住一会,但在面试官的提醒下还是说出了解题的关键算法。还有一道与面试官在题意上有冲突,虽然一开始和面试官有点交流不畅,但后面的两个问题还是解决得满顺的。第二面十分完美,除了题目在很短的时间内做出来以外,中间发生了一段小插曲:我的肚子叫了(-_-b 早饭没吃饱啊),面试官很友善地给我拿了咖啡和饼干,咖啡很好喝。另外,最后一位面试官送我走之前,给了我一个KFC汉堡包,^_^,对公司好感度顿时增加到100%!总体感觉还是不错的,事后我有发觉我的程序还是有漏洞的,但我想结果并不重要,我把我解决问题的思路和方法展现给了面试官,所以面试还是成功的。

面试结束后,我去超市买了不少吃的,脑力和体力消耗太多,需要补一下。晚7点,做tc算法的round 1c,虽然人还是有点疲倦,但听说过round 1就有飞盘~,拼了!第一题很容易就解决了。第二题卡了,写了个DP,但结果始终不对。想到了二分答案,但是我不会写二分答案的算法(知道有点像二分搜索,但因为从来没写过,一下子也摸不着头脑)。结果只做了第一题,最后的结果是排名152名好像。晋级是没有问题的,只是只做了一题,始终感觉不是很爽。过两天就是round 2,+U。

今天marathon成绩出来了,排名150+,不理想,rating也跌了不少。另一件关于tc的事是我的blog增加了一个看tc算法赛事的widget。原本我用flash写的一个,有图片,类tc个人资料的那个flash的。但后来发觉导出成swf就怎么都连不上topcoder,那就拿不到feed了,但是exe和直接在flash IDE下调试是完全成功的。郁闷,不能出swf那就不能挂在blog上了,所以花了半天时间再写了一个javascript的,只是是文字,跟图表的效果是没法比的。



附加一个用CSS 做 tooltip的好文章链接:
http://www.communitymx.com/content/article.cfm?cid=4E2C0&print=true#

为什么我一开始说很忙又很闲呢,忙得是这周事情不少,闲的是大部分事情都只是在花时间和体力,比如毕设、flash的tc rating表白做了和面试那两天的8个小时路程,总有一种在浪费时间的感觉。

Saturday, April 07, 2007

Cute Otters.

Otters hand by hand, looks so sweet.

I saw them on the news and decide to check it out, they're stars now!

Tuesday, April 03, 2007

TCO Marathon Online Round #2

TCO Marathon OR2 finished. I got 65/445 rank, 11331.73 score, and advance to round 3 successfully. My friend, FinalLaugh, got rank 191, while he has got 200 rank when the submission parse finished, just by a finger's breadth. The path to Las Vegas is becoming more and more narrow, next time , we will fight for 50 contestants position.

The top 2 players' program scares me a lot...... So many codes that looks like "AA>s;oI2A". As we, FinalLaugh and I, discussed, it's a technology of compress.

I dislike this problem, two reasons: 1st, it's a gambling game; 2nd, it's solution is not so hard, but with a lot of work. My solution is so easy to implement , somewhat like saarixx (rank 7) did.

First of all, list all card combinations: {4,4} {3,3} ... 15 cases from high to low. Then, provide a simple solution to newcard(), round1(), draw() then take them into an array, each owns 15 elements, just like this:


 private int[] newc = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 };
private int[] rd1 = { 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 };
private int[] draw = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2 };



For these three method, I think, a fixed strategy will be ok. As to round2(), it's more complexity, but as I'm so lazy.... I realize it like this:


   public int round2(int card1, int card2, int bets1, int bets2, int drew) {
int idx = getCardIdx(card1, card2);

// pre solution, like the too little card will return 0 immediately

switch (drew) {
case 2:
// some solution
case 1:
// some solution
case 0:
// some solution
}
return -1;
}



That's all, so simple but strong enough to advance to the next round. Wish my good luck next round!

Friday, March 30, 2007

TCO Marathon Online Round #1

TCO Marathon OR1 and OR2 has finished today, which consume my thoughts for two weeks.

To OR1, I got 1309.01 at submission phase and 4990.66 at end, final rank 67/532. See the problem here(need login), which is a really interesting and challenge game. As my solution, the image could be considered as a onion, the target of this prob is to peel the onionskin. So, here is the steps of my algorithm:

1. Generate the rays, those rays will be the easy calculating ones. (Attention, generate rays does not mean call the measure() method.)
2. Pick out the rays that just cross one unit('x' unit), and store them in a queue.
3 Iterate the selected rays, calculate the density of that unit(call measure() here), and then mark the unit as calculated.
4 Repeat step 2, but the more repetition we used, the more precision we will lost. It should be a bound to control the precision before we start this algorithm.

As to step one, the rays should be selected meet the condition that they will be easy to calculate, otherwise, it will be a great amount work of calculation and simulation. As I considered, each ray will start from one of the four corners of the unit, and the ray should cross exactly n row unit while it crossed 1 col unit, and vice versa. The main reason I ensure this condition is that every length of the row unit( according to my example) that the ray would cross is the same, and that would lower the complexity of the ray calculation. As a result, when n is greater than 30(I forget the exactly number, but 30 is enough), every unit will be covered.

As to step four, the repetition times is a hard decision. The performs of different repetition times would result in a normal distribution, and the peak of the distribution is the one we desired. I choose the repetition according to a great amount of test.

Wednesday, March 14, 2007

《大唐西游记》 [探索·发现]

记录片《大唐西游记》,制作在国内算是十分精良的了。全力推荐!

音效出众!配音出色!
对《西游记》名著的动画表现,充满了活力!
而对历史的重现采用虚拟3D技术,虽然技术上还有不是十分完善。但足以用来描述好这段神奇的冒险故事了。

推荐!强力推荐!
喜欢记录片的朋友千万不要错过了!

Wednesday, March 07, 2007

解决系统盘空间不足

我的系统盘只有4G。虽然平时我已经很注意保持系统盘的清爽,但还是总免不了“磁盘空间不足”的麻烦。满惹人的,于是在网上搜搜有没有达人能给我一点好的idea。没想到确有高手,以下是该文的引用:


其中第7、8条真是杀手锏!把100M不到的空间释放到1G多,汗颜,原来有这么多垃圾没清理掉。
第9-12条是清除平时不用的windows文件的,有一点危险性,不过知道东东的含义就不怕啦。

13、14和27的bcd都是值得推荐的方法,算是比较温和的方法却能很大程度上改观当前系统盘的尴尬局面。

Thursday, March 01, 2007

Widget for Google Calendar

See my blog's left bar, there is a fantastic widget that shows my google calendars in the form of event list and calendar table.

Now, the widget is available here:
http://ray58750034.googlepages.com/googlecalendarwidget

Reply your comments, ideas and the bugs you find about the widget here, thx.

Friday, February 23, 2007

Graphics program with Javascript

Apple introduced a new HTML tag <canvas> to the world, which endue client-side script language the ability of graphics drawing. Now, Firefox and Opera has implement the <canvas> tag, so the javascript programmer was able to write a rich graphic-based client application.

I've written a simple ball game to show the interactive between javascript graphic app and browser user.

See details : http://ray58750034.googlepages.com/javascriptballgame
See more examples : http://developer.mozilla.org/en/docs/Category:Canvas_examples

Wednesday, February 21, 2007

Topcoder SRM340 DIV II

首先叹一下只能沦落在Div2和Div1的边缘。颇为伤感,以后想做Component了。

多么戏剧性的一场比赛啊,第一题还是很稳健的敲掉了,毕竟DIV2第一题太没搞头了。第二题其实也很简单,但比赛的时候,人就容易犯糊涂。 我把第二题先想成dfs,写完后发觉超时,郁闷。然后越想越复杂,想到了DP,DP的路就越走越远拉。最后是235.85收场。

第二题,其实枚举和贪心就行,巨汗呐。不过在Challenge阶段,表现神勇啊!一路从18冲进前10。主要是靠事前准备的对付第二题dfs的数据,哈哈,果然有用dfs还不知情的,连掐3个 ,HOHO。当时排名第10, score 385.85。

最后的System Test是关键!第三题全军覆没,房间里没人过。第二题就第一个人过了。然后,因为我掐了三个人,所以我的总积分排第二!巨汗啊,居然排到了No2,不枉我通宵比赛,呵呵。总结一下,第二题我其实TEST数据早过了,但由于我确定我的程序不完美,所以我一直不交。看来战术是正确的!如果交了被掐掉,那就很尴尬了。

按规则,这场比赛有奖金可以拿,多少无所谓,只要确实有拿就好。拿到钱得请梁大吃饭!梁大应该是说比我做的好,但是最后也是只有一题过了,再加上没掐,所以分数比我差。当然他们房间的整体实力可能还比我这强一点。

Saturday, February 17, 2007

HSB Color Space

java.awt.Color类有根据HSB色彩空间创建Color的静态方法,今天去查了查。了解了HSB是怎么一个色彩空间,它和RGB又有什么区别,分享一下。

下图的圆锥描述的就是HSB如何表示色彩,相当华丽吧:

Hue:描述色彩,其值为 [0,360) ,是圆锥顶部的圆,其0和360均为红色。另外60为黄、120为绿、180为青、240为兰、300为紫。颜色如彩虹~呵呵。

Saturation:描述饱和度,其值为[0,1]之间的小数,图中是圆锥的轴到圆锥的边缘。取0则是纯白,无论Hue取多少。

Brightness:描述明亮度,其值为[0,1]之间的小数,图中可以说是圆锥的高度,自底向上逐渐明亮。当取0时,色彩为纯黑,无论Hue和Saturation取何值。

参考:
http://www.tomjewett.com/colors/

IE 好龊

微软自家的东西都兼容这么差,IE居然不如Firefox识别能力强。 -_-b

Friday, February 16, 2007

Javascript Menu 代码

只为了显现一个简单的menu,网上搜了不少代码。 但要么就是太复杂,搞得我改都无从改,要么就是不符合我的需求。结果自己静下心 20分钟就搞定了, -_-b ,找了大概2小时啊,汗呐。

非常简单的要求:
  1. 必须是js代码,因为我要实现menu在很多页面里都要用,如果掺了html就要用iframe之类的,iframe毕竟不舒服啊。
  2. 对界面没什么要求,简单的ul和li就行了,css沿用站点的,无须另外配。
  3. 多级目录结构
  4. 每层menu可以是链接,也可以是打开子目录
  5. 可复用,其实就是实现类似jsp的<%@include file="">的作用,只是我没有服务器,所以只好用js啦。
先看效果:



以下是我的代码:

<div id="soya_menus">
</div>
<script language="JavaScript">

var MENU_ITEMS = [
['Ray',{ href : 'http://raythking.blogspot.com/',target : "_blank" }],
['Google',null,[
['Web',{ href : 'http://www.google.com',target : "_blank"}],
['Image',{ href : 'http://images.google.com',target : "_blank"}],
['Video',{ href : 'http://video.google.com',target : "_blank"}]
]
],
['Baidu', null,[
['Index',{ href : 'http://www.baidu.com/',target : "_blank"}],
['Zhidao',{ href : 'http://zhidao.baidu.com/',target : "_blank"}]
]
],
['Sogou',{ href : 'http://www.sogou.com/',target : "_blank"}],
['About',{ href : 'javascript:alert(" This is a simple javascript menu !")',target : "_self"}]
];


function showSubMenu( tolist ){
var sublist = document.getElementById(tolist);

if(sublist.style.display == ""){
sublist.style.display = "none";
}else{
sublist.style.display = "";
}
}

function insertMenu(divarea){
document.getElementById(divarea).innerHTML=createMenu(MENU_ITEMS,"soya_menu");
showSubMenu("soya_menu");
}

function createMenu(menu_it,id_pre){
var html="<ul id='"+id_pre+"' style='display:none;padding-top:8px' >";
for( var i=0 ; i<menu_it.length; ++i){
var sub_id_pre=id_pre+"m"+i;
html += "<li>";
if(menu_it[i][1]){
html += "<a href='"+menu_it[i][1]+"'>";
html += menu_it[i][0];
html += "</a>";
}else if(menu_it[i][2]){
html += "<a href='"+menu_it[i][1].href+"' target='"+menu_it[i][1].target+"'>";
html += menu_it[i][0];
html += "</a>";
html += createMenu(menu_it[i][2],sub_id_pre);
}else{
html += menu_it[i][0];
}

html += "</li>";
}
html +="</ul>";

return html;
}

insertMenu("soya_menus");

</script>

Wednesday, February 14, 2007

不同浏览器下装载js的不同表现

这两天在改blog,因为脑子里又掺了一些杂七杂八的念头,想要实现一下,呵呵。如果这两天有看我blog的话,可能时不时会发觉自动跳框啊或者某个功能怎么没了等等状况。那就是我在改blog,这个时候要找我的话,直接上gtalk就行啦。

为了实现多个浏览器下效果一致,花了不少心血啊。先看看效果吧,见左边的“日程更新”,我的Calendar是以event list形式表示,当然可以有其他选择,这是后话(有空时候再说吧)如果是Firefox的话可以看到边是带弧的,是用的css3,ie和opera下没看出来。ie下还有其他一些css效果也看不出来。不过基本的效果是三个都一样的。

因为涉及要下多个Calendar然后合并的操作,发觉三个浏览器对于js下载和加载的表现各不相同。在做Web可要特别注意了哦,在这我说一下我遇到的情况吧:

情况如下,首先要下载四个Calendar的数据(用Google 的 JSON API),每个下载完回调一个Handle,Handle将数据加入EventList。四个都Handle过了,调用showEventList()。三个浏览器的下载方式应该都是并发的,这点应该没有疑问。每一个Calendar的操作相当于是在一句<script src="****"></script>,加载顺序正好三种浏览器三种方式。


首先是IE,由于对多个Calendar操作,然后用到了一个eventlist,可以想象是多线程在操作一个数据域。IE可以说是完全多线程的,如果给Calendar编号 1 2 3 4,那么在下载完数据后回调的顺序可能是 2 3 1 4 或者 1 3 4 2 等等。另外,用来动态加载这些javascript的那段js与这四个新js也是并发的。这样有两点麻烦:
  1. 时间上难掌握:程序是非顺序的,对于需要顺序完成的任务实现时要加不少辅助变量。
  2. 空间上易出错:由于好几个Calendar的Handle是同一个Handle,这样就要手动控制好变量的同步,容易出现脏数据。

然后是Opera,Opera不论从哪方面讲都适合年轻人使用,充满了朝气!今天的修改其实主要是针对IE的,Firefox和Opera基本上是一致的。但在最后,Opera的一个反常举动让我调了老半天才调出来。
Opera的js装载好象是完全顺序,与IE截然相反。顺序到一个页面的所有script都得一步一步来,就像只有一个线程。如果以原script为 0,四个数据js文件还是 1 2 3 4,那么Opera的执行顺序将是 0 1 2 3 4 0,最后的0是返回原脚本,感觉就是堆栈式的函数调用。就是最后那个返回原脚本,让我措手不及。楞了老半天才发觉。


最后是Firefox,个人觉得,Firefox 更适合用来开发 web 程序。就在今天的修改过程中,无论我怎么改,只要基本的逻辑是对的,那么Firefox的效果始终是如预期的。
以Opera那种假设下来说,Firefox的执行顺序是 0 1 2 3 4。我觉得这样理解好了,Firefox是把script放在页面文件中。装载顺序是从头到尾依次装载的(严格按照js在页面中出现的顺序),js的运行不并发,装一个运行一个结束后再装。几个好处吧:
  1. 更贴近web开发者的正常逻辑。web开发者一般是写页面的时候嵌js,而不是写js的时候嵌页面 。这样Firefox显然比Opera更适合web开发者。
  2. 脚本并行处理(IE)考虑了一块js一个用途的方式时候的效率,但是不适合多个js联合工作,特别是需要时间上和空间上控制的工作。

其实单就用户体验来说,IE可能更受欢迎,毕竟是多线程的,不会因为一个js的错误而导致整个页面僵死。而且就三个浏览器看我blog的速度来说,IE应该是比较快的(除了Opera在有缓存的情况,其缓存给我的印象颇深刻~)。但我还是比较喜欢Firefox,毕竟咱是做“写”工作的人嘛,而且速度这个是可以用不同手段提高的。

最后赞一下Firebug,开发人员的福音啊!