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].Observer wrote:Make sure that your code do not do the calculations more than once.

## 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:
**4493**

- 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

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

- Sat Jan 12, 2008 9:10 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11394 - Digit Blocks
- Replies:
**18** - Views:
**9034**

- Sat Jan 12, 2008 8:52 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11394 - Digit Blocks
- Replies:
**18** - Views:
**9034**

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

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

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

- Mon Jan 07, 2008 4:40 am
- Forum: Volume 113 (11300-11399)
- Topic: 11380 - Down Went The Titanic
- Replies:
**19** - Views:
**10091**

Hmm, but if I do that, for this case: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.

Code: Select all

```
3 5 2
##.**
.~*~.
.....
```

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

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

- Sun Jan 06, 2008 8:54 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11380 - Down Went The Titanic
- Replies:
**19** - Views:
**10091**

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

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

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