UVa OJ Board

jvimal

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

jvimal

Will the naive 2**16 * 8 algorithm work? It gets TLEd for me

jvimal

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

jvimal

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

jvimal

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?

jvimal

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

jvimal

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

jvimal

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

jvimal

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.

jvimal

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

jvimal

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!

jvimal

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

jvimal

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

jvimal

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

jvimal

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

UVa OJ Board

Search found 16 matches

TLE?

Re: 11388 - GCD LCM

Re: 11380 - Down Went The Titanic