## 11114 - Polygon Encoder

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

### 11114 - Polygon Encoder

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.

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
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 ??

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
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...

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
Hi,

I implemented binary search but did not get TLE.
Maybe your big-num functions aren't efficient enough?

Cu, Erik

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
any test cases plzz ??

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases...

Input:

Code: Select all

``````211709921225737426682900
348983400808580771
2946876997361
*``````
Output:

Code: Select all

``````16.0
50.0
3.5``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage

kspilario
New poster
Posts: 3
Joined: Mon Jun 20, 2011 3:53 pm

### Re: 11114 - Polygon Encoder

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)

Viaxiavef
New poster
Posts: 1
Joined: Wed May 11, 2011 5:06 pm
Location: Italy
Contact:

+1