11401 - Triangle Counting

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

Moderator: Board moderators

birlax
New poster
Posts: 1
Joined: Fri Jan 25, 2008 10:29 pm

11401 - Triangle Counting

Post by birlax » Fri Jan 25, 2008 10:40 pm

geting TL please help i am storing all the solution in array a[1000000]
before reading any input and @ run time i directly print

a[input] which is the correct output what to do

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Post by jurajz » Sat Jan 26, 2008 12:22 pm

I used same method as you and have AC in 0.030. My precalculation is in O(n). If you have correct answer for n, then you can get correct answer for n+1 in O(1). Try to find it. If you used big int, it is not needed, int64 (in C/C++ long long) is enough.

One warning to this problem: The input is terminated with n less then 3, not with 0 (in lot of problems, input is terminated with 0). And surely it is not 0, I have one WA because of that :-?

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Sat Jan 26, 2008 11:28 pm

jurajz wrote:If you have correct answer for n, then you can get correct answer for n+1 in O(1). Try to find it.
Thanks for the tip. I was trying to brute-force every possible solution but it was too slow. I will think in a Dynamic Programming solution now.

Also, if a moderator reads this post I would suggest him to do two things:
1) Change the title of this thread to "11401 - Triangle counting" instead of "11401" alone.
2) Open a new subforum for volume CXIV. Clearly this problem is not from Volume CXIII.

I hope my comment is not an offense for anyone.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Sun Feb 17, 2008 2:29 pm

Can anyone confirm the result for the following set:

Code: Select all

9
10
11
12
50
100
1000
10000
100000
I Get:

Code: Select all

34
50
70
95
9500
79625
82958750
83295837500
51903307670168
Thanks

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Feb 17, 2008 6:39 pm

arif_pasha,
All but last one is correct

input

Code: Select all

100000
output

Code: Select all

83329583375000

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Sun Feb 17, 2008 9:29 pm

Thanks.

For temporary variable i was using int instead of long long. that was overflowing. :oops:

Brainless
New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 pm

Post by Brainless » Fri Mar 14, 2008 5:18 pm

Hi,

I think that my algorithm is correct, but I still get WA.

Here is my source code :

Code: Select all

#include <iostream>
#include <map>
using namespace std;

typedef unsigned long ul;
typedef unsigned long long ull;
typedef long double ld;

int main()
{
	map<ul, ld> S;
	//ld S[1000001];
	ld R;
	S[3] = 0;
	S[4] = 1;
	ul b;
	for(ul n=5; n<=1000000; ++n)
	{
		b = n/2+1;
		R = n*(n-1)-(n+1)*(n-b)-b*(b-1);
		S[n] = S[n-1] + R;
	}
	ul n;
	cin >> n;
	ull res;
	while(n>=3)
	{
		if(n==0)
		{
			cout << 0 << endl;
		}
		else
		{
			res = (ull)S[n];
			cout << res << endl;
		}
		cin >> n;
	}
	
	return 0;
}
I need some help ! Thanks ...

Brainless
New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 pm

Post by Brainless » Fri Mar 14, 2008 5:29 pm

For n = 1 000 000, the output I get is :

2030481550920432

Brainless
New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 pm

Post by Brainless » Fri Mar 14, 2008 5:38 pm

Ok,ok ... :oops:

Now I got AC. The problem was on overflow of the value "b", which is not a double, but I unsigned long long ...

I submitted totally 8 times ...

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Tue Mar 18, 2008 2:05 pm

You can remove your code from the post. (don't spoil the fun to solve a problem :D)

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11401 - Triangle Counting

Post by Obaida » Tue Jan 06, 2009 10:28 am

I don't know why this is WA!!!!!!! :(

Code: Select all

mistake fixed
Last edited by Obaida on Wed Jan 07, 2009 7:38 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

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

Re: 11401 - Triangle Counting

Post by Jan » Tue Jan 06, 2009 3:53 pm

Check the following line...

Code: Select all

f = i*(i-1)-(i+1)*(i-b)-b*(b-1);
Since i, b both are normal integers so, overflow will occur if i/b is too big. So, declare i and b as 64 bit integer.
Ami ekhono shopno dekhi...
HomePage

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11401 - Triangle Counting

Post by Obaida » Wed Jan 07, 2009 7:35 am

Thanks vai got ACC. :) :) :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 11401 - Triangle Counting

Post by Shahidul.CSE » Sun Jul 27, 2014 10:59 am

this is an interesting problem !!
Last edited by Shahidul.CSE on Sat Sep 05, 2015 8:14 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11401 - Triangle Counting

Post by brianfry713 » Mon Jul 28, 2014 8:59 pm

My AC code runs each test case in constant time with O(max_n) pre-processing.
The output will fit in a long long unsigned.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 114 (11400-11499)”