11114 - Polygon Encoder

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11114 - Polygon Encoder

Post by sclo » Sun Oct 08, 2006 11:49 pm

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

Post by Khaled_912 » Thu Apr 05, 2007 6:06 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 ??

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 05, 2007 6:41 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

Post by Khaled_912 » Fri Apr 06, 2007 2:44 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:

Post by Erik » Fri Apr 06, 2007 2:47 pm

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

Post by Khaled_912 » Sat Apr 07, 2007 7:06 pm

any test cases plzz ??

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Apr 07, 2007 11:35 pm

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

Post by kspilario » Mon Jun 20, 2011 3:57 pm

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:

re:

Post by Viaxiavef » Mon Jul 04, 2011 3:18 am

+1

Sadragnemeant
New poster
Posts: 1
Joined: Thu Jun 30, 2011 9:18 pm
Location: Deutch
Contact:

ok

Post by Sadragnemeant » Tue Jul 12, 2011 2:01 am

ok

Post Reply

Return to “Volume 111 (11100-11199)”