1 Feb 2007 bi   » (Journeyer)

Golbasto Momarem Evlame Gurdilo Shefin Mully Ully Gue

Update:

Update #2: I see the solutions for Bitwise 2007 are up. Well, fzort and myself took part, and we got into the top 50... but I still wanted to know how well my solutions compare against the `official' solutions. So...

Problem 1

My approach:
Remove the outer layer of leaves, and repeat until the number of nodes ≤ 2; then the remaining node(s) will be the answer.

This will be O(n) except that in one place (marked /* ugh */) I do a linear search in the adjacency list for a node.

My code:

#include <stdio.h>

int main()
{
        unsigned test_cases, n, e, i, j, k, frog, lvi;
        static unsigned deg[1000], adjl[1000][1000], lv[2][1000], nlv[2];
        scanf("%u", &test_cases);
        while (test_cases--) {
                scanf("%u", &n);
                e = n - 1;
                for (i = 0; i < n; ++i)
                        deg[i] = 0;
                while (e--) {
                        scanf("%u %u", &i, &j);
                        adjl[i][deg[i]++] = j;
                        adjl[j][deg[j]++] = i;
                }
                nlv[0] = 0;
                for (i = 0; i < n; ++i)
                        if (deg[i] < 2)
                                lv[0][nlv[0]++] = i;
                frog = 0;
                while (n > 2) {
                        nlv[!frog] = 0;
                        for (lvi = 0; lvi < nlv[frog]; ++lvi) {
                                --n;
                                i = lv[frog][lvi];
                                if (deg[i] == 0)
                                        continue;
                                j = adjl[i][0];
                                /* ugh */
                                for (k = 0; adjl[j][k] != i; ++k);
                                adjl[j][k] = adjl[j][--deg[j]];
                                if (deg[j] == 1)
                                        lv[!frog][nlv[!frog]++] = j;
                        }
                        frog = !frog;
                }
                for (lvi = 0; lvi < nlv[frog]; ++lvi)
                        printf("%u ", lv[frog][lvi]);
                putchar('\n');
        }
        return 0;
}

Official solution:

Step 1: Identify any leaf of the tree.
Step 2: Find one of the farthest leaves from that leaf (and name it L1).
Step 3: Find one of the farthest leaves from L1, and name it L2.
Step 4: The middle point(s) of the path L1-L2 is the ‘center’ of the graph and the ideal location for Spiderman to buy a house for Mary-Jane.

Conclusion: my code seems to work, but I think the official solution makes more sense.

Problem 2

My approach:
For each denomination a[i], maintain 2 arrays, one for when a[i] is used, one for when a[i] is not used. Once each a[i] is processed, throw it away. In other words, successively find the number of coins needed to achieve a sum of 0, 1, 2, ..., S, using only { a[1] }, { a[1], a[2] }, { a[1], a[2], a[3] }, ...

(The "frog" thing in the code is totally unneeded, but I can't be bothered to clean it up.)

My code:

#include <limits.h>
#include <stdio.h>

int main()
{
        unsigned test_cases, s, d, a, b, t, c1, c2, frog;
        static unsigned coins[2][10001];
        scanf("%u", &test_cases);
        while (test_cases--) {
                scanf("%u %u", &s, &d);
                frog = 0;
                coins[frog][0] = 0;
                for (t = 1; t <= s; ++t)
                        coins[frog][t] = UINT_MAX;
                while (d--) {
                        scanf("%u %u", &a, &b);
                        if (b == 0)
                                b = 1;
                        for (t = 0; t < a * b && t <= s; ++t)
                                coins[!frog][t] = UINT_MAX;
                        for (; t <= s; ++t) {
                                if (coins[frog][t - a * b] == UINT_MAX)
                                        c1 = UINT_MAX;
                                else
                                        c1 = coins[frog][t - a * b] + b;
                                if (coins[!frog][t - a] == UINT_MAX)
                                        c2 = UINT_MAX;
                                else
                                        c2 = coins[!frog][t - a] + 1;
                                coins[!frog][t] = c1 < c2 ? c1 : c2;
                        }
                        for (t = 0; t <= s; ++t)
                                if (coins[frog][t] < coins[!frog][t])
                                        coins[!frog][t] = coins[frog][t];
                        frog = !frog;
                }
                if (coins[frog][s] == UINT_MAX)
                        printf("-1\n");
                else
                        printf("%u\n", coins[frog][s]);
        }
        return 0;
}

Official solution:

n(S) = min(∀i, V[i])
where, V[i] = min { n(S - a[i] * (b[i] + j)) + (b[i] + j) }, ∀j, j ∈ [0, b[i])

Initialization Step:
n(x) = 0, if x = 0
n(x) = ∞, if x != 0

Conclusion: I don't know what the official solution is saying. :|

Problem 5

My approach:
Consider powers g, g^2, g^3, ..., of a generator g of the multiplicative group A = { 1, 2, ..., p - 1 }. For each possible order d | p - 1 of a group element, there are φ(d) elements with this order -- all the g^i(p/d) where i is coprime with d. Thus
S = Σ[d|p-1] dφ(d)

To efficiently compute this function, factorize p - 1 into powers of distinct primes: p - 1 = q[1]^k[1] q[2]^k[2] ... q[m]^k[m], where all q[.] are distinct and k[.] > 0. Then any factor of p - 1 can be represented uniquely as q[1]^i[1] q[2]^i[2] ... q[m]^i[m] where 0 ≤ i[v] ≤ k[v] for all v. Now φ(q[1]^i[1] q[2]^i[2] ... q[m]^i[m]) = φ(q[1]^i[1])φ(q[2]^i[2])...φ(q[m]^i[m]), so after playing some games with the distributive law,

S
= Π[1≤vm] Σ[0≤i[v]≤k[v]] q[v]^i[v]φ(q[v]^i[v])
= Π[1≤vm] (1 + Σ[1≤ik[v]] q[v]^i . (q[v]^(i-1)) . (q[v] - 1))

(The function prime_power_order(.) probably needs a renaming.)

My code:

#include <limits.h>
#include <stdio.h>

static unsigned long long prime_power_order(unsigned q, unsigned k)
{
        /* find sum of orders for a cyclic group of order q^k */
        unsigned i;
        unsigned long long qq = 1, s = 1;
        for (i = 1; i <= k; ++i) {
                s += qq * q * qq * (q - 1);
                qq *= q;
        }
        return s;
}

int main()
{
        unsigned test_cases;
        unsigned long p, pp, w, k;
        unsigned long long s;
        scanf("%u", &test_cases);
        while (test_cases--) {
                scanf("%lu", &p);
                s = 1;
                pp = p - 1;
                for (w = 2; (unsigned long long)w * w <= pp; ++w) {
                        if (pp % w != 0)
                                continue;
                        k = 0;
                        while (pp % w == 0) {
                                pp /= w;
                                ++k;
                        }
                        s *= prime_power_order(w, k);
                }
                if (pp > 1)
                        s *= prime_power_order(pp, 1);
                printf("%qu\n", s);
        }
        return 0;
}

Official solution:

Note that if n=Π[p|n] p^a then the sum is
Π[p|n] {1+p(p-1)+p^2(p^2-p)+p^3(p^3-p^2)+...+p^a(p^a-p^(a-1))}
which can be also written as
Π[p|n] (1-p+p^2-p^3+...-p^(2a-1)+p^(2a))

Conclusion: really the same solution, except it didn't occur to me to do the final simplification 1 + Σ[1≤ik] q^i . q^(i-1) . (q - 1) = 1 - q + q^2 - q^3 + ... + q^(2k).

Problem 6

fzort solved this problem.

Problem 9

My approach:
I was intending to cast the problem as one of finding the maximum matching in a bipartite graph, but I was too exhausted. :/

Official solution:

The problem reduces to finding maximum cadinality matching in bipartite graphs.

Conclusion: boom.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!