wlach totally boggles my mind. So is he saying that the oil companies are raising prices because they, out of the goodness of their hearts, suddenly decide they want to make people moderate their oil consumption in order to save the earth's climate?
berend is normally a raving wingnut, but he's right on the money when he says,
The drive-by media previously reported that one of the definitions of a geek was someone who couldn't get a girlfriend. Now a geek is someone with a stripper as girlfriend:
Preliminary results from the research show so-called computer geeks are becoming the new schoolyard bullies.
In related news, Jacqueline Passey says she's a geek because she watches cheesy TV shows. Geek geek geek!
Edit:
kelly: What? What? It reads below the Citizendium page:
Photo by Magnus Manske. From [1] on Wikimedia Commons. Licensed under GFDL 1.2 or later, or CC-by 1.0.
Call for Spoof Papers!
I figured this is as good a place as any other to repeat my call to submit spoof papers on global warming to the AEI. If you're a global warming researcher, or you know someone who is, or you know someone who knows someone who is, etc. etc., then do help spread the message!
fzort: man,
that's pure evil.
So, IOCCC 2006 and Bitwise 2007 are both over. This leaves the ICFP Contest.
In other news, I see that the Tubes of the Internet are now filled with the latest antics of the wikiclowns:
I hope both projects will soon collapse under the sheer weight of their own stupidity, and we can have something better.
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.
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...
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.
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 != 0Conclusion: I don't know what the official solution is saying. :|
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. ThusS = Σ[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≤v≤m] Σ[0≤i[v]≤k[v]] q[v]^i[v]φ(q[v]^i[v])
= Π[1≤v≤m] (1 + Σ[1≤i≤k[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≤i≤k] q^i . q^(i-1) . (q - 1) = 1 - q + q^2 - q^3 + ... + q^(2k).
fzort solved this problem.
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.
"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.
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...
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!
