#APMO_2017
Most acquaintances of mine know about my immense obsession with maths. I remembered the moments when I just spent a few hours in a row to crack just a tough mathematical Olympiad problem, merely to enjoy the relief as I finally tackled it successfully. The diminishing occurrences of myself immersing in the sea of mathematical thoughts after IMO 2014, therefore, made me question myself “where did my mathematical passion go?”
In fact, it wasn’t because I didn’t want to do math again. Rather, it was due to practical reasons like time consumption, academic workload, and the application to universities (back then) and internships (right now). It was also because of my obsession with competitive coding, due to my research in graph theory right now and my will to ace my subsequent internship applications. This explains the gradual blending of HackerRank and Codeforces into my regular routine, and the kick-staring of my contest participation on Codeforces after my ascending to O(1) rating (top 1%) on HackerRank (with two gold medals on Week of Code 24 and 32).
My attempt on APMO 2017 was worth a mention in this respect, whereby I tried for no more than 2 hours on the 4-hour paper (during which I captured the main idea of problems 2 to 4 since problems 1 and 5 looked hard). As usual, the “90 degree observation” on problem 2 suggested me to use trigonometric bashing, and the bijection methodology of problem 3 jumped out of itself after expanding the series of 2^x-1 into 1+2+…+2^(x-1). Problem 4 simply relies on the fact that if p divides a+b+c and two of a,b,c are divisible by p, then the the third one is also divisible by p. This leads to the conclusion that the exponent of each prime in the numerator part of c is divisible by (x+y)/gcd(x,y), leading to the solution. The apparent difficult looking of Problem 1 dissuaded me from spending time on it, until I read the solution that outlines its vulnerability under the manipulation of greatest common divisor (gcd) and infinite descent. Meanwhile, problem 5 rendered me clueless, and I didn’t know where to begin (after fake-solving once in my head, only to realize that my proposed invariant did not hold).
This serves to tell something: math still matters for me, but now it’s just not the right time to allocate a few hours in a day just for it. Come Putnam contest preparation, and I will devote more time for you (math) again. ❤
In any case, here’s a mischievous conversion of problem 3 into an algorithmic problem that returns the bijective image from A to B, and vice versa:
Function a->b(array arr) is:
Let n=size(arr), k[i]=log_2(arr[i]+1)
Let array bar[k[0]]
bar[i]=max(sum(exp(k[j]-i-1))
where exp(n)=2^n for n>=0 and 0 for n<0
return bar
Function b->a(array bar) is:
Let n=size(bar)
Let vector arr(0)
Let temp[n],
Foreach i do temp[i]<-bar[i]
while temp[0]>0 do:
let k=0
while (k<n and temp[k]>0) do:
k<-k+1 (so k is the maximum index such that temp[k-1]>0)
arr: push back (exp(k)-1)
where exp(i)=2^i
Foreach i from 0 to k-1 (inclusive) do
temp[i]<-temp[i]-exp(k-i-1)
return arr
anzoteh96 