Older blog entries for bi (starting at number 62)

16 Feb 2007 (updated 17 Feb 2007 at 06:51 UTC) »
Lumos Kelmin pesso desmar lon emposo

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... (long-winded stuff ahead)

And, an old blog post on googlejuice:

One of the great ironies of my recent mistake here was that it actually increased this blog's Googlejuice. Between those who linked to complain, my responses in apology, and those who followed up on my explanation saying they hadn't seen my apology, the incoming link traffic here actually rose 50%. If some of those people stick around (maybe wondering when I'll fall on my face next) it's actually a good thing.

Update: I was Journeyer before, but after OpenSpecies gave me an additional certification, I'm now Observer. Weird.

1 Feb 2007 (updated 17 Feb 2007 at 06:50 UTC) »
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.

28 Jan 2007 (updated 28 Jan 2007 at 08:46 UTC) »
Word of the Day: "Jihadi"

"Jihadi"? I want to seek out and physically harm the person who coined this stupid word. People who engage in jihads are either "jihadists" or "mujahidin". A "Jihadi" is a citizen of the hypothetical nation of Jihad.

17 Jan 2007 (updated 17 Jan 2007 at 12:06 UTC) »
Towards permalinks all the way

The .tk domain for my Pax Neo-TeX doesn't forward URL paths -- zompower.tk forwards to fzort.org/bi/neo-tech/, but zompower.tk/vote.php won't forward to fzort.org/bi/neo-tech/vote.php. To work around this, I added some PHP at the top of the index page to redirect to the appropriate page if the referrer contains a path to some other page:

<?
$refr = $_SERVER['HTTP_REFERER'];
if (isset($refr)) {
        $refrp = parse_url($refr);
        $rhost = $refrp['host'];
        $rpath = $refrp['path'];
        if (($rhost === 'zompower.tk' ||
             $rhost === 'www.zompower.tk') &&
             $rpath !== '' && $rpath !== '/' && $rpath !== '/index.php') {
                $rfrag = $refrp['fragment'];
                $rqy = $refrp['query'];
                if (isset($rfrag) && $rfrag !== '')
                        $rfrag = '#' . $rfrag;
                else if (isset($rqy) && $rqy !== '')
                        $rfrag = '#' . $rqy;
                header("Location: http://fzort.org/bi/neo-tech" .
                    $rpath . $rfrag);
        }
}
?>

The code also converts query strings (e.g. ?foo) into anchors (e.g. #foo).

This trick may be useful with other forwarding services and web sites as well...

12 Jan 2007 (updated 12 Jan 2007 at 16:09 UTC) »
Quo errat demonstrator

  • I did a silly Shockwave Flash clock.
  • Here is a version of the comp.lang.logo FAQ from, um, January 1994. This FAQ is a bit hard to find on Google, for some reason.
  • OK, where can I find some sort of specification of classical versions of Logo?

Update: eh...
Update #2: source files for the clock: 1, 2.

6 Jan 2007 (updated 6 Jan 2007 at 18:34 UTC) »
This entry intentionally not blank, but there should really be a picture of a cute doggie here

Some crazy things across the new year:

  • The froofy::qua::buffer_out slowness problem seems to be fixed, and froofyJIT 0.24 is out.
  • Jay is Games is holding a Flash game design competition.
  • There's a new IOCCC on. (It's called IOCCC 2006 and not IOCCC 2007 -- it officially starts 2006 Dec 31 23:59 UTC. Heh.)
29 Dec 2006 (updated 29 Dec 2006 at 21:22 UTC) »
"Wheeee!", as they (?) say

In a fit of weirdness, I slapped together an implementation of quajects and added it to froofyJIT 0.23.

Qua!

(I admit, my pic(1) skills aren't 31337 enough yet. I originally wanted to do a stuffed koala, but in the end it turned into a generic teddy bear.)

There's still a problem though: buffer_out is sometimes fast, and sometimes slow. I've not exactly nailed down the cause of the slowness yet...

Are we on the same page?

From Linux getpagesize(2):

Generally, one uses binaries that are architecture but not machine model dependent, in order to have a single binary distribution per architecture. This means that a user program should not find PAGE_SIZE at compile time from a header file, but use an actual system call, at least for those architectures (like sun4) where this dependency exists.

Aww.

And froofyJIT 0.22 is out.

21 Dec 2006 (updated 21 Dec 2006 at 16:55 UTC) »
And Michael Moore is still fat

fejj: Duh.

20 Dec 2006 (updated 20 Dec 2006 at 19:18 UTC) »
Merry Christmas: Because Michael Moore is fat

fejj, nutella: Hmm.

Update: fejj: Jeez.

53 older 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!