USACO 2013 November Contest, Gold Problem 3. No Change

http://usaco.org/index.php?page=viewproblem2&cpid=348

Tips : 位元dp + binary search

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX_N = 1e5 + 6;
const int MAX_K = 21;

int a[MAX_N];
int p[MAX_K];
int pre[MAX_N];
int dp[(1<<MAX_K)];
int n,k;

int f(int s,int p) {
    if (s>n) return n;
//    cout<<"s = "<<s<<" , p = "<<p;
    int L=s-1,R=n+1;
    while (R-L!=1) {
        int mid=(L+R)>>1;
        if (pre[mid] - pre[s-1] <= p) L=mid;
        else R=mid;
    }
//    cout<<" ret = "<<L<<endl;
    //L is the answer
    return L;
}

int main () {
    if (fopen("nochange.in","r")) {
        freopen("nochange.in","r",stdin);
        freopen("nochange.out","w",stdout);
    }
    while (scanf("%d %d",&k,&n) != EOF) {
        memset(dp,0,sizeof(dp));
        for (int x=0;k>x;x++) {
            scanf("%d",&p[x]);
        }
        for (int x=1;n>=x;x++) {
            scanf("%d",&a[x]);
            pre[x] = pre[x-1] + a[x];
        }
        for (int x=1;(1<<k)>x;x++) {
            for (int y=0;k>y;y++) {
                if ((x&(1<<y))!=0) {
                    dp[x] = max(f(dp[x^(1<<y)]+1,p[y]),dp[x]);
                }
            }
//            cout<<"dp[" << x<<"] = " <<dp[x]<<endl;
        }
        int ans=-1;
        for (int x=0;(1<<k)>x;x++) {
            if (dp[x] >= n) {
                int tmp=0;
                for (int y=0;k>y;y++) {
                    if ((x&(1<<y)) == 0) {
                        tmp+=p[y];
                    }
                }
                ans = max(ans,tmp);
            }
        }
        printf("%d\n",ans);
    }
}

USACO 2013 November Contest, Gold Problem 1. Empty Stalls

http://usaco.org/index.php?page=viewproblem2&cpid=346

Tips : something like union-find tree

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX_N = 3e6 + 6;

struct DisjointSet {
    int p[MAX_N];
    void init(int n) {
        for (int x=0;n>=x;x++) p[x] = x;
    }
    int Find(int x) {
        return p[x]==x?x:p[x]=Find(p[x]);
    }
    void Union(int x,int y) {
        p[Find(x)]=Find(y);
    }
} djs;

int nxt[MAX_N];

void go(int x,int n) {
    nxt[djs.Find(x)]=(nxt[djs.Find((nxt[djs.Find(x)]+1)%n)]);    
    djs.Union(djs.Find(x),(nxt[djs.Find(x)])%n);
}

void pp(int n) {
    for (int x=0;n>x;x++) cout<<nxt[djs.Find(x)]<<' ';
    cout<<endl;
}

int main () {
    if (fopen("empty.in","r")) {
        freopen("empty.in","r",stdin);
        freopen("empty.out","w",stdout);
    }
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF) {
        djs.init(n);
        for (int x=0;n>x;x++) {
            nxt[x] = x;
        }
        for (int x=0;k>x;x++) {
            long long int a,b,c,d;
            scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
            for (int i=0;a>i;i++) {
                for (int j=1;b>=j;j++) {
//                    cout<<"put at "<<(c*j+d)%n<<endl;
                    go((c*j+d)%n,n);
//                    pp(n);
                }
            }
        }
        printf("%d\n",nxt[djs.Find(0)]);
    }
}

USACO 2013 November Contest, Silver Problem 3. Pogo-Cow

http://www.usaco.org/index.php?page=viewproblem2&cpid=345

Main idea : DP

note that Bessie can jump to the positive infinite or negative infinite

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <utility>
#include <algorithm>
#include <cassert>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int MAX_N = 1006;
const LL INF = 1e17 + 6;
const int oo = 1e9 + 7;

LL dp[MAX_N][MAX_N];
LL mx[MAX_N][MAX_N];
pii a[MAX_N];

LL dis(LL i,LL j) {
 if (i<1) return INF;
 return a[j].first - a[i].first;
}

int main () {
 if (fopen("pogocow.in","r")) {
     freopen("pogocow.in","r",stdin);
     freopen("pogocow.out","w",stdout);
    }
 int n;
 while (scanf("%d",&n) != EOF) {
     for (int x=0;n>=x;x++) {
         for (int y=0;n>=y;y++) {
             dp[x][y] = -INF;
             mx[x][y] = -INF;
            }
        }
     for (int x=1;n>=x;x++) {
         int i,j;
         scanf("%d %d",&i,&j);
         a[x] = make_pair(i,j);
        }
     sort(a+1,a+n+1);
     for (int x=1;n>=x;x++) {
         dp[x][0] = a[x].second;
         mx[x][0] = a[x].second;
        }
     for (int i=1;n>=i;i++) {
         for (int j=1;n>=j;j++) {
             if (i-j<1) break;
             int t=i-j;
             int L=-1,R=n+1;
             while (R-L != 1) {
                 int mid=(L+R)>>1;
                 if (dis(t-mid,t) <= dis(t,i)) L=mid;
                 else R=mid;
                }
//             cout<<"i = "<<i<<" , j=  "<<j<<" , L = "<<L<<endl;
             assert(L!=-1);
             if (L==-1) dp[i][j] = -INF;
             else dp[i][j] = mx[t][L] + a[i].second;
            }
         mx[i][0] = dp[i][0];
         int t=0;
         for (int j=1;n>=j;j++) {
             if (dp[i][j] == -INF) {
//                 mx[i][j] = mx[i][t];
                 continue;
                }
             mx[i][j] = max(dp[i][j] , mx[i][t]);
             t=j;
            }
        }
//     cout<<"Mx :\n";
//     for (int i=0;n>=i;i++) {
//         for (int j=0;n>=j;j++) {
//             cout<<(mx[i][j] == -INF?-1:mx[i][j])<<' ';
//            }
//         cout<<endl;
//        }
//     cout<<endl;
     LL ans=-INF;
     for (int i=0;n>=i;i++) {
         for (int j=0;n>=j;j++) {
//             cout<<(dp[i][j] == -INF?-1:dp[i][j])<<' ';
             ans = max(ans,dp[i][j]);
            }
//         cout<<endl;
        }
        //above is 順時針
        //下面��逆時針
     for (int x=0;n>=x;x++) {
         for (int y=0;n>=y;y++) {
             dp[x][y] = -INF;
             mx[x][y] = -INF;
            }
        }
     for (int x=1;n>=x;x++) {
         int i,j;
//         scanf("%d %d",&i,&j);
         a[x] = make_pair(-a[x].first+oo,a[x].second);
        }
     sort(a+1,a+n+1);
     for (int x=1;n>=x;x++) {
         dp[x][0] = a[x].second;
         mx[x][0] = a[x].second;
        }
     for (int i=1;n>=i;i++) {
         for (int j=1;n>=j;j++) {
             if (i-j<1) break;
             int t=i-j;
             int L=-1,R=n+1;
             while (R-L != 1) {
                 int mid=(L+R)>>1;
                 if (dis(t-mid,t) <= dis(t,i)) L=mid;
                 else R=mid;
                }
//             cout<<"i = "<<i<<" , j=  "<<j<<" , L = "<<L<<endl;
             assert(L!=-1);
             if (L==-1) dp[i][j] = -INF;
             else dp[i][j] = mx[t][L] + a[i].second;
            }
         mx[i][0] = dp[i][0];
         int t=0;
         for (int j=1;n>=j;j++) {
             if (dp[i][j] == -INF) {
//                 mx[i][j] = mx[i][t];
                 continue;
                }
             mx[i][j] = max(dp[i][j] , mx[i][t]);
             t=j;
            }
        }
//     cout<<"Mx :\n";
//     for (int i=0;n>=i;i++) {
//         for (int j=0;n>=j;j++) {
//             cout<<(mx[i][j] == -INF?-1:mx[i][j])<<' ';
//            }
//         cout<<endl;
//        }
//     cout<<endl;
//     ans=-INF;
     for (int i=0;n>=i;i++) {
         for (int j=0;n>=j;j++) {
//             cout<<(dp[i][j] == -INF?-1:dp[i][j])<<' ';
             ans = max(ans,dp[i][j]);
            }
//         cout<<endl;
        }
     printf("%lld\n",ans);
    }
}

USACO 2013 November Contest, Silver Problem 1. Farmer John has no Large Brown Cow

http://www.usaco.org/index.php?page=viewproblem2&cpid=343

Tips : binary Search

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

typedef long long LL;
const int MAX_N = 106;
const int MAX_K = 26;

struct P {
 int n;
 int id;
 string a[MAX_K];
} p[MAX_N],ans;

bool operator<(const P &p1,const P &p2) {
// assert(p1.n == p2.n);
 int n=p1.n;
 for(int x=0;n>x;x++) {
     if (p1.a[x] < p2.a[x]) return true;
     else if (p1.a[x] > p2.a[x]) return false;
    }
 return false;
}

vector<string> mp[MAX_N];

int main () {
 if (fopen("nocow.in","r")) {
     freopen("nocow.in","r",stdin);
     freopen("nocow.out","w",stdout);
    }
 int n,k;
 while (scanf("%d %d",&n,&k) != EOF) {
     string s;
     int m;
     getchar();
     for (int x=0;n>x;x++) {
         getline(cin,s);
         int sz=s.size();
         string i="";
         int cnt=0;
         for (int y=19;sz-4>y;y++) {
             if (s[y] == ' ') {
//                 cout<<"get "<<i<<endl;
                 mp[cnt].push_back(i);
                 p[x].a[cnt++]=i;
                 i="";
                }
             else {
                 i+= " ";
                 i[i.size()-1]=s[y];
                }
            }
         p[x].n=cnt;
         m=cnt;
        }
     LL tot=1;
     string INF = " ";
     INF[0] = 'z'+1;
     for (int x=0;m>x;x++) {
         mp[x].push_back("A");
         mp[x].push_back(INF);
         sort(mp[x].begin(),mp[x].end());
         mp[x].resize(unique(mp[x].begin(),mp[x].end()) - mp[x].begin());
         tot *= (mp[x].size() - 2);
//         for (int y=1;mp[x].size()-2>=y;y++) cout<<mp[x][y]<<' ';
//         cout<<endl;
        }
     sort(p,p+n);
     p[n].a[0] = "}";
     p[n].id = n+1;
     for (int x=0;n>x;x++) {
         p[x].id = x+1;
        }
     ans.n=m;
     for (int x=0;m>x;x++) {
         ans.a[x] = INF;
        }
     LL ss=0;
     for (int x=0;m>x;x++) {

         tot/=(mp[x].size()-2);
//         cout<<"tot = "<<tot<<endl;
//         cout<<"ss = "<<ss<<endl;
         int L=0,R=mp[x].size()-1;
         while (R-L!=1) {
             int mid=(L+R)>>1;
             ans.a[x] = mp[x][mid];
//             cout<<"mid = "<<mid<<endl;
             P tmp=*lower_bound(p,p+n,ans);
             int delta=1;
             if (!(tmp<ans) && ! (ans<tmp) ) delta = 0;
//             cout<<"val = "<<ss + (mid)*tot - (tmp).id + delta<<endl;
             if (ss + (mid)*tot - (tmp).id + delta>= k) R=mid;
             else L=mid;
            }
         ss += (R-1)*tot;
         ans.a[x] = mp[x][R];
        }
     for (int x=0;m>x;x++) {
         if (x!=0) cout<<' ';
         cout<<ans.a[x];
        }
     cout<<endl;
    }
}

USACO 2014 US Open, Silver Problem 1. Fair Photography

http://www.usaco.org/index.php?page=viewproblem2&cpid=433

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e5 + 6;
const int INF = 1e9 + 7;

pii a[MAX_N];
int pre[MAX_N];
int mx[2*MAX_N];

int main () {
    if (fopen("fairphoto.in","r")) {
        freopen("fairphoto.in","r",stdin);
        freopen("fairphoto.out","w",stdout);
    }
    int n;
    while (scanf("%d",&n) != EOF) {
        memset(pre,0,sizeof(pre));
        fill(mx,mx+2*MAX_N,-INF);
        for (int x=1;n>=x;x++) {
            int i;
            char c;
            scanf("%d %c",&i,&c);
            a[x] = make_pair(i,c=='W'?1:-1);
        }
        sort(a+1,a+n+1);
        for (int x=1;n>=x;x++) {
            pre[x] = pre[x-1] + a[x].second;
            mx[pre[x]+MAX_N] = x;
        }
        for (int x=2*MAX_N-2;x>=0;x--) {
            mx[x] = max(mx[x],mx[x+1]);
        }
        int ans=-INF;
        for (int x=1;n>=x;x++) {
            int s = -a[x].second + pre[x];
            if (x==1) s=-a[x].second;
            s += MAX_N;
            int t=mx[s];
//            cout<<"x = "<<x<<" , s= "<<s<<" , t ="<<t<<endl;
            if (t==-INF) continue;
            if ((t-x)%2==0) t--;
            ans = max(ans,a[t].first-a[x].first);
        }
        printf("%d\n",ans);
    }
}

USACO 2013 November Contest, Silver Problem 2. Crowded Cows (Copy on Write 線段樹模板)

http://www.usaco.org/index.php?page=viewproblem2&cpid=344

要用copy on write 線段樹支援！！！

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <assert.h>
using namespace std;

struct Node {
    Node* lc;
    Node* rc;
    int val;
    Node() {
        lc=rc=NULL;
        val=-1;
    }
    void pull() {
        if (lc==NULL && rc==NULL) val=-1;
        else if (lc==NULL && rc!=NULL) val=rc->val;
        else if (lc!=NULL && rc==NULL) val=lc->val;
        else if (lc!=NULL && rc!=NULL) val=max(rc->val,lc->val);
    }
};

void modify(Node* node,int L,int R,int pos,int val) {  //similar to build
    if (L==R) {
        assert(L==pos);
        node->val=val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) {
        if (node->lc==NULL) {
            Node* tmp = new Node();
            node->lc=tmp;
        }
        modify(node->lc,L,mid,pos,val);
    }
    else if (pos>mid) {
        if (node->rc==NULL) {
            Node* tmp = new Node();
            node->rc=tmp;
        }
        modify(node->rc,mid+1,R,pos,val);
    }
    node->pull();
}

int query(Node* node,int L,int R,int l,int r) {
    if (L>r||l>R) return -1;
    else if (l<=L && R<=r) return node->val;
//    else if (L==R) return node->val;
    int mid=(L+R)>>1;
    int q1=-1;
    if (node->lc==NULL) q1=-1;
    else q1=query(node->lc,L,mid,l,r);
    int q2=-1;
    if (node->rc==NULL) q2=-1;
    else q2=query(node->rc,mid+1,R,l,r);
//    cout<<"return "<<max(q1,q2)<<endl;
    return max(q1,q2);
}

const int MAX_N = 50002;
const int MAX_H = 1000000005;

int x[MAX_N], h[MAX_N];

int main () {
    freopen("crowded.in","r",stdin);
    freopen("crowded.out","w",stdout);
    int n,d;
    while (scanf("%d %d",&n,&d) != EOF) {
        Node* root = new Node();
        for (int i=0;n>i;i++) {
            scanf("%d %d",&x[i],&h[i]);
            modify(root,1,MAX_H,x[i],h[i]);
        }
        int ans=0;
        //start query
        for (int i=0;n>i;i++) {
            //left side
            int anss=0;
            if (x[i]!=1) {
                int L=(x[i]-d),R=x[i]-1;
                if (L<=1) L=1;
                int tmp=query(root,1,MAX_H,L,R);
                if (tmp>=2*h[i]) {
                    anss++;
                }
            }
            if (x[i]!=MAX_H) {
                int L=(x[i]+1),R=x[i]+d;
                if (R>=MAX_H) R=MAX_H;
                int tmp=query(root,1,MAX_H,L,R);
                if (tmp>=2*h[i]) {
                    anss++;
                }
            }
            if (anss==2) ans++;
        }
        printf("%d\n",ans);
//        for (int x=1;20>=x;x++) cout << x << " = " << query(root,1,MAX_H,x,20)<<endl;
    }
}