A Survey on Dialogue Systems:Recent Advances and New Frontiers

2018-01-15

generative

more proper, never appeared
Neural Responding Machine for Short-Text Conversation
A Neural Conversational Model

SSIST by-talk day3

2017-06-15

There is a idea appears in my mind… to attend a PHD program in ShanghaiTech

Malik and Girod … big bosses’ talk are always too big for me.

SSIST by-talk day2

2017-06-15

keynote talks
Yann Lecun and Harry Shum depict a grand road map of AI.
Speaking speed of Lecun is 3x faster than normal people. fail to take and understand most part of his talk. The talk focused on CNN related project.
keyword:
Mask R-CNN instance segmentation
ConvSeq2Seq for traslation
FAIR
memory network
stacked-augmented
neural turing network
differentiable memory
Harry Shum’s talk use XiaoIce as the example to depict the AI’s feature and MSRA’s work.

SSIST by-talk day1

2017-06-15

The first impression of ShanghaiTech University is different from other universities I’ve visited.

Cheetah mobile AI Lab
Speaker is a young man who quit UIUC PHD conducted by MaYi and made a startup evalued as almost 200 million yuan.

Finding similar articles

2017-04-15

Due to the demand of removing similar articles in Touchpal Dialer’s feeds, I did some research on related algorithms and realized a few of them.
I will tell about three of them in this article.

hdu 4456 crowd

2013-09-03

去年区域赛留下来的遗憾题之一。

此题要考的是坐标转换后的二维树状数组，难点在于内存开不下，需要20000**20000，现场赛胆大的直接开了这么大就过了，向我们这种胆小的就直接被吓傻了。

hdu上内存32768K。

由树状数组的性质可知每次最多只会更新log(n)次，因此二维树状数组总共会更新m log(n)log(n)个地方，所以想办法存这些值就可以了，map会超时，搞个靠谱点的hash就可以了。

CF 338E Optimize!

2013-08-18

题意：给一个串a,长度为n，一个串b长度为len, 问a有多少个长度为len的子串满足：和b任意匹配后，每一对值的和都大于等于h。

把b从大到小排序，对a里面的元素求出和b[i]相加大于等于h的最大的i , 这样b[1]~b[i]都满足和当前a里的元素相加大于等于h。
然后分别求出a中每一段长度为len的子串里：有多少要和b[1],b[2],……,b[len]之前匹配，记为c[i]，如果存在一个c[i] > i那显然这个子串无法满足了。
那么我们从左往右扫一遍，用线段树来维护，一开始每一个点先减去i,然后扫描中把c[i]加上去，如果线段树最大值比0大，那就表示这个串不满足。

//#pragma comment(linker, "/STACK:65536000")
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
#include<iostream>
#define max(x,y)(x>y?x:y)
#define min(x,y)(x<y?x:y)
#define ll long long
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;

const int inf = 1e9;
const int N = 200000;
int a[N],b[N];
int n,m,h;
int ma[4*N],add[4*N];

bool cmp(int a,int b){
    return a>b;
}

void pushdown(int x){
    add[x+x] += add[x];
    add[x+x+1] += add[x];
    add[x] = 0;
}
void pushup(int x){
    ma[x] = max(ma[x+x]+add[x+x],ma[x+x+1]+add[x+x+1]);
}

void insert(int x,int l,int r,int tl,int tr,int v){
    if(l>tr || r<tl) return ;
    if(l<=tl && r>=tr){
        add[x] += v;
        return ;
    }
    pushdown(x);
    int mid = (tr+tl)/2;

    insert(x*2,l,r,tl,mid,v);
    insert(x*2+1,l,r,mid+1,tr,v);

    pushup(x);
}
int main(){
//    freopen("/home/zyc/Documents/Code/cpp/in","r",stdin);
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=m;i++) scanf("%d",b+i);
    sort(b+1,b+m+1,cmp);
    for(int i=1;i<=n;i++){
        int tmp;
        scanf("%d",&tmp);
        int l = 1, r = m+1;
        while(r!=l){
            int mid = (l+r)>>1;
            if(b[mid] + tmp >=h) l = mid+1;
            else r = mid;
        }
        l--;
        a[i] = l;
    }
    for(int i=0;i<=m;i++) insert(1,i,i,0,m,-i);
    for(int i=1;i<=m;i++) insert(1,a[i],m,0,m,1);
    int ans = 0;
    for(int i=m;i<=n;i++){
        if((ma[1] + add[1])<=0) ans++;

        if(i!=n){
            insert(1,a[i-m+1],m,0,m,-1);
            insert(1,a[i+1],m,0,m,1);
        }
    }
    printf("%d\n",ans);
    return 0;
}

两题类似的数位DP

2013-08-17

CF 331C3 - The Great Julya Calendar (60 points)
SGU 390 TICKETS
dfs写法的数位dp最牛的地方是:只要考虑状态怎么变，边界情况搞搞好然后就能AC。
这两题都是一段区间会对下一段区间有影响的数位DP，这个影响就用pair来记录，其他无脑写。

HDU 4684 The Budget of Traveler

2013-08-17

题意：在树上做斜率优化（题意是不是太浓缩了= =）
以前感觉毫无想法，必须写下blog加深印象。
dp[i] = dp[j] + (sum[i]-sum[j])p[i] + r[i]; 转移方程，其中j是i的祖先。
斜率优化要维护队头和队尾，在树上怎么搞呢？把树链想成队列，开个fa[]数组记录在每个节点在队列里的前一个元素，更新队尾只要把当前节点的fa设为设为相应的值，更新队头没有办法删除，只能采用三分得到实际应当成为队头的地方，正确性可以根据斜率优化的性质知道，队头不删，那队列中的g()值，也就是状态转移方程的值是先减后增的。
队尾维护时一个个父亲更新过去，最坏情况每个节点都要o(n)，因此也要三分，正确性也可以由斜率优化性质得到。（做完这题，又得重学斜率优化了）。
三分找第k个父亲采用树上倍增，所以总的复杂度是o(nlog(n)*log(n))

#pragma comment(linker, "/STACK:65536000")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define INC(x,y) {x+=y;if(x>=mod) x-=mod;}
#define Max(x,y) {if(y>x) x=y;}
#define Min(x,y) {if(y<x) x=y;}
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;

const int N = 500000;
const ll inf = 1e18;
int n;
ll f[N],p[N],r[N],sum[N],num[N],dp[N];
int fa[N][20];
vector<int> e[N];


ll f1(int k,int j) {
    return dp[j] - dp[k];
}
ll f2(int k,int j) {
    return sum[j] - sum[k];
}
ll g(int i,int j) {
    return dp[j] + (sum[i]-sum[j])*p[i] + r[i];
}

int find(int u,int k){
    int c = 0;
    while(k){
        if(k&1) u =  fa[u][c];
        k>>=1;
        c++;
    }
    return u;
}
void getMax(int u,int father){
    int left = 0,right = num[father]-1;
    while(left<right){
        int mid = (left+right)/2;
        int fa0 = find(father,mid);
        int fa1 = fa[fa0][0];

        if(g(u,fa0)>g(u,fa1)) left = mid+1;
        else right = mid;
    }
    dp[u] = g(u,find(father,left));
}
int getFa(int u,int father){
    int left = 0,right = num[father]-1;
    while(left<right){
        int mid = (left+right)/2;
        int f = find(father,mid);
        int ff = fa[f][0];
        if((double)f1(ff,f)*f2(f,u)>=(double)f1(f,u)*f2(ff,f)) left = mid+1;
        else right = mid;
    }
    return find(father,left);
}

void dfs(int u,int father){
    getMax(u,father);
    int tf = getFa(u,father);
    fa[u][0] = tf;
    num[u] = num[tf]+1;
    for(int i=1;(1<<i)<=num[u]-1;i++)
        fa[u][i] = find(tf,(1<<i)-1);

    for(int i=0;i<e[u].size();i++){
        int v = e[u][i];
        if(v==father) continue;
        sum[v] = sum[u] + f[v];
        dfs(v,u);
    }
}
int main(){
//    freopen("/home/zyc/Documents/Code/cpp/in","r",stdin);
    int T,cas=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            e[i].clear();
            scanf("%I64d%I64d%I64d",&f[i],&p[i],&r[i]);
//            scanf("%lld%lld%lld",&f[i],&p[i],&r[i]);
        }
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        num[0] = 1;
        sum[1] = f[1];
        dfs(1,0);
        ll ans = 0;
        for(int i=2;i<=n;i++){
            ans += dp[i];
        }
        printf("Case #%d: %I64d\n",++cas,ans);
//        printf("Case #%d: %lld\n",++cas,ans);
    }
    return 0;
}

SRM 475 DIV1 900

2013-08-12

题意：
一场考试。一些题目结果已经出来，对于j题每个人能知道自己是否做对，做对得到points[j]分，做错0分。
令一些结果还未出来的题目，对于j题知道每个人是否提交，提交了就有机会得到points[j]分，否则必然的到0分。
然后对于成绩排在前p的人中（分数相同按照id，id小的排前面），随机选择q个，问方案数。

_LT_zyc

generative