11401 - Triangle Counting
Moderator: Board moderators
11401 - Triangle Counting
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
before reading any input and @ run time i directly print
a[input] which is the correct output what to do
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![:-?](./images/smilies/icon_confused.gif)
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
![:-?](./images/smilies/icon_confused.gif)
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.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.
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
Are you dreaming right now?
http://www.dreamviews.com
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
Can anyone confirm the result for the following set:
I Get:
Thanks
Code: Select all
9
10
11
12
50
100
1000
10000
100000
Code: Select all
34
50
70
95
9500
79625
82958750
83295837500
51903307670168
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
arif_pasha,
All but last one is correct
inputoutput
All but last one is correct
input
Code: Select all
100000
Code: Select all
83329583375000
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
Hi,
I think that my algorithm is correct, but I still get WA.
Here is my source code :
I need some help ! Thanks ...
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;
}
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
Re: 11401 - Triangle Counting
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.
This may be the address of success.
Re: 11401 - Triangle Counting
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.
Code: Select all
f = i*(i-1)-(i+1)*(i-b)-b*(b-1);
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: 11401 - Triangle Counting
Thanks vai got ACC.
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
-
- Experienced poster
- Posts: 148
- Joined: Sun Jul 13, 2014 4:32 am
- Location: Rangpur, Bangladesh
Re: 11401 - Triangle Counting
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
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
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11401 - Triangle Counting
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.
The output will fit in a long long unsigned.
Check input and AC output for thousands of problems on uDebug!