Search found 16 matches

by jvimal
Mon Jan 14, 2008 9:22 am
Forum: Volume 113 (11300-11399)
Topic: 11391 - Blobs in the Board
Replies: 10
Views: 4493

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].
by jvimal
Mon Jan 14, 2008 7:47 am
Forum: Volume 113 (11300-11399)
Topic: 11391 - Blobs in the Board
Replies: 10
Views: 4493

TLE?

Will the naive 2**16 * 8 algorithm work? It gets TLEd for me :(
by jvimal
Sat Jan 12, 2008 10:02 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 9034

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(...
by jvimal
Sat Jan 12, 2008 9:10 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 9034

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 :)
by jvimal
Sat Jan 12, 2008 8:52 pm
Forum: Volume 113 (11300-11399)
Topic: 11394 - Digit Blocks
Replies: 18
Views: 9034

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?
by jvimal
Sat Jan 12, 2008 8:45 pm
Forum: Volume 113 (11300-11399)
Topic: 11388 - GCD LCM
Replies: 18
Views: 10173

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 ...
by jvimal
Mon Jan 07, 2008 8:05 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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...
by jvimal
Mon Jan 07, 2008 4:46 am
Forum: Volume 113 (11300-11399)
Topic: 11378 - Bey Battle
Replies: 10
Views: 5297

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 ...
by jvimal
Mon Jan 07, 2008 4:40 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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.
by jvimal
Sun Jan 06, 2008 9:29 pm
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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 . ...
by jvimal
Sun Jan 06, 2008 9:11 pm
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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!
by jvimal
Sun Jan 06, 2008 8:54 pm
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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 :(
by jvimal
Sun Jan 06, 2008 11:24 am
Forum: Volume 113 (11300-11399)
Topic: 11378 - Bey Battle
Replies: 10
Views: 5297

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: "...
by jvimal
Sun Jan 06, 2008 11:22 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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....
by jvimal
Sun Jan 06, 2008 10:24 am
Forum: Volume 113 (11300-11399)
Topic: 11380 - Down Went The Titanic
Replies: 19
Views: 10091

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

Go to advanced search