- Bitwise 2007: registration ends Feb 4, contest on Feb 11 (1200--2400 IST).
- 10th ICFP Contest: on Jul 20--23.
Update:
- And the 3rd Experimental Gameplay Competition, Feb 3--19.
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.
