Search found 51 matches

Wed Aug 13, 2008 5:42 pm
Forum: Algorithms
Topic: use Bellman ford algo. to find a negative cycle
Replies: 5
Views: 4093

Re: use Bellman ford algo. to find a negative cycle

Execute the usual Ford-Bellman Algorithm (N or N-1 iterations); also save 'parents'. Then execute one more iteration, and if some changes in dists occur on this extra iteration, than at least one negative cycle exists. Let firstchanged be any vertex, distance to which had changed. Then just go throu...
Mon Jun 16, 2008 10:48 pm
Forum: C++
Topic: use fgets
Replies: 4
Views: 2781

Re: use fgets

Why not using just a gets()?
Sat Jun 07, 2008 9:04 pm
Forum: Algorithms
Topic: Longest Increasing Subsequenc LIS
Replies: 3
Views: 1261

Re: Longest Increasing Subsequenc LIS

Let's build another dynamics. Let D , i=1..N, is a number, that is the last number of LIS of length i (if there are several such numbers, choose the smallest one; if there no LIS of such length, D = INF). The result, obviously, will be such D , that D !=INF and i is maximal. This dynamics can be eas...
Fri Jun 06, 2008 3:39 pm
Forum: Algorithms
Topic: Longest Increasing Subsequenc LIS
Replies: 3
Views: 1261

Re: Longest Increasing Subsequenc LIS

I am not sure, but I'm afraid %ld format flag may not work.
At least, I had such problems some time ago.
Thu Jun 05, 2008 3:44 pm
Forum: Off topic (General chit-chat)
Topic: How you feel when you are not solving problem?
Replies: 7
Views: 38194

Re: How you feel when you are not solving problem?

When in summer I'm preparing to go to countryside, I read statements of problems I haven't solved yet, and remember them. Of course, it's good to have a rest from solving all the year round, but in the evenings, when I have nothing to do, I'm lying and thinking about the problems. This technique is ...
Tue Jun 03, 2008 10:33 pm
Forum: Algorithms
Topic: Maximum inscribed circle in a convex polygon
Replies: 6
Views: 3808

Re: Maximum inscribed circle in a convex polygon

mf Excuse me... :oops: What a banality - an error in program... When I didn't understand algorithm correctly I wrote an "if", that should process some special case, and then I've forgotten to remove this incorrect "if". About the adjacent parallel sides - yes, I've already understood this, only my ...
Tue Jun 03, 2008 5:43 pm
Forum: Algorithms
Topic: Maximum inscribed circle in a convex polygon
Replies: 6
Views: 3808

Re: Maximum inscribed circle in a convex polygon

Yeah, I definitely have problems with understanding. For example, if we take a square ((0;0), (1;0), (1;1), (0;1)), so in heap there would be values (1,i), i=0..3, and what should we do after erasing the first edge? Its two neighbours are collinear, and it's difficult to understand, what should be d...
Tue Jun 03, 2008 1:04 pm
Forum: Algorithms
Topic: Maximum inscribed circle in a convex polygon
Replies: 6
Views: 3808

Re: Maximum inscribed circle in a convex polygon

mf Can you please check me, haven't I mistaken? Let's consider three consecutive sides. The geometric place of the two vertices while their moving is the bisector of the angle. So, to calculate the time, after the middle side with length A will transform to a point, we need to calculate a height of...
Tue Jun 03, 2008 11:05 am
Forum: Algorithms
Topic: Maximum inscribed circle in a convex polygon
Replies: 6
Views: 3808

Re: Maximum inscribed circle in a convex polygon

mf Thank you very much. Before posting my topic I've tried to search the forum, but hadn't find anything. But your post in http://online-judge.uva.es/board/viewtopic.php?f=38&t=19991 is... just like you've predicted :) mf , when I decided to post my topic, I really hoped that you will help me. Than...
Tue Jun 03, 2008 7:59 am
Forum: Algorithms
Topic: Maximum inscribed circle in a convex polygon
Replies: 6
Views: 3808

Maximum inscribed circle in a convex polygon

The problem is to find a radius of maximum inscribed circle for given convex polygon. I know two methods of solving this problem, but both of them don't fit in TL (the problem is at http://acm.sgu.ru/problem.php?contest=0&problem=332 ). Constraints are: 10000 vertices, coordinates are integer, <= 10...
Sun Apr 20, 2008 12:07 pm
Forum: Bugs and suggestions
Topic: No Forum in new UVA site ?
Replies: 6
Views: 1792

Re: No Forum in new UVA site ?

Then IMO it would be better to add to baylor's site link to this forum.
Sat Apr 19, 2008 11:50 am
Forum: Bugs and suggestions
Topic: No Forum in new UVA site ?
Replies: 6
Views: 1792

Re: No Forum in new UVA site ?

As for me, I'm sure this forum should be migrated to the new site.
I think it's rather strange when judge is on one site and forum on another.
Thu Jan 31, 2008 8:34 pm
Forum: C++
Topic: sorting using algorithm
Replies: 1
Views: 1682
Correct.
I use standard sort() always, and I never had any problems.
Mon Jan 21, 2008 11:24 pm
Forum: Bugs and suggestions
Topic: Transparency
Replies: 3
Views: 1515
My opinion:
1. yes, it would be great to have an access to my own submissions.
2. show compiler output in case of Compilation error.
Mon Jan 21, 2008 10:45 am
Forum: C++
Topic: freopen--stdin??
Replies: 7
Views: 4748
Fibonacci_Prower
Your solution doesn't work on GNU/Linux systems.
Thanks, I didn't even expect that this may not work...