Older blog entries for bi (starting at number 61)

1 Feb 2007 (updated 17 Feb 2007 at 06:50 UTC) »
Golbasto Momarem Evlame Gurdilo Shefin Mully Ully Gue


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) {
                                i = lv[frog][lvi];
                                if (deg[i] == 0)
                                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]);
        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;
                                        c1 = coins[frog][t - a * b] + b;
                                if (coins[!frog][t - a] == UINT_MAX)
                                        c2 = UINT_MAX;
                                        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("%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,

= Π[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)
                        k = 0;
                        while (pp % w == 0) {
                                pp /= w;
                        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:

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.


(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.


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.

19 Dec 2006 (updated 21 Dec 2006 at 17:15 UTC) »
There are some things we know that we know...

Who will win in a fight between fejj, Zaitcev, and King Arthur? I don't know (well... I'll bet on King Arthur), but check out the following words which fejj quotes Clinton as saying (emphasis added):

"And mark my words, he will develop weapons of mass destruction. He will deploy them, and he will use them. Because we are acting today, it is less likely that we will face these dangers in the future."

From these words, he goes on to draw this conclusion (emphasis added, again):

[...] it is interesting to note that even the Clinton Administration claimed that Iraq had WMDs [...]

Now, when someone can't properly distinguish between the past tense, the present tense and the future tense, are we supposed to trust his self-righteous pronouncements on US presidents past and present?

(Wait. Why's fejj reading Slashdot?)

Update: fejj concedes his "wording was wrong there". Would that he would apply the same charitable interpretation to the Slashdot poster's words! But no; he had to go on a lengthy diatribe over what it means for "Bush" to have "lied", to conclude -- of course -- that the schmuck was guilty of evil evil evil anti-Bush bias.

But anyway, consider these. Hans Blix's inspection in Iraq in 2003 was met with unprecedented cooperation, and indeed he wrote that

Iraq has on the whole cooperated rather well so far with UNMOVIC in this field.  The most important point to make is that access has been provided to all sites we have wanted to inspect and with one exception it has been prompt.

Blix asked for a few more months to resolve the outstanding WMD issues. Did Bush listen? So, how justified was Bush's invasion of Iraq? And what's the whole idea of going into a war without a coherent post-war plan?

Update #2: fejj trots out the old discredited argument as used by Donald "Unknown unknowns" Rumsfeld:

There is/was only one way to find out for sure if Iraq had WMDs - invade (as you say, there have been, to my knowledge, no found WMDs of nuclear nature inside the boarders of Iraq, that we know of - but that doesn't mean they don't exist, hidden somewhere; similarly it doesn't mean that they do. But that was my previous point).

Wow, great. Notice that you can use this argument as a basis to invade any country whatsoever -- just replace the word "Iraq" with something else. Who needs intelligence operations when all you need is to sit in a room and engage in such philosophical wankery?

And fejj goes on to say,

Saddam was unstable - a threat to the people of Iraq and his neighbors and had been for decades, it was time this threat was eliminated for the safety of millions.

Is Iraq really safer than before? No, according to Burnham et al. Well, obviously war supporters don't like this conclusion, so they've taken to criticizing Burnham et al.'s work using the "let's hurl feces at them and totally refuse to learn the actual science behind their work w00t w00t w00t!!!!!11111111" methodology.

nutella: At least I can say I didn't start this whole thing. And of course, Michael Moore is fat.

Update #3: fejj, are you really that obtuse? Your above thesis on WMD is unfalsifiable -- it's constructed in such a way that it admits no possibility of contrary evidence, because any empirical observation can be made to "fit" with it. In brief, it's a silly piece of sophistry that doesn't merit discussion.

Update #4: fejj says,

So, despite a higher mortality rate, the Iraqi people seem to prefer life post-Saddam as compared to under Saddam.

Blatant moving of goalposts. You said that invading Iraq was for the "safety of millions". Burnham et al.'s Lancet report says Iraq wasn't safer than before. The survey you cite doesn't even address this question -- it talks about a whole bunch of other stuff, and the closest it gets to the safety issue is saying "85 per cent feel safer with CPA in place", which is a totally vague assertion. ("Feel" safer? With the CPA in place, in contrast to... what? A total power vacuum, maybe?)

Iraq isn't safer than before. Get over it.

I agree that the claim that Iraq had WMDs is unfalsifiable [...]

...and, in case you don't already know, this makes your argument as rational as other unfalsifiables -- conspiracy theories, Creation Science, postmodernist gobbledygook, and so on. If a theory can "fit" whatever reality is presented to it, then it means the theory says nothing about reality. Is this so difficult to see?

I find it hillarious that the only argument against what I've posted comes down to:

"No really, Bush is a Bad Man because I say so."

How about "no really, invading Iraq was good because I say so"? Do you have no substantive points which actually address other people's arguments? I agree with zanee, you're not trying to engage in rational discussion.

52 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!