It's been a while since my last post, I want to apologize to the readers of my blog, I was kind of busy studying Chinese.
There is not to much left to say about this match, there is an excellent official contest analysis. Nevertheless, I want to share some ideas that may help somebody to better understand the problems.
Let's first begin with a brute force solution of the small-input, according to the problem statement Maria begins first by drawing a circle of radius \(r + 1\) around the first white circle of radius \(r\), if there is enough paint she continue with a ring of radius \(r + 3\) around a circle of radius \(r + 2\) and so on...
So the area of the \(k\) ring correspond to the expression:
\( A_{k} = (r + 2k - 1)^{2} - (r +2k - 2)^{2} \pi \) \(cm^{2}\)
For example to paint the black rings showed in the previous picture we need:
\(S = ((r + 1) ^2 - r^2) + ((r +3)^{2} - (r + 2)^{2})\) millilitres of black paint.
Let's don't forget that according to the statement 1 \(ml\) of paint is required to cover an area of \(\pi\) \(cm^{2}\).
Because for the small-input the constraints are low, we can just simply sum up the areas of the rings until we run out of black paint:
Until this point everything seems like a fairy tale, unfortunate the constraints for the large-input are kind of evil :). To understand the idea behind the solution we may need some understanding of arithmetic progressions.
An arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant, let's call this constant value \(d\), so the \(n\)-term of certain sequence \(a\) is given by the formula:
\( a_{n} = a_{1} + (n-1)d \)
In order to get some intuition, let's first take a sequence of 3 rings, by our previous area formula we get something like this:
\(a = ((r + 1) ^2 - r^2) , ((r +3)^{2} - (r + 2)^{2}) , ((r +5)^{2} - (r + 4)^{2})\)
So far our expression don't look really arithmetic :) let's apply some algebra and see where it take us:
\(a = (r^{2} + 2r + 1 - r^{2}) , (r^{2} + 6r + 9 - (r^{2} + 4r + 4))
\\ , (r^{2} + 10r + 25 - (r^{2} + 8r + 16))\)
\(a = (2r + 1) , ( 2r + 5) , (2r + 9)\)
Given this expression is easy to see that we have arithmetic progression, with a constant factor \(d = 4\):
\(a = (2r + 1) , ( 2r + 5) , (2r + 9), \cdots, (2r + 4k - 3) \)
\( a_{k} = 2r + 4k - 3 \)
Another way of getting the s \(k\)-th term of our arithmetic sequence, is applying some algebra to the given area formula:
\( a_{k} = (2k + r -1)^{2} - (2k + r -2)^{2} \)
\( a_{k} = (2k + r -1)^{2} - ((2k + r - 1) - 1)^{2} \)
\( a_{k} = (2k + r -1)^{2} - (2k + r - 1)^{2} + 2(2k + r - 1) - 1 \)
\( a_{k} = 2(2k + r - 1) - 1 \)
\( a_{k} = 2r + 4k - 3 \)
Now our next goal is the sum of the area of the first \(k\) black rings, such that \( S_{k} \leq t\) where \(t\) is the total amount of black paint available.
To calculate the sum of an arithmetic progression we use the following formula \(S_{k} = \frac{k(a_{1} + a_{k})}{2} \), here is the proof.
By substituting \(a_{1} = 2r + 1\) and \(a_{k} = 2r + 4k - 3\) we get:
\(S_{k} = \frac{k(2r + 1 + 2r + 4k - 3)}{2} \)
\(S_{k} = \frac{n(4r + 4k - 2)}{2} \)
\(S_{k} = k(2r + 2k - 1)\)
Up to this point we already have all the math that we need, but there still one more problem, we can't check value after value until some \(k\) holds, we are going to need binary search to look for the \(k\) that maximize our result. Because the constraints are a little bit to high, we should be careful with overflow. A work around is use Python, so you don't have to worry about overflow.
There is not to much left to say about this match, there is an excellent official contest analysis. Nevertheless, I want to share some ideas that may help somebody to better understand the problems.
A. Bullseye
http://code.google.com/codejam/contest/2418487/dashboard#s=p0&a=2Let's first begin with a brute force solution of the small-input, according to the problem statement Maria begins first by drawing a circle of radius \(r + 1\) around the first white circle of radius \(r\), if there is enough paint she continue with a ring of radius \(r + 3\) around a circle of radius \(r + 2\) and so on...
So the area of the \(k\) ring correspond to the expression:
\( A_{k} = (r + 2k - 1)^{2} - (r +2k - 2)^{2} \pi \) \(cm^{2}\)
For example to paint the black rings showed in the previous picture we need:
\(S = ((r + 1) ^2 - r^2) + ((r +3)^{2} - (r + 2)^{2})\) millilitres of black paint.
Let's don't forget that according to the statement 1 \(ml\) of paint is required to cover an area of \(\pi\) \(cm^{2}\).
Because for the small-input the constraints are low, we can just simply sum up the areas of the rings until we run out of black paint:
Until this point everything seems like a fairy tale, unfortunate the constraints for the large-input are kind of evil :). To understand the idea behind the solution we may need some understanding of arithmetic progressions.
An arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant, let's call this constant value \(d\), so the \(n\)-term of certain sequence \(a\) is given by the formula:
\( a_{n} = a_{1} + (n-1)d \)
In order to get some intuition, let's first take a sequence of 3 rings, by our previous area formula we get something like this:
\(a = ((r + 1) ^2 - r^2) , ((r +3)^{2} - (r + 2)^{2}) , ((r +5)^{2} - (r + 4)^{2})\)
So far our expression don't look really arithmetic :) let's apply some algebra and see where it take us:
\(a = (r^{2} + 2r + 1 - r^{2}) , (r^{2} + 6r + 9 - (r^{2} + 4r + 4))
\\ , (r^{2} + 10r + 25 - (r^{2} + 8r + 16))\)
\(a = (2r + 1) , ( 2r + 5) , (2r + 9)\)
Given this expression is easy to see that we have arithmetic progression, with a constant factor \(d = 4\):
\(a = (2r + 1) , ( 2r + 5) , (2r + 9), \cdots, (2r + 4k - 3) \)
\( a_{k} = 2r + 4k - 3 \)
Another way of getting the s \(k\)-th term of our arithmetic sequence, is applying some algebra to the given area formula:
\( a_{k} = (2k + r -1)^{2} - (2k + r -2)^{2} \)
\( a_{k} = (2k + r -1)^{2} - ((2k + r - 1) - 1)^{2} \)
\( a_{k} = (2k + r -1)^{2} - (2k + r - 1)^{2} + 2(2k + r - 1) - 1 \)
\( a_{k} = 2(2k + r - 1) - 1 \)
\( a_{k} = 2r + 4k - 3 \)
Now our next goal is the sum of the area of the first \(k\) black rings, such that \( S_{k} \leq t\) where \(t\) is the total amount of black paint available.
To calculate the sum of an arithmetic progression we use the following formula \(S_{k} = \frac{k(a_{1} + a_{k})}{2} \), here is the proof.
By substituting \(a_{1} = 2r + 1\) and \(a_{k} = 2r + 4k - 3\) we get:
\(S_{k} = \frac{k(2r + 1 + 2r + 4k - 3)}{2} \)
\(S_{k} = \frac{n(4r + 4k - 2)}{2} \)
\(S_{k} = k(2r + 2k - 1)\)
Up to this point we already have all the math that we need, but there still one more problem, we can't check value after value until some \(k\) holds, we are going to need binary search to look for the \(k\) that maximize our result. Because the constraints are a little bit to high, we should be careful with overflow. A work around is use Python, so you don't have to worry about overflow.
No comments:
Post a Comment