## Search found 10 matches

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?
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.
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?
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...
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...
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.
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...
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
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...
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?