Happy Coding

This blog is for my memorandum.

Happy Coding

This blog is for my memorandum

AtCoder Beginner Contest 010 D - 浮気予防

problem

D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder

how to solve

This problem can be reduced to the maximum matching problems. This means that Ford-Fulkerson is among the good way to solve this problem.We have to take care that this graph is undirected so we have to prepare two edges for solving flow problems. The following link is very helpful to understand.

http://hidollara.hatenablog.com/entry/2017/07/29/165951

code

#include <iostream>
#include <vector>
using namespace std;

#define INF (1<<15)

class Solver {
    private:
        int n, g, e;
        vector<vector<int> > adj; 
        vector<bool> visited;
    public:
        Solver(){
            cin >> n >> g >> e;
            adj = vector<vector<int> >(n + 1, vector<int>(n + 1, 0));
            for (int i = 0; i < g; ++i)
            {
                int mark;
                cin >> mark;
                adj[mark][n] = 1;
                // adj[n][mark] = 1;
            }
            for (int i = 0; i < e; ++i)
            {
                int a, b;
                cin >> a >> b;
                adj[a][b] = 1;
                adj[b][a] = 1;
            }
        }

        int dfs(int from, int goal, int min_cost) {
            if(from == goal) return min_cost;
            visited[from] = true;
            for (int to = 0; to < n + 1; ++to)
            {
                if(adj[from][to] == 0 || visited[to]) continue;
                int flow = dfs(to, goal, min(min_cost, adj[from][to]));
                if(flow != 0) {
                    adj[from][to] -= flow;
                    adj[to][from] += flow;
                    return flow;
                } 
            }
            return 0;
        }

        void exec(){
            int sum_flow = 0;
            while(true) {
                visited = vector<bool>(n + 1, false);
                int flow = dfs(0, n, INF);
                if(flow == 0) {
                    cout << sum_flow << endl;
                    return;
                }
                sum_flow += flow;
            }
        }
};


int main(){
    Solver s = Solver();
    s.exec();
}

Network Flow - Maximum Flow

problem

Maximum Flow | Aizu Online Judge

code

#include <iostream>
#include <vector>

#define INF (1<<15)

using namespace std;

struct edge{
    int to;
    int cap;
    int rev_id;
};

class FordFulkerson
{
private:
    vector<vector<edge> > adj;
    int v;
    int e;
    vector<bool> visited;
public:
    FordFulkerson() {
        cin >> v;
        cin >> e;
        adj.resize(v);
        for (int i = 0; i < e; ++i)
        {
            int u;
            int v;
            int c;
            cin >> u >> v >> c;
            adj[u].push_back((edge){v, c, adj[v].size()});
            adj[v].push_back((edge){u, 0, adj[u].size() - 1});
        }
    }


    int dfs(int from, int goal, int flow) {
        if(from == goal) return flow;
        visited[from] = true;
        for (int i = 0; i < adj[from].size(); ++i)
        {
            edge &e = adj[from][i];
            if(!visited[e.to] && e.cap > 0) {
                int d = dfs(e.to, goal, min(e.cap, flow));
                if(d > 0) {
                    adj[from][i].cap -= d;
                    adj[e.to][e.rev_id].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    void exec() {
        int flow_sum = 0;
        while(true) {
            visited = vector<bool>(v, false);
            int flow = dfs(0, v - 1, INF);
            if(flow == 0) {
                cout << flow_sum << endl;
                return;
            }
            flow_sum += flow;
        }
    }
};

int main() {
    FordFulkerson ff = FordFulkerson();
    ff.exec();
}

Family Guy season9 1-2 And Then There Were Fewer

Plot

One day, Peter who is a father like a kind of homer in Simpsons is invited to the party by an anonymous guest. Also other families in his town are invited to this. When the party is about to started, one of the guest is shooted by someone.

vocabulary list

word explanation example
let up 嵐がやむ before the storms lets up
skin(v) 動物の皮を剥ぐ
unconscious 無意識
hot chicks 魅力的な女性
gasp はっという
stay up 遅くまで起きる or どどまる
huddle up to gather or crowd together in a close mass
scrutinize examine or inspect closely and thoroughly.
nocturnal 夜行性の
intruder 侵入者
crawl はう、よつんばいになってはう
podunk A piece of shit, redneck, small-town
slippery difficult to hold firmly or stand on because it is smooth, wet, or slimy.つるつる、するする 追いかけてる人がなかなか捕まらない時とかにつかう
i’m managing なんとかやってるよ(how are you?とかの返し)
for the time being しばらくね
He dumped me 彼は私を振ったの
crumble 崩れる I watched my career and my love life crumble
seize にぎる つかまえる チャンスをつかんだ I seized the moment
seduce 誘惑する
reel him  つる 
pay her off 彼女に復讐する
instill 思い込ませる
hysterical ヒステリックに

CUDA まとめ

CUDAのメモリについて

  • グローバルメモリはGPU上どこからでも見えるがメモリアドレスが低速なメモリ

  • シェアードメモリは同一ブロックからしかみえないが高速に読み書きができるメモリ

  • コンスタントメモリは読み込み専用だがグラオーバルメモリと同様のスレッドから見える高速なメモリ。

CUDAの性能劣化をひきおこす特徴

warp divergence

実際のcudaスレッドの処理は連続したIDを持つ32スレッドを1グループ(ワープと呼ぶ)とし、ワープ単位で同一命令を実行するGPUの特徴により発生するオーバーヘッドである。同一ワープ内のスレッドが異なる命令を実行することをワープダイバージェンスと呼ぶ。

coalesed memory access

スレッドIDとアクセスするメモリアドレスが不連続な場合に負荷が発生する。特に連続したIDを持つスレッドが連続したメモリ番地へアクセスすることで、高速なデータ転送が実行できる。

Remove all ads

AtCoder Regular Contest 029 B 高橋君と禁断の書

問題

arc029.contest.atcoder.jp

解き方

二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指定回数分二分探索して見つからなかったら"NO"。

計算量

二分探索の繰り返し回数をkとすると O(kn)

code

xgboost memory problem

Memory is shortage in xgboost program

Sometimes, program is forcibly quit when using xgboost. In that time, there are several solutions(It is true that the solution is existed except for the following).

https://www.kaggle.com/c/grupo-bimbo-inventory-demand/discussion/22321

solution

AtCoder Beginner Contest 060 D - Simple Knapsack

Problem Statement

You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi.

You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1≤N≤100 1≤W≤109 1≤wi≤109 For each i=2,3,…,N, w1≤wi≤w1+3. 1≤vi≤107 W, each wi and vi are integers.

how to solve

We have to check the constraints. In this problem w and v is big, so we cannot solve this problem in common dynamic programming way. This time we use the constraint w1 ≤ wi ≤ w1 + 3. Because of this, there are at most 4 possible weights for a single item. So I can test the all case that is how many items I have to use per 4 weights. This time complexity is O(n4)

code is following