11114 - Polygon Encoder

[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.

[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 ??

[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.

[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...

[Erik]

Hi,

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

Cu, Erik

[Khaled_912]

any test cases plzz ??

[Jan]

Try the cases...

Input:

Code: Select all

211709921225737426682900
348983400808580771
2946876997361
*

Output:

Code: Select all

16.0
50.0
3.5

Hope these help.

[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)

[Viaxiavef]

+1

[Sadragnemeant]

ok