Topcoder - подключение плагина moj

Для того чтобы упростить себе жизнь в соревнованиях топкодер существует различные плагины.
Рассматриваемые в этом посте плагин moj умеет следующее:

• генерировать скелет решения (класс и метод) и сохранять его в указанное место
• включить в сгенерированный скелет необходимый prewritten код
• генерировать по сэмплам из условия задачи код, необходимый для тестирования

1. Для начала качаем архив с необходимыми файлами по ссылке
2. После этого заходим в арену, выбираем Options->Editor->Add. В появившемся диалоге указываем:

• Name: CodeProcessor
• EntryPoint: codeprocessor.EntryPoint
• ClassPath: нажимаем browse и выбираем все jar файлы из скаченного архива (moj.jar, CodeProcessor.jar, FileEdit.jar)

3. Нажимаем Configure и в поле Editor Entry Point пишем fileedit.EntryPoint и ниже добавляем строчку с содержимым moj.moj.
4. Снова нажимаем Configure для того чтобы задать настройки плагина. Здесь необходимо указать имя директории куда будут сохраняться сгенерированные файлы. Кроме того рекомендуется снять галочку Backup existing file then overwrite. Наконец, нужно вставить код шаблона для используемого языка программирования. Так, для C++ он может выглядеть следующим образом:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <sstream> #include <cmath> #include <string> #include <string.h> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <algorithm> #include <cassert> using namespace std; #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define sz(x) ((int)((x).size())) #define rep(i, N) for (int i = 0; i < N; ++i) #define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it) typedef long long lint; typedef vector<string> vs; typedef vector<int> vi; typedef pair<int, int> pii; class $CLASSNAME$ { public: $RC$ $METHODNAME$( $METHODPARMS$ ) { } }; $BEGINCUT$ $TESTCODE$ $DEFAULTMAIN$ $ENDCUT$

Useful CouchDB tips

curl

HOST="http://127.0.0.1:5984"

1. Create database:

curl -u admin:admin -X PUT $HOST/db

{"ok":true}

2. Delete database

curl -u admin:admin -X DELETE $HOST/db

{"ok":true}

3. Create document

curl -X PUT $HOST/db/foo -d '{"count":1}'

{"ok":true,"id":"foo","rev":"1-74620ecf527d29daaab9c2b465fbce66"}

4. Update document

curl -X PUT $HOST/db-replica/foo -d '{"count":2, "_rev":"1-74620ecf527d29daaab9c2b465fbce66"}'


{"ok":true,"id":"foo","rev":"2-de0ea16f8621cbac506d23a0fbbde08a"}

5. Replication

curl -u admin:admin -H "Content-Type:application/json" -X POST $HOST/_replicate -d '{"source":"db", "target":"http://127.0.0.1:5984/db-replica"}'

{"ok":true,"session_id":"48d43591b4f145ae08a9207dcc586fe2","source_last_seq":1,"replication_id_version":3,"history":[{"session_id":"48d43591b4f145ae08a9207dcc586fe2","start_time":"Wed, 15 Jan 2014 09:59:42 GMT","end_time":"Wed, 15 Jan 2014 09:59:42 GMT","start_last_seq":0,"end_last_seq":1,"recorded_seq":1,"missing_checked":1,"missing_found":1,"docs_read":1,"docs_written":1,"doc_write_failures":0}]}

6. Changes

curl $HOST/_changes?feed=longpoll&heartbeat=300000&style=all_docs&since=233

Views

1. View conflicts

function(doc) {
  if(doc._conflicts) {
    emit(doc._conflicts, null);
  }
}

Java: преобразование объектов в строковый тип и обратно

toString()
Каждый java объект может быть преобразован в String с помощью базового метода объекта toString. Также у классов оберток имеется статическая версия этого метода.
Примеры:

String s = BigInteger.ZERO.toString();
String s = Double.toString(0.4);
String s = Integer.toString(255, 16); // 0xff

valueOf()
Метод valueOf является статическим методом класса и используется для того чтобы получить инстанцию данного класса по строке или по значению некоторого примитивного типа.
Примеры:

Integer xx = Integer.valueOf("34", 10);
String s = String.valueOf(true);
BigInteger b = BigInteger.valueOf(34L);
BigDecimal b = BigDecimal.valueOf(345.0);

parse()
Кроме того, классы обертки умеют инициализировать свои примитивы по значению строки. Для этого существует набор методов parseInt, parseDouble и т.д.
Примеры:

int x = Integer.parseInt("ff", 16);   // 255
double d = Double.parseDouble("0.34");

Использование сторонних библиотек с MCR в objective c

Возникла интересная ситуация при использовании проекта Jastor для преобразования NSDictionary в кастомный обект. Проект не использует acr, но я решил перевести его на acr (удалив при этом все release,retain,autorealese), чего делать было нельзя. Проблема была с методом:

static const char *property_getTypeName(objc_property_t property) 

Конкретно в методе создавался NSData и возвращалось свойство bytes этого объекта. При этом в месте вызова появлялись некорректные данные.

Вообщем вывод такой, лучше стороние библиотеки, которые не используют автоматический подсчет ссылок, использовать в том же режиме (ручной подсчет ссылок), с соответствующим флагом компиляции.

SRM 534

Div2 - 250 EllysDirectoryListing

public class EllysDirectoryListing {
    public String[] getFiles(String[] files) {
        int n = files.length;
        if (check(files)) return files;
        int p = getPos(files);
        swap(files, p, n - 1);
        if (check(files)) return files;
        p = getPos(files);
        swap(files, p, n - 2);
        return files;
     }

    boolean check(String files[]) {
        int n = files.length;
        if (files[n - 1].equals(".") && files[n - 2].equals("..")) return true;
        if (files[n - 2].equals(".") && files[n - 1].equals("..")) return true;
        return false;
    }
    int getPos(String files[]) {
        for (int i = 0; i < files.length; ++i) {
            if (files[i].equals(".")) return i;
            if (files[i].equals("..")) return i;
        }
        return -1;
    }
    void swap(String f[], int i, int j) {
        String tmp = f[i];
        f[i] = f[j];
        f[j] = tmp;
    }

}

Div2 - 500, Div1 - 250 EllysCheckers

public class EllysCheckers {
    public String getWinner(String board) {        
        int use = 0;
        N = board.length();
        for (int i = 0; i + 1 < N; ++i) {
            if (board.charAt(i) != '.') {
                use |= 1 << i;
            }
        }
        dp = new Integer[1 << N];
        return rec(use) == 1 ? "YES" : "NO";
     }
    
    Integer dp[];
    int N;

    int rec(int use) {
        if (testBit(use, N - 1)) use ^= 1 << N - 1;
        if (dp[use] != null) return dp[use];
        for (int i = 0; i < N; ++i) {
            if (i + 1 < N && testBit(use, i) && !testBit(use, i + 1)) {
                int nuse = use ^ (1 << i) ^ (1 << i + 1);
                if (rec(nuse) == 0) return dp[use] = 1;
            }
            if (i + 3 < N && testBit(use, i) && testBit(use, i + 1)
            && testBit(use, i + 2) && !testBit(use, i + 3)) {
                int nuse = use ^ (1 << i) ^ (1 << i + 3);
                if (rec(nuse) == 0) return dp[use] = 1;
            }
        }
        return dp[use] = 0;
    }

    boolean testBit(int x, int p) {
        return ((x >> p) & 1) == 1;
    }
}

Div2 - 1000 EllysFiveFriends

public class EllysFiveFriends {

    static final long MOD = 1000 * 1000 * 1000 + 7;

    boolean check(int a[]) {
        for (int i = 0; i < 5; ++i) {
            if (a[i] > 0) return false;
        }
        return true;
    }

    long getHash(int a[]) {
        long r = 0;
        for (int i = 0; i < 5; ++i) {
            r = r * 10007 + a[i];
        }
        return r;
    }

    static final int MAX = 1 << 22;
    static final int MASK = MAX - 1;
    static final int MAXH = 1 << 21;
    int NH;
    long Hkey[];
    int Hval[];
    int Hnext[];
    int h[];

    int get(long key) {
        int pos = (int)(key&MASK);
        for (int cur = h[pos]; cur != 0; cur = Hnext[cur]) {
            if (Hkey[cur] == key)  return Hval[cur];
        }
        return -1;
    }
    int rec(int a[]) {
        if (check(a)) return 1;
        long key = getHash(a);
        int t = get(key);
        if (t != -1) return t;
        int pos = (int)(key&MASK);
        long res = 0;
        for (int i = 0; i < 5; ++i) {
            int j = i + 1;
            if (j == 5) j = 0;
            if (a[i] <= 0 || a[j] <= 0) continue;
            int x = a[i], y = a[j];
            a[i] >>= 1;
            a[j] >>= 1;
            res += rec(a);
            a[i] = x;
            a[j] = y;
            if ((a[i] & 1) == 1 && (a[j] & 1) == 1) {
                --a[i];
                --a[j];
                res += rec(a);
                ++a[i];
                ++a[j];
            }
        }
        int r = (int)(res % MOD);
        Hkey[NH] = key;
        Hval[NH] = r;
        Hnext[NH] = h[pos];
        h[pos] = NH++;
        return r;
    }
    

    public int getZero(int[] numbers) {        
        h = new int[MAX];
        Hkey = new long[MAXH];
        Hval = new int[MAXH];
        Hnext = new int[MAXH];
        NH = 1;
        return rec(numbers);
     }
}

Div1 - 500 EllysNumbers

import java.util.*;

public class EllysNumbers {
    List<Integer> uses;
    int N;

    int[] collect(String[] s) {
        String str = "";
        for (String cur : s) {
            str += cur;
        }
        String ss[] = str.split(" ");
        int r[] = new int[ss.length];
        for (int i = 0; i < ss.length; ++i) {
            r[i] = Integer.valueOf(ss[i]);
        }
        return r;
    }

    public long getSubsets(long n, String[] special) {        
        Set<Integer> divisors = new TreeSet<Integer>();
        int vals[] = collect(special);
        for (int val : vals) {
            add(divisors, val);
        }
        List<Integer> d1 = new ArrayList<Integer>();
        List<Integer> d2 = new ArrayList<Integer>();
        long x = n;
        for (Integer divisor : divisors) {
            int c = 0;
            while (x % divisor == 0) {
                ++c;
                x /= divisor;
            }
            if (c == 0) continue;
            d1.add(divisor);
            d2.add(c);
        }

        if (x > 1) return 0;
        N = d1.size();
        uses = new ArrayList<Integer>();
        for (int val : vals) {
            int cur = val;
            boolean ok = true;
            int use = 0;
            for (int i = 0; ok && i < d1.size(); ++i) {
                int c = 0;
                while (cur % d1.get(i) == 0) {
                    cur /= d1.get(i);
                    ++c;
                }
                if (c == 0) continue;
                if (c == d2.get(i)) {
                    use |= 1 << i;
                    continue;
                }
                ok = false;
            }
            if (cur != 1 || !ok) continue;
            uses.add(use);
        }
        return calc();
     }
    
    long calc() {
        long dp[][] = new long[2][1 << N];
        int prev = 0, next = 1;
        dp[prev][(1 << N) - 1] = 1;
        for (int k = uses.size() - 1; k >= 0; --k) {
            int nuse = uses.get(k);
            for (int use = 0; use < 1 << N; ++use) {
                dp[next][use] = dp[prev][use];
                if ((use + nuse) == (use ^ nuse))
                    dp[next][use] += dp[prev][use ^ nuse];
            }
            int tmp = prev;
            prev = next;
            next = tmp;
        }
        return dp[prev][0];
    }

    void add(Set<Integer> d, int val) {
        for (int i = 2; i * i <= val; ++i) {
            int c = 0;
            while (val % i == 0) {
                val /= i;
                ++c;
            }
            if (c > 0) d.add(i);
        }
        if (val != 1) d.add(val);
    }
}

Div1 - 1000 #

SRM 533

Div2 - 250 PikachuEasy

public class PikachuEasy {
   public String check(String word) {
        String w[] = {"pi", "ka", "chu"};
        while (true) {
            boolean was = false;
            for (String cur : w) {
                if (word.startsWith(cur)) {
                    word = word.substring(cur.length());
                    was = true;
                }
            }
            if (!was) break;
        }
        if (word.length() == 0) return "YES";
        return "NO";
   }
}

Div2 - 500, Div1 - 250 CasketOfStarEasy

public class CasketOfStarEasy {
    int w[];
    Integer dp[][] = new Integer[100][100];
    int rec(int lo, int hi) {
        if (lo + 1 == hi) return 0;
        if (dp[lo][hi] != null) return dp[lo][hi];
        int tmp = w[lo] * w[hi];
        int res = 0;
        for (int k = lo + 1; k < hi; ++k) {
            res = Math.max(res, rec(lo, k) + rec(k, hi) + tmp);
        }
        return dp[lo][hi] = res;
    }
    public int maxEnergy(int[] weight) {
        this.w = weight;
        return rec(0, weight.length - 1);
    }
}

Div2 - 1000 MagicalGirl

public class MagicalGirl {
    int[] day, win, gain;
    int M;
    Double dp[][] = new Double[51][100 * 1000 + 1];
    
    double rec(int k, int m) {
        if (dp[k][m] != null) return dp[k][m];
        int curDay = day[k];
        if (m == 0) return curDay;
        int nextDay = k + 1 < day.length ? day[k + 1] : 10000000;
        int d = nextDay - curDay;
        double r1, r2;
        if (m >= d) r1 = rec(k + 1, m - d);
         else r1 = curDay + m;
        int g = Math.min(m + gain[k], M);
        double p = win[k] / 100.0;
        if (g >= d) r2 = rec(k + 1, g - d) * p + curDay * (1.0 - p);
        else r2 = (curDay + g) * p + curDay * (1.0 - p);
        return dp[k][m] = Math.max(r1, r2);
    }

    public double maxExpectation(int M, int[] day, int[] win, int[] gain) {
        int n = day.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (day[i] > day[j]) {
                    int tmp;
                    tmp = day[i]; day[i] = day[j]; day[j] = tmp;
                    tmp = win[i]; win[i] = win[j]; win[j] = tmp;
                    tmp = gain[i]; gain[i] = gain[j]; gain[j] = tmp;
                }
            }
        }
        this.day = day;
        this.win = win;
        this.gain = gain;
        this.M = M;
        if (M < day[0]) return M;
        return rec(0, M - day[0]);
    }
}

Div1 - 500 #

Div1 - 1000 #

SRM 531

Div2 - 250 UnsortedSequence

import java.util.Arrays;
public class UnsortedSequence {
    public int[] getUnsorted(int[] s) {
        int n = s.length;
        if (n == 1) return new int[0];
        Arrays.sort(s);
        int i = n - 2;
        while (i >= 0 && s[i] == s[i + 1]) --i;
        if (i < 0) return new int[0];
        int t = s[i];
        s[i] = s[i + 1];
        s[i + 1] = t;
        return s;
    }
}

Div2 - 600, Div1 - 300 NoRepeatPlaylist

import java.util.*;
public class NoRepeatPlaylist {
    int N, M, P;
    static final int MOD = 1000 * 1000 * 1000 + 7;

    long dp[][] = new long[101][101];

    long rec(int k, int used) {
        if (k == P) {
            return used == N ? 1 : 0;
        }
        if (dp[k][used] != -1) return dp[k][used];
        long res = 0;
        if (used < N) res = rec(k + 1, used + 1);
        int busy = Math.min(k, M);
        if (used > busy) {
            res += rec(k + 1, used) * (used - busy);
            res %= MOD;
        }
        return dp[k][used] = res;
    }


    public int numPlaylists(int N, int M, int P) {
        this.M = M;
        this.P = P;
        this.N = N;
        for (int i = 0; i <= 100; ++i) {
            Arrays.fill(dp[i], -1);
        }
        long ans = rec(0, 0);
        for (int i = 2; i <= N; ++i) {
            ans = (ans * i) % MOD;
        }
        return (int)ans;
    }
}

Div2 - 950 #

import java.util.*;
public class KingdomReorganization {
    void dfs(int u, char[][] a, boolean[] use) {
        use[u] = true;
        int n = a.length;
        for (int v = 0; v < n; ++v) {
            if (use[v]) continue;
            if (a[u][v] != '1') continue;
            dfs(v, a, use);
        }
    }

    int countOfComponent(char[][] a) {
        int n = a.length;
        int res = 0;
        boolean use[] = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (use[i]) continue;
            dfs(i, a, use);
            ++res;
        }
        return res;
    }

    class Edge implements Comparable<Edge> {
        int u, v, cost;
        Edge(int u, int v, int cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }
        public int compareTo(Edge e) {
            return cost - e.cost;
        }
    }

    int get(char ch) {
        if (Character.isUpperCase(ch)) return ch - 'A';
        return ch - 'a' + 26;
    }


    public int getCost(String[] kingdom, String[] build, String[] destroy) {
        List<Edge> buildEdges = new ArrayList<Edge>();
        List<Edge> destroyEdges = new ArrayList<Edge>();
        int n = kingdom.length;
        char a[][] = new char[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                a[i][j] = kingdom[i].charAt(j);
                if (i >= j) continue;
                if (a[i][j] == '1') {
                    destroyEdges.add(new Edge(i, j, get(destroy[i].charAt(j))));
                } else {
                    buildEdges.add(new Edge(i, j, get(build[i].charAt(j))));
                }
            }
        }
        Collections.sort(buildEdges);
        Collections.sort(destroyEdges);
        int cnt = countOfComponent(a);
        int res = 0;
        // destroy
        for (int i = 0; i < destroyEdges.size(); ++i) {
            int u = destroyEdges.get(i).u;
            int v = destroyEdges.get(i).v;
            int cost = destroyEdges.get(i).cost;
            a[u][v] = a[v][u] = '0';
            int newCnt = countOfComponent(a);
            if (newCnt == cnt) {
                res += cost;
            } else {
                a[u][v] = a[v][u] = '1';
            }
        }
        // build 
        for (int i = 0; i < buildEdges.size(); ++i) {
            int u = buildEdges.get(i).u;
            int v = buildEdges.get(i).v;
            int cost = buildEdges.get(i).cost;
            a[u][v] = a[v][u] = '1';
            int newCnt = countOfComponent(a);
            if (newCnt == cnt) {
                a[u][v] = a[v][u] = '0';
            } else {
                res += cost;
                cnt--;
            }
        }
        return res;
    }
}

Div1 - 500 #

Div1 - 1000 #