Page **1** of **2**

### 11401 - Triangle Counting

Posted: **Fri Jan 25, 2008 10:40 pm**

by **birlax**

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

Posted: **Sat Jan 26, 2008 12:22 pm**

by **jurajz**

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

Posted: **Sat Jan 26, 2008 11:28 pm**

by **andmej**

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.

Posted: **Sun Feb 17, 2008 2:29 pm**

by **arif_pasha**

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

Posted: **Sun Feb 17, 2008 6:39 pm**

by **emotional blind**

arif_pasha,

All but last one is correct

input

output

Posted: **Sun Feb 17, 2008 9:29 pm**

by **arif_pasha**

Thanks.

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

Posted: **Fri Mar 14, 2008 5:18 pm**

by **Brainless**

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

Posted: **Fri Mar 14, 2008 5:29 pm**

by **Brainless**

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

2030481550920432

Posted: **Fri Mar 14, 2008 5:38 pm**

by **Brainless**

Ok,ok ...

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

Posted: **Tue Mar 18, 2008 2:05 pm**

by **arif_pasha**

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

)

### Re: 11401 - Triangle Counting

Posted: **Tue Jan 06, 2009 10:28 am**

by **Obaida**

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

### Re: 11401 - Triangle Counting

Posted: **Tue Jan 06, 2009 3:53 pm**

by **Jan**

Check the following line...

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.

### Re: 11401 - Triangle Counting

Posted: **Wed Jan 07, 2009 7:35 am**

by **Obaida**

### Re: 11401 - Triangle Counting

Posted: **Sun Jul 27, 2014 10:59 am**

by **Shahidul.CSE**

this is an interesting problem !!

### Re: 11401 - Triangle Counting

Posted: **Mon Jul 28, 2014 8:59 pm**

by **brianfry713**

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.