Re: [gcj] Re: Bull's Eye - Large
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- alvaro.br...@gmail.com 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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [gcj] Re: Bull's Eye - Large
I dont understad it either. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [gcj] Re: Bull's Eye - Large
Area of the first white circle is pi* r*r
Area of first black circle that includes first white circle is pi * (r+1) *
(r+1)
So area of first black strip is pi * (r+1) * (r+1) - pi *r *r
If you continue doing this then area of second black strip is pi * (r+3) *
(r+3) - pi * (r+2) * (r+2)
So total area of n black strips is (pi * (r+1) * (r+1) - pi * r * r) + (pi
* (r+3) * (r+3) - pi * (r+2) * (r+2)) + ...
I will remove pi as pi is common for all. So above expression can be
written as
(r*r + 2*r + 1 - r *r) + (r*r + 6 * r + 9 - r * r + 4 * r + 4) + ..
( 2* r + 1) + ( 2*r + 5) + (2r + 9) + .
2 * r * n + (1 + 5 + 9 + )
2* r * n + ( 1 + (1 + 4) + ( 1 + 8 ) + )
2 * r * n + ( 1 * n + ( 4 + 8 + 12 + ...))
2 * r * n + 1 * n + 4 * n * ( n-1) /2
2 * r * n + n + 2 * n * (n -1)
This is the formula everyone used to do the binary search
=
On Sat, Apr 27, 2013 at 1:04 PM, newbie007 lescoutinh...@gmail.com wrote:
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.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msg/google-code/-/nB8pI_xLLzAJ.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [gcj] Re: Bull's Eye - Large
int a=2*r+1; int d=4; double d=-(2*a-d)+Math.sqrt((2*a-d)*(2*a-d)+8*d*k); int dinominator=2*d; int result=d/dinominator; answer is result On Sun, Apr 28, 2013 at 7:35 AM, bas 366a...@gmail.com wrote: The result of that formula is very large, so there is a possibility that it will not fit into a 64-bit integer. The first comparison uses 'double' type to check if this number is too large. If it is, it is certainly bigger than t. If it is not, more precise integer computations can be used (second comparison). I guess 1.5 is just a large enough number to be safe. I personally used 'unsigned long long' instead, and that was enough to avoid dealing with floating point calculations. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [gcj] Re: Bull's Eye - Large
Thank you Kannapan. I tested with 1.4 and 1.6 and both worked. 1.0 does't
work.
I also tested the code without the first condition, but it's necessary to
make it work.
On Sat, Apr 27, 2013 at 4:42 PM, Kannappan deshka...@gmail.com wrote:
the 1.5 might just be to speed up the process to get the value. even if
1.6 was used or 1.55 was used for that matter, you might still get the
right answer but with varying speeds. thats just my guess. haven't tried it.
On Sat, Apr 27, 2013 at 6:04 PM, newbie007 lescoutinh...@gmail.comwrote:
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.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msg/google-code/-/nB8pI_xLLzAJ.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [gcj] Re: Bull's Eye - Large
Thank you Bas and Samuel.
Thanks a lot Raj and Álvaro. Now I understand the formula. =)
On Sun, Apr 28, 2013 at 7:08 PM, Leandro Coutinho
lescoutinh...@gmail.comwrote:
Thank you Kannapan. I tested with 1.4 and 1.6 and both worked. 1.0 does't
work.
I also tested the code without the first condition, but it's necessary to
make it work.
On Sat, Apr 27, 2013 at 4:42 PM, Kannappan deshka...@gmail.com wrote:
the 1.5 might just be to speed up the process to get the value. even if
1.6 was used or 1.55 was used for that matter, you might still get the
right answer but with varying speeds. thats just my guess. haven't tried it.
On Sat, Apr 27, 2013 at 6:04 PM, newbie007 lescoutinh...@gmail.comwrote:
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.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msg/google-code/-/nB8pI_xLLzAJ.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [gcj] Re: Bull's Eye - Large
the 1.5 might just be to speed up the process to get the value. even if 1.6
was used or 1.55 was used for that matter, you might still get the right
answer but with varying speeds. thats just my guess. haven't tried it.
On Sat, Apr 27, 2013 at 6:04 PM, newbie007 lescoutinh...@gmail.com wrote:
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.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msg/google-code/-/nB8pI_xLLzAJ.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
