Search found 131 matches

by abishek
Fri Nov 19, 2004 3:05 pm
Forum: Algorithms
Topic: width of a POSET
Replies: 2
Views: 1134

It is dilworths (hard) theorem that the number of chains in the minimum chain decomposition is the width of the poset. that is why I asked to find this value. I realised after I posted that as the dimension of this poset in the question is 2 there may be some special way than a generalized algorithm...
by abishek
Fri Nov 19, 2004 12:47 pm
Forum: Algorithms
Topic: width of a POSET
Replies: 2
Views: 1134

width of a POSET

I would like to know of any efficient algorithm to find the width of a given partially ordered set. See for example this question in the live archive: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2322 I think the solution to this question is to find the width of the given POSET,...
by abishek
Fri Nov 12, 2004 1:25 pm
Forum: Algorithms
Topic: how to check efficiently if an edge is a BRIDGE
Replies: 9
Views: 4415

thats only to find it once right?

how do you modify this to implement fleury's algorithm?

bye
abi
by abishek
Tue Nov 09, 2004 8:47 pm
Forum: Volume 107 (10700-10799)
Topic: 10767 - Barcelona's trams
Replies: 6
Views: 2464

the function T(v, x, y) which will give the average time velocity for the xth segment with y crashes will depend on the average time for x+1 the segement and y or y+1 crashes. as none of these can be affected by this velocity, they can be assumed to be constant w.r.t this v when you differentiate. s...
by abishek
Tue Nov 09, 2004 6:17 am
Forum: Volume 107 (10700-10799)
Topic: 10753 - Exponential Function
Replies: 11
Views: 5197

I checked teh output for this case using scilab's Exp(A) function and my program the outputs matched to three decimal places. btw, I do the iterations till the entries converge to 1e-8 of their value. I also tried once by iterating 5000 times. both gave me WA. the answer from my program: 29423158354...
by abishek
Tue Nov 09, 2004 6:06 am
Forum: Algorithms
Topic: how to check efficiently if an edge is a BRIDGE
Replies: 9
Views: 4415

I am clear with the fleury algorithm. But how do I implement the idea of checking whether an edge is a bridge or not in the reduced graph? if I use DFS every time, the order will become n^2.
bye
abi
by abishek
Sun Nov 07, 2004 7:09 am
Forum: Volume 107 (10700-10799)
Topic: 10753 - Exponential Function
Replies: 11
Views: 5197

10753 - Exponential Function

though the problem has not yet come to the set, I'd like to discuss about it a bit. the problem asks for exp(A), and gives a complicated definition using Jordan cells and .... but from mathematics we also know that exp(A) = 1+A/1!+A^2/2!+.... even for matrices. So, I simply summed up that series unt...
by abishek
Wed Nov 03, 2004 9:31 pm
Forum: Algorithms
Topic: how to check efficiently if an edge is a BRIDGE
Replies: 9
Views: 4415

Never once tried the fleury's algorithm myself.
always used to merge disjoint cycles.
any body can help?
by abishek
Wed Nov 03, 2004 5:47 am
Forum: Volume 107 (10700-10799)
Topic: 10754 - Fantastic Sequence
Replies: 16
Views: 10939

Well, my AC program actually outputs -10.
by abishek
Wed Nov 03, 2004 5:45 am
Forum: Algorithms
Topic: how to check efficiently if an edge is a BRIDGE
Replies: 9
Views: 4415

hint: DFS
by abishek
Mon Nov 01, 2004 4:34 pm
Forum: C++
Topic: scanf and gets
Replies: 2
Views: 1624

Re: scanf and gets

44557FW wrote: [cpp]scanf("%[^\n]\n",a);
[/cpp]
may be it is interpreted as any string not containing a '\' and a 'n'?
by abishek
Sun Oct 31, 2004 7:35 pm
Forum: Volume 107 (10700-10799)
Topic: 10733 - The Colored Cubes
Replies: 14
Views: 4054

the answer is actually a polynomial in n. so you were lucky to get it right by fitting it with the first six values. actually, for any of these one doesnot need burnsides lemma because anyways the answers is polynomial in n and thus you can try to fit it. but try 10601, cubes. Slightly more difficul...
by abishek
Sun Oct 31, 2004 7:33 pm
Forum: Volume 107 (10700-10799)
Topic: 10754 - Fantastic Sequence
Replies: 16
Views: 10939

just an hint: Matrix multiplication
by abishek
Sun Oct 31, 2004 7:31 pm
Forum: Algorithms
Topic: Please tell me the number of problems can use polya theoerm
Replies: 2
Views: 1222

10601, 10733
by abishek
Sun Oct 31, 2004 7:43 am
Forum: Volume 107 (10700-10799)
Topic: 10755 - Garbage Heap
Replies: 20
Views: 10568

my algorithm to solve this problem is O(n^5) only. The approach is to reduce this to O(n^2) two dimensional problems and solve it in O(n^3).

Go to advanced search