0w1

CFR Gym FB Hacker Cup Qualification Round

http://codeforces.com/gym/100869
pA. Quite trivial, just take combination of distances.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const double EPS = 1e-8;

vector<pii> star;

double sqr(double k){ return k * k; }
double dis(int a, int b){
    return sqr( star[a].first - star[b].first ) + 
           sqr( star[a].second - star[b].second );
}

int dcmp(double k){
    if( fabs( k ) < EPS ) return 0;
    return k < 0 ? -1 : 1;
}

int Cs2(int s){ // C( s, 2 )
    return s * ( s - 1 ) / 2;
}
int solve(){ // assuming no points have the same ( x, y ) ?
    int cnt = 0;
    for(int i = 0; i < star.size(); ++i){
        vector<double> dist;
        for(int j = 0; j < star.size(); ++j) if( i != j )
            dist.push_back( dis( i, j ) );
        sort( dist.begin(), dist.end() );
        double ld = -1e8; int same_cnt = 0;
        for(int j = 0; j < dist.size(); ++j){
            if( dcmp( dist[j] - ld ) == 0 ){
                ++same_cnt;
                continue;
            }
            cnt += Cs2( same_cnt );
            same_cnt = 1;
            ld = dist[j];
        }
        cnt += Cs2( same_cnt );
    }
    return cnt;
}

int main(){
    int T; scanf("%d", &T);
    int kase = 0;
    while( T-- ){
        star.clear();
        int n; scanf("%d", &n);
        for(int i = 0; i < n; ++i){
            int x, y; scanf("%d %d", &x, &y);
            star.push_back( pii( x, y ) );
        }
        printf("Case #%d: %d\n", ++kase, solve());
    }
    return 0;
}

pB. Count how many shortcuts could be made i.e. first row: x.x, second row: ..., we will be able to save cost for the first row if we put one guard on the middle of the second row. That will be the only way to reduce guards and otherwise it will be the count of consecutive segments in each row.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;

char G[2][MAXN];
int mark[MAXN], mark2[MAXN];

int main(){
    int T; scanf("%d", &T);
    for(int kase = 1; kase <= T; ++kase){
        int n; scanf("%d", &n);
        for(int i = 0; i < 2; ++i)       
            scanf("%s", G[i]);
        int p = 0, ans = 0;
        while( p < n ){
            if( G[0][p] == 'X' ){
                ++p;
                continue;
            }
            if( p == 0 || G[0][p - 1] == 'X' ){
                if( p == n - 1 || G[0][p + 1] == 'X' ){
                    if( G[1][p] == '.' && mark[p] != kase ){
                        mark2[p] = kase;
                        for(int k = p; k >= 0; --k){
                            if( G[1][k] == '.' ) mark[k] = kase;
                            else break;
                        }
                        for(int k = p + 1; k < n; ++k){
                            if( G[1][k] == '.' ) mark[k] = kase;
                            else break;
                        }
                        ++p;
                        continue;
                    }
                }
            }
            while( p + 1 < n && G[0][p + 1] == '.' ) ++p;
            ++p, ++ans;
        }
        for(p = 0; p < n; ){
            if( G[1][p] == 'X' ){
                ++p;
                continue;
            }
            if( p == 0 || G[1][p - 1] == 'X' ){
                if( p == n - 1 || G[1][p + 1] == 'X' ){
                    if( G[0][p] == '.' && mark2[p] != kase ){
                        for(int k = p; k >= 0; --k){
                            if( G[0][k] == '.' ) mark2[k] = kase;
                            else break;
                        }
                        for(int k = p + 1; k < n; ++k){
                            if( G[0][k] == '.' ) mark2[k] = kase;
                            else break;
                        }
                        // printf("%d\n", p);
                        ++p;
                        continue;
                    }
                }
            }
            while( p + 1 < n && G[1][p + 1] == '.' ) ++p;
            ++p, ++ans;
        }
        printf("Case #%d: %d\n", kase, ans);
    }
    return 0;
}

pC. 尺取りだけ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;

int n, p;
int box[MAXN];

ll solve(){
    int lb = 0;
    ll cnt = 0LL, sum = 0LL;
    for(int rb = 0; rb < n; ++rb){
        sum += box[rb];
        while( sum > p ) sum -= box[lb++];
        cnt += rb - lb + 1;
    }
    return cnt;
}

int main(){
    int T; scanf("%d", &T);
    int kase = 0;
    while( T-- ){
        scanf("%d %d", &n, &p);
        for(int i = 0; i < n; ++i)
            scanf("%d", &box[i]);
        printf("Case #%d: %lld\n", ++kase, solve());
    }
    return 0;
}

pD. I was not able to solve this problem myself, I had to read the editorial, which really helped. The key is to realize that the optimal method is to print the words lexicographically, and to make use of the property that after strings are sorted lexicographically, lcp{ string i .. j } = min{ lcp( string( i, i + 1 ), string( i + 1, i + 2 ) .., string( j - 1, j ) }. This will speed up the transition for dynamic programming.
dp[ p ][ c ]: minimum cost to print c words, where the last word is the p'th string
dp[ p ][ 1 ] = s[ i ].length() + 1
dp[ p ][ c ] = min{ dp[ q ][ c - 1 ] + ( s[ q ].size() - lcp( p, q ) ) + ( s[ p ].size() - lcp( p, q ) ) + 1 } Ɐ s[ q ] < s[ p ]

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int MAXN = 300 + 2;
const int MAXK = 300 + 2;
const int MAXS = 1e5 + 2;

int n, k;
string s[MAXN];
int lcp[MAXN];
int memo[MAXN][MAXK];

void build_lcp(){
    for(int i = 0; i + 1 < n; ++i){
        lcp[i] = 0;
        for(int j = 0; j < s[i].size(); ++j){
            if( s[i][j] == s[i + 1][j] ) ++lcp[i];
            else break;
        }
    }
}

int kase;
int vis[MAXN][MAXK];
int dp(int p, int c){
    if( c > p + 1 ) return INF;
    if( c == 1 ) return s[p].size() + 1;
    if( vis[p][c] == kase ) return memo[p][c];
    vis[p][c] = kase;
    int g = INF;
    memo[p][c] = INF;
    for(int i = p - 1; i >= 0; --i){
        g = min( g, lcp[i] );
        int v = dp( i, c - 1 ) + s[i].size() - g + s[p].size() - g + 1;
        memo[p][c] = min( memo[p][c], v );
    }
    return memo[p][c];
}

int main(){
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for(kase = 1; kase <= T; ++kase){
        cin >> n >> k;
        for(int i = 0; i < n; ++i)
            cin >> s[i];
        sort( s, s + n );
        
        build_lcp();

        int ans = INF;
        for(int i = 0; i < n; ++i){
            ans = min( ans, dp( i, k ) + (int)s[i].size() );
        }

        cout << "Case #" << kase << ": " << ans << endl;
    }
    return 0;
}