Search found 10 matches

by pradhanp
Thu Apr 03, 2008 2:34 am
Forum: Volume 114 (11400-11499)
Topic: 11442 - Linear Diophantine Tidbits
Replies: 1
Views: 1001

11442 - Linear Diophantine Tidbits

Any hints for this one? It reduces to counting the number of lattice points in a triangle in 3-D space. How do you do that? Is there a generalisation of Pick's theorem which could be applied here?
by pradhanp
Wed Apr 02, 2008 6:08 pm
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

Re: 11446 - Where is the 'back' button?

I finally managed to get my solution accepted. However, the accepted solution gives an output of 1 on the following input:

1
7 8
0 1
1 0
2 3
3 2
1 4
3 5
4 6
5 6

The correct answer should be 2, shouldn't it?

@Yang, could you please tell me the output of your code on this case.
by pradhanp
Tue Apr 01, 2008 8:05 pm
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

Re: 11446 - Where is the 'back' button?

Would the answer for the case P=1, L=0 be 0 or 1?
by pradhanp
Tue Apr 01, 2008 9:51 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

Re: 11446 - Where is the 'back' button?

I am sorry. I misread your post. What I meant is that for those nodes in the cycles, they don't necessary need additional links even if they are roots/leaves. I don't understand that. If a vertex belongs to a cycle, then, its in-degree>=1 and out-degree>=1. Hence, if a vertex has zero in-degree(root...
by pradhanp
Tue Apr 01, 2008 9:41 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

Re: 11446 - Where is the 'back' button?

That would be true if I was considering the DAG formed by the strongly connected components. That is not the DAG in picture. In this DAG, the only vertices that remain are those which did not belong to any cycle in the original graph. There is an edge from u to v, where u and v are two vertices in t...
by pradhanp
Mon Mar 31, 2008 2:54 pm
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

I am deleting all the vertices which belong to a cycle. I am doing this on the transitive closure so that the connectivity of the other vertices is not affected.
by pradhanp
Mon Mar 31, 2008 7:48 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

The intention of my algorithm is not to make the graph strongly connected. I will try to clarify what I meant. 1) We might as well consider the graph G'(after making it a DAG, as described in my previous post). Is this correct? 2) Assuming that it is correct, we need to add atleast max(c1, c2) edges...
by pradhanp
Mon Mar 31, 2008 3:57 am
Forum: Volume 114 (11400-11499)
Topic: 11440 - Help Tomisu
Replies: 9
Views: 3606

You only need to report the answer modulo 100000007. So the product of primes being O(n!) does not matter.

Hint : Euler's totient function
by pradhanp
Mon Mar 31, 2008 2:41 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3616

11446 - Where is the 'back' button?

If I understand the problem correctly, it is asking us to find the minimum number of edges to add, so that, in the resulting graph, every vertex belongs to a cycle. I am getting WA for the following algorithm. Could someone please provide a counter? Let G be the given graph. 1) G' = transitive closu...
by pradhanp
Mon Mar 31, 2008 2:17 am
Forum: Volume 114 (11400-11499)
Topic: 11439 - Maximizing the ICPC
Replies: 4
Views: 3151

11439 - Maximizing the ICPC

Any hints on this one? One reduction is to maximum matching, which can be done with Edmonds' blossom algorithm. Is there anything simpler?

Go to advanced search