**Golbasto Momarem Evlame Gurdilo Shefin Mully Ully Gue**

- 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 denominationa[i], maintain 2 arrays, one for whena[i] is used, one for whena[i] is not used. Once eacha[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 powersg,g^2,g^3, ..., of a generatorgof the multiplicative groupA= { 1, 2, ...,p- 1 }. For each possible orderd|p- 1 of a group element, there are φ(d) elements with this order -- all theg^i(p/d) whereiis coprime withd. 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 allq[.] are distinct andk[.] > 0. Then any factor ofp- 1 can be represented uniquely asq[1]^i[1]q[2]^i[2] ...q[m]^i[m] where 0 ≤i[v] ≤k[v] for allv. 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 ifthen the sum isn=Π[p|n]p^aΠ[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 findingmaximum cadinality matchingin bipartite graphs.Conclusion: boom.