Использование сторонних библиотек с 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 #

SRM 530

Div2 - 250 GogoXBallsAndBinsEasy
My intuition told me very simple solution. But I don't tried to prove it.

public class GogoXBallsAndBinsEasy {
    public int solve(int[] T) {
        int ans = 0;
        for (int i = 0; i < T.length / 2; ++i) {
            ans += T[T.length - 1 - i] - T[i];
        }
        return ans;
    }
}

Div2 - 500, Div1 - 250 GogoXCake

public class GogoXCake {
    public String solve(String[] cake, String[] cutter) {
        int n = cake.length;
        int m = cake[0].length();
        int r = cutter.length;
        int c = cutter[0].length();
        char a[][] = new char[n][m];
        for (int i = 0; i < n; ++i) {
            a[i] = cake[i].toCharArray();
        }
        for (int i = 0; i + r <= n; ++i) {
            for (int j = 0; j + c <= m; ++j) {
                boolean ok = true;
                for (int i1 = 0; i1 < r; ++i1) {
                    for (int j1 = 0; j1 < c; ++j1) {
                        if (cutter[i1].charAt(j1) != '.') {
                            continue;
                        }
                        if (a[i + i1][j + j1] != '.') {
                            ok = false;
                        }
                    }
                }
                if (!ok) {
                    continue;
                }
                for (int i1 = 0; i1 < r; ++i1) {
                    for (int j1 = 0; j1 < c; ++j1) {
                        if (cutter[i1].charAt(j1) == '.') {
                            a[i + i1][j + j1] = 'X';
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == '.') {
                    return "NO";
                }
            }
        }
        return "YES";
    }
}

Div2 - 1000 GogoXReimuHakurai
Div1 - 500 GogoXMarisaKirisima
Despite the fact that these problems are different (second problem is more common) we can solve them using same approach.

public class GogoXMarisaKirisima {
    public int solve(String[] choices) {
        int n = choices.length;
        boolean a[][] = new boolean[n][n];
        for (int i = 0; i < n; ++i) {            
            for (int j = 0; j < n; ++j) {
                if (i == j) a[i][i] = true;
                else a[i][j] = choices[i].charAt(j) == 'Y';
            }
        }
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (a[i][k] && a[k][j]) {
                        a[i][j] = true;
                    }
                }
            }
        }
        if (!a[0][n - 1]) return 0;
        int V = 0, E = 0;
        boolean use[] = new boolean[n];
        for (int i = 0; i < n; ++i) {
            use[i] = a[0][i] && a[i][n - 1];
        }
        for (int i = 0; i < n; ++i) {
            if (!use[i]) continue;
            ++V;
            for (int j = 0; j < n; ++j) {
                if (!use[j]) continue;
                if (choices[i].charAt(j) == 'Y') {
                    ++E;
                }
            }
        }
        return  E - V +  2;
    }
}

Div1 - 1000 GogoXBallsAndBins

import java.util.*;

public class GogoXBallsAndBins {
    int need, N;
    int[] T;
    Map m[][];
    static final long MOD = 1000 * 1000 * 1000 + 9;
    int rec(int k, int wait, int cum) {
        if (k == N) {
            if (cum == need && wait == 0) return 1;
            return 0;
        }
        if (m[k][wait].containsKey((Integer)cum)) 
            return (Integer)m[k][wait].get(cum);
        long res = rec(k + 1, wait, cum);
        long w = wait;
        if (wait > 0) {
            res += rec(k + 1, wait, cum) * w * 2; 
            res += rec(k + 1, wait - 1, cum + 2 * T[k]) * w * w;
        }
        res += rec(k + 1, wait + 1, cum - 2 * T[k]);
        res %= MOD;
        m[k][wait].put(cum, (int)res);
        return (int)res;
    }

    public int solve(int[] T, int moves) {
        this.T = T;
        need = 2 * moves;
        N = T.length;
        m = new Map[N + 1][N + 1];
        for (int i = 0; i <= N; ++i) {
            for (int j = 0; j <= N; ++j) {
                m[i][j] = new HashMap();
            }
        }
        return rec(0, 0, 0);
     }
}

One sum computation

Solving one problem I encountered one problem. I needed calculate one interesting sum: sigma(N / i), where (1 <= i && <= K). How we can do it as fast as possible. We can do it using complexity sqrt(N) moving from two ends. Following code demonstate this approach.

    long smart(long N, long K) {
        long res = 0;
        long t = (long)Math.sqrt(N * 1.0);
        for (long i = 1; i * i < N; ++i) {
            if (i <= K) res += N / i;
            long lo = Math.max(N / (i + 1), t);
            long hi = Math.min(N / i, K);
            if (hi > lo) res += (hi - lo) * i;
        }
        if (t * t == N && t <= K) res += t;
        return res;
    }

After it I recall one neerc problem. But there we need compute a little different sum: sigma(N % i), where (1 <= i && <= K). So we can replace N % i to (N - N / i * i) and addopt previous code to calculate sigma(N / i * i).

SRM 529

Div2 - 250 PairingPawns

public class PairingPawns {
    public int savedPawnCount(int[] start) {
        int n = start.length;
        for (int i = n - 1; i > 0; --i) {
            start[i - 1] += start[i] / 2;
        }
        return start[0];
     }
}

Div2 - 500, Div1 - 250 KingSort

import java.util.*;

public class KingSort implements Comparator<String> {
    Map<String, Integer> map = new HashMap<String, Integer>();

    public String[] getSortedList(String[] kings) {
        String s1[] = ",I,II,III,IV,V,VI,VII,VIII,IX,X".split(",");
        String s2[] = ",X,XX,XXX,XL,L".split(",");
        for (int i = 1; i <= 50; ++i) {
            map.put(s2[i / 10] + s1[i % 10], i);
        }
        Arrays.sort(kings, this);
        return kings;
    }
    public int compare(String s1, String s2) {
        String t1[] = s1.split(" ");
        String t2[] = s2.split(" ");
        if (!t1[0].equals(t2[0])) return t1[0].compareTo(t2[0]);
        return map.get(t1[1]).compareTo(map.get(t2[1]));
    }
}

Div2 - 1000 MinskyMysteryDiv2

public class MinskyMysteryDiv2 {
    long get(long N) {
        if (N < 2) return -1;
        long i = 2;
        while (i * i <= N && N % i != 0) ++i;
        if (i * i > N) i = N;
        return N / i + i;
    }
    public long computeAnswer(long N) {
        return get(N);
        
     }
}

Div1 - 600 MinskyMystery

import java.util.*;

public class MinskyMystery {

    final int MOD = 1000 * 1000 * 1000 + 9;

    long add(long r, long x) {
        x %= MOD;
        if (x < 0) x += MOD;
        return (r + x) % MOD;
    }

    // get sum N/i (i == 1..N)
    long clever(long N) {
        long res = 0;
        long t = (long)Math.sqrt(1.0 * N);
        long i;
        for (i = 1; i * i < N; ++i) {
            res += N / i;
            if (N / i > t) res += (N / i - N / (i + 1)) * i;
        }
        if (i * i == N) res += i;
        return res;
    }

    public int computeAnswer(long N) {
        if (N < 2) return -1;
        long r = 1;
        long j = 2;
        while (j * j <= N && N % j != 0) ++j;
        if (j * j > N) j = N;

        r = add(r, 2 * j - 3);
        r = add(r, (j - 1) % MOD * (N % MOD) % MOD * 3); 
        r = add(r, (j - 2) % MOD * (N % MOD) % MOD); 

        if (j == N) {
            r = add(r, clever(N) - N);
        } else {
            for (long i = 2; true; ++i) {
                r = add(r, N / i);
                if (N % i == 0) break; 
            }
        }
        return (int)r;
    }
}

Div1 - 900 BigAndSmallAirports