10973 - Triangle Counting

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

Moderator: Board moderators

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

Re: 10973 - Triangle Counting

Post by Hikari9 » Sat Jun 15, 2013 12:10 pm

Just a tip, especially for those who get TLE and RTE

1. A brute force O(n^3) approach can get Accepted (with use of scanf and good memory allocation)
2. Vertices in the input CAN be greater than n (check problem description)
3. You only need to count triangles up to vertex n

matheusdallrosa
New poster
Posts: 11
Joined: Fri Nov 08, 2013 11:04 pm

Re: 10973 - Triangle Counting

Post by matheusdallrosa » Sat Jan 17, 2015 11:00 am

Hikari9 wrote:Just a tip, especially for those who get TLE and RTE

1. A brute force O(n^3) approach can get Accepted (with use of scanf and good memory allocation)
2. Vertices in the input CAN be greater than n (check problem description)
3. You only need to count triangles up to vertex n
About the first item: make a linked list using new for node allocation you'll get a better time.

Post Reply

Return to “Volume 109 (10900-10999)”