Search found 10 matches

by gaurav2289
Sun Jan 18, 2015 4:35 am
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13188

Re: 10805 - Cockroach Escape Networks

I finally managed to get AC. For anyone else, this proved to be a great hint: "In every tree there exists a point (possibly in the ‘middle’ of some edge) such that the distance of the furthest vertex from it is exactly half the diameter of the tree." I just tried every possible such point ( includin...
by gaurav2289
Sun Jan 18, 2015 12:20 am
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13188

Re: 10805 - Cockroach Escape Networks

I cannot find the algorithm used to solve this problem. The link provided in the earlier posts is not working : http://www.cs.utexas.edu/users/yguan/pa ... node2.html

Can someone point me to the algorithm?
by gaurav2289
Sun Jan 11, 2015 4:55 am
Forum: Volume 108 (10800-10899)
Topic: 10874 - Segments
Replies: 10
Views: 4813

Re: 10874 - Segments

I am getting TLE for the below code even though I am using DP :( Can someone help me ?

Code: Select all

Removed after AC. I was using std::vector< std::vector<int> > for memoization table construction and destruction of which is too slow and results in TLE.
by gaurav2289
Tue Oct 27, 2009 2:20 pm
Forum: Volume 117 (11700-11799)
Topic: 11721 - Instant View of Big Bang
Replies: 12
Views: 6140

Re: 11721 - "Instant View of Big Bang"

@r2ro I mean the same as mentioned by jbernadas above-- * The nodes indices are between 0 and N, inclusive, not N-1. I had to add an extra node to the graph to make it work. * Also, when printing the answer, only nodes strictly lower than N should be printed, even when N belongs to a negative cycle...
by gaurav2289
Tue Oct 27, 2009 10:11 am
Forum: Volume 117 (11700-11799)
Topic: 11721 - Instant View of Big Bang
Replies: 12
Views: 6140

Re: 11721 - "Instant View of Big Bang"

@ jbernadas
My code is working for this input as well. You are right Test data is faulty. I only included nth node as well and printed only n-1 node and got AC.
Thanks for your help.
Would you like to share your approach for this problem?
by gaurav2289
Mon Oct 26, 2009 10:53 pm
Forum: Volume 117 (11700-11799)
Topic: 11721 - Instant View of Big Bang
Replies: 12
Views: 6140

11721 - Instant View of Big Bang

I tried this problem a lot number of times and getting WA. But I am unable to figure out the mistake as my code is working for all the test data I generate. Algorithm I have used is -- 1. Reverse the direction of each edge. 2. Set distance of coming to each node to 0. 3. Perform Bellman Ford. 4. Che...
by gaurav2289
Sun Oct 25, 2009 12:25 am
Forum: Bugs and suggestions
Topic: Create forum 'Volume CXVII'
Replies: 4
Views: 1816

Re: Create forum 'Volume CXVII'

Admins, Please create a forum CXVII for discussion of problems 11700-11799.
by gaurav2289
Sun Jul 12, 2009 6:31 pm
Forum: Volume 5 (500-599)
Topic: 594 - One Little, Two Little, Three Little Endians
Replies: 46
Views: 13422

Re: 594 : about negative number

Your approach is correct. Just do all calculations in unsigned int instead of long int. Modifications in your code will be-- int a1; unsigned int a,g1,g2,g3,g4,x,g; while(cin>>a1) { a=(unsigned int)a1; unsigned int c=1,m=8,num=0,num2=0,m1=32; ..rest all same cout<<a1<<" converts to "<<(int)num2<<"\n...
by gaurav2289
Tue Jul 07, 2009 5:40 pm
Forum: Volume 115 (11500-11599)
Topic: 11579 - Triangle Trouble
Replies: 20
Views: 10104

Re: 11579 - Triangle Trouble

@helloneo
Thanks for your reply. I got AC.
Earlier I was using selection sort algorithm which has complexity O(n^2). Because of that I got TLE.
Now I replaced it with O(nlogn) algorithm (c++ in-built sort algorithm) and got AC.
by gaurav2289
Tue Jul 07, 2009 3:46 pm
Forum: Volume 115 (11500-11599)
Topic: 11579 - Triangle Trouble
Replies: 20
Views: 10104

Re: 11579 - Triangle Trouble

Hi Will anyone please tell me why i am getting TLE?? I use the following algorithm- 1. Sort all the side lengths in increasing order. 2. Check all three consecutive sides in sorted order and if they form a triangle (i.e. a+b>c), calculate the area using heron's formula. 3. Print the largest area and...

Go to advanced search