## Search found 16 matches

Mon Jan 14, 2008 9:22 am
Forum: Volume 113 (11300-11399)
Topic: 11391 - Blobs in the Board
Replies: 10
Views: 4395
Observer wrote:Make sure that your code do not do the calculations more than once.
Yeah, I made sure of that. But, it didnt strike me that the memoization could be done on [r][c][State]. Initially I had just done [State].
Mon Jan 14, 2008 7:47 am
Forum: Volume 113 (11300-11399)
Topic: 11391 - Blobs in the Board
Replies: 10
Views: 4395

### TLE?

Will the naive 2**16 * 8 algorithm work? It gets TLEd for me
Sat Jan 12, 2008 10:02 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 8939
How could I speed up this code? I kinda dislike how I am doing it, but ... :-) #include <iostream> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; #define FOR(x,a,b) for(int x=(a); x<(b);x++) #define LET(...
Sat Jan 12, 2008 9:10 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 8939
luishhh wrote:The answer for 55 is 2, the only two possibilities are 5 and 55
okay, was wondering if the blocks are distinguishable or not
Sat Jan 12, 2008 8:52 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 8939
sohel wrote:You can apply dynamic programming on the state dp[1<<16][5];
What is the answer if the input is "55"? Is it 2 or 4?
Sat Jan 12, 2008 8:45 pm
Forum: Volume 113 (11300-11399)
Topic: 11388 - GCD LCM
Replies: 18
Views: 10041

### Re: 11388 - GCD LCM

Is it right to say that the solution doesn't exists if and only if G is not a divisor of L ? Yes. One way of proving it would be: if a = product pi ** (alpha i), b = product pi ** (beta i), then gcd = product pi ** (min(alpha i, beta i)), lcm = product pi ** (max(alpha i, beta i)). gcd must divide ...
Mon Jan 07, 2008 8:05 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939
It seems correct to me. But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell. Thanks mf, I got it AC. I just re-read my program (damn, I should do it properly next time), and the mistake I did was: for all vertices u,v: add (2u,2u+1) with vca...
Mon Jan 07, 2008 4:46 am
Forum: Volume 113 (11300-11399)
Topic: 11378 - Bey Battle
Replies: 10
Views: 5109
mmmm.. suppose you have points (0,0)....(0,4).... and (3,7).... the closest points are (0,0) and (0,4) ( if i am not so sleep :P ).... then your answer would be 4... but the correct answer is 3. Suppose you have two points on the plane, how do you get the greatest size of the squares? When you get ...
Mon Jan 07, 2008 4:40 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939
mf wrote:It seems correct to me.
But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell.
Hmm, but if I do that, for this case:

Code: Select all

``````3 5 2
##.**
.~*~.
.....
``````
I am getting an answer of 3. It should be 2.
Sun Jan 06, 2008 9:29 pm
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939
That's all correct. Okay. I tried many more, got them right. Let me explain the connections in the graph. Each cell is a vertex. With a vertex capacity for 1. # => infi 2. @ => inf 3. "." => 1 4. * => 1 5. ~ => 1 Now, create a digraph where there are connections between . and # @ . of capacity 1 . ...
Sun Jan 06, 2008 9:11 pm
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939
mf wrote:If you make and post some inputs, I can show the output of my accepted program for them.

Code: Select all

``````3 3 1
*.*
@#@
*.*
Ans: 1

1 12 1
*#*#*#*##***
Ans: 5

2 12 1
*~*~*~*~#***
..@.@@@@.@@@
Ans: 1

2 12 2
*~*~*~*##***
..@@@@@@.@@@

Ans: 4
``````
Thanks!
Sun Jan 06, 2008 8:54 pm
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939
mf wrote:Any maxflow algorithm will work.

To handle vertex capacities, just use the usual trick - split each vertex into two.
Hi, could you give some more cases?
I tried many examples... Still couldnt find the bug
Sun Jan 06, 2008 11:24 am
Forum: Volume 113 (11300-11399)
Topic: 11378 - Bey Battle
Replies: 10
Views: 5109
Actually, there was a tricky thing for me in the problem statement, i didnt realize that the square sides might not have integer coordinates. My approach is ok, and i also did the closest point idea, which showed to be easier to implement :).Thanks! gl! Eric. For this problem, would the approach: "...
Sun Jan 06, 2008 11:22 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939
Just ignore it - time doesn't matter. In this problem people can stay at the same place for any period of time and nothing bad will happen. So, you could make people move to their destinations by one person at a time, and in this scenario no two persons would ever be at an iceberg at the same time....
Sun Jan 06, 2008 10:24 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 9939

### Re: 11380 - Down Went The Titanic

What is the idea for this problem? I guess we can formulate it as a maxflow. We have both vertex capacities and edges capacities here. And, the main problem is the condition: Two people cant be on the same iceberg at the same time. How can I incorporate that condition into maxflow if there is no tim...