I did not actually compete in the competition(I slept thru it) but came up
with this answer which is O(1) per case in python
http://0xdeafc0de.wordpress.com/2013/04/30/gcj-2013-r1a-bullseye-o1-solution/
- Madura A.
On Sun, Apr 28, 2013 at 10:23 PM, alv-r- <[email protected]> wrote:
> Em sábado, 27 de abril de 2013 21h53min06s UTC-3, alv-r- escreveu:
> > For the first circle, you need pi*(r+1)²-pi*r², which is pi*((r+1)² -
> r²) cm², since 1 mililiter covers pi cm², you need (r+1)²-r² paint.
> >
> >
> >
> > following this logic, for each circle you need:
> >
> > 1st: (r+1)² - (r-0)²
> >
> > 2nd: (r+3)² - (r-2)²
> >
> > 3rd: (r+5)² - (r-4)²
> >
> > 4th: (r+7)² - (r-6)²
> >
> > and so on...
> >
> >
> >
> > note the relation between each one: 1 0, 3 2, 5 4, 7 6 ...
> >
> > generalizing, the "numbers" for the i-th circle are 2i-1 and 2i-2
> >
> >
> >
> > So, the general formula for the amount of paint you need for the i-th
> circle is:
> >
> > (r+(2i-1))² - (r+(2i-2))²
> >
> > which, simplifying, leads to: c
> >
> >
> >
> > The amount of paint you need to paint all circles from i to n, are:
> >
> >
> >
> > Summation(4i+2r-3) from i=1 to n
> >
> > The formula for this summation is: n(2n + 2r - 1)
> >
> >
> >
> > In the algorithm, he uses (2 * r + 1) * n + 2.0 * n * (n - 1), which is
> equivalent to 2n²+2nr-n = n(2n+2r-1).
> >
> >
> >
> > So, basically, what the algorithm does is a binary search to search for
> "n" (the number of circles) where the amount of paint needed will be
> smaller than t (amount of paint you have).
> >
> >
> >
> > Hope this helps you nderstand.
> >
> >
> >
> > (Now, why the comparison to 1.5t is used, is also a mystery to me :P).
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > Hi,
> >
> > >
> >
> > >
> >
> > >
> >
> > > I understand that they're using binary search, but I don't know how
> can it get to the solution.
> >
> > >
> >
> > > Could someone be very nice and explain the code below, please?
> >
> > >
> >
> > > This is from coder "wata":
> >
> > >
> >
> > >
> >
> > >
> >
> > > void solve() {
> >
> > >
> >
> > > long left = 0, right = 1L << 40;
> >
> > >
> >
> > > while (right - left > 1) {
> >
> > >
> >
> > > long n = (left + right) / 2;
> >
> > >
> >
> > > if ((double)(2 * r + 1) * n + 2.0 * n * (n - 1) > 1.5 * t)
> {
> >
> > >
> >
> > > right = n;
> >
> > >
> >
> > > } else if ((2 * r + 1) * n + 2 * n * (n - 1) > t) {
> >
> > >
> >
> > > right = n;
> >
> > >
> >
> > > } else {
> >
> > >
> >
> > > left = n;
> >
> > >
> >
> > > }
> >
> > >
> >
> > > }
> >
> > >
> >
> > > System.out.println(left);
> >
> > >
> >
> > > }
> >
> > >
> >
> > >
> >
> > >
> >
> > > Why those values, why 1.5? Man, I don't understand this code :(
> >
> > >
> >
> >
> >
> > >
> >
> > >
> >
> > > Em sábado, 27 de abril de 2013 05h42min58s UTC-3, Vaibhav Tulsyan
> escreveu:
> >
> > >
> >
> > > > I was seeing the solutions of the top 10 contestants for the large
> input of Bull's Eye. They all seem to have used some method involving
> variables like beginning,end and mid. Can anybody explain to me what method
> they've applied exactly?
> >
> > >
> >
> > > > I just used basic maths to solve it. They seem to have used some
> better algorithm.
>
> I typed it wrong, should be "which, simplifying, leads to: 4i+2r-3" dunno
> where that "c" came from, lol.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msg/google-code/-/jpk2UXZmAEkJ.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
