Page 1 of 1
11114 - Polygon Encoder
Posted: Sun Oct 08, 2006 11:49 pm
by sclo
I don't see any indication of the size of the input, but after some testing, the length of the input number should be at most 400 decimal digits.
Posted: Thu Apr 05, 2007 6:06 pm
by Khaled_912
The problem is all about writing the decode function.. the rest is straight forward. I'm getting TLE... Here's my decode function, which decodes a value 'p' into the corresponding row and column 'r' and 'c':
Code: Select all
void decode(type p, type& r, type& c)
{
type l = 0;
type h = p + 1;
while(1 < h - l)
{
type m = (l + h)/2;
if (p < m*(m+1)/2) h = m;
else l = m;
}
//d = (sqrt(1 + 8*p) - 1)/2;
type& d = l; // The diagonal number
c = p - (d*d + d)/2;
r = d - c;
}
is there a faster method using bigints ???? I deduced a formula for direct calculation of the row and the column (the commented line 'd = ...') instead of binary search, but it involves calculating sqrt, so I couldn't use it with bigint.
any ideas or hints ??
Posted: Thu Apr 05, 2007 6:41 pm
by little joey
I'm not sure if it's the only way, but I did it by taking sqrts from bignums.
So put your teeth into it
. The code will be useful for many other problems.
Posted: Fri Apr 06, 2007 2:44 pm
by Khaled_912
but wouldn't the sqrt of a bignum need to be calculated using binary search as well ?? do u know an efficient implementation for calculating the sqrt of a bignum?? I've seen some algorithms such as "pell's equation", but binary search proves to be much faster...
Posted: Fri Apr 06, 2007 2:47 pm
by Erik
Hi,
I implemented binary search but did not get TLE.
Maybe your big-num functions aren't efficient enough?
Cu, Erik
Posted: Sat Apr 07, 2007 7:06 pm
by Khaled_912
any test cases plzz ??
Posted: Sat Apr 07, 2007 11:35 pm
by Jan
Try the cases...
Input:
Code: Select all
211709921225737426682900
348983400808580771
2946876997361
*
Hope these help.
Re: 11114 - Polygon Encoder
Posted: Mon Jun 20, 2011 3:57 pm
by kspilario
The problem should have stated that the points calculated after decoding were already sorted in ccw/cw order.
I had trouble sorting them so that my area calculation would work. (Too many WAs)
re:
Posted: Mon Jul 04, 2011 3:18 am
by Viaxiavef
+1
ok
Posted: Tue Jul 12, 2011 2:01 am
by Sadragnemeant
ok