## Search found 18 matches

- Tue Oct 03, 2006 5:34 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10051 - Tower of Cubes
- Replies:
**19** - Views:
**8762**

### 10051

I want to solve this problem by building a graph and running topological sort on it and then finding the longest path in the graph. now for a dense graph I get E = V^2 where V <= 6 * 500 right? (6 positions and 500 cubes maximum) so (6*500)^2 is too much space isn't? (for int array) there is another...

- Mon Sep 25, 2006 5:49 pm
- Forum: Algorithms
- Topic: CUTS CUTS CUTS
- Replies:
**1** - Views:
**1755**

### CUTS CUTS CUTS

Hi have two questions: 1. I read somewhere that if any cut in a weighted graph has only one lightest edge in every cut then the graph does NOT necessarily has a unique minumum spanning tree? does someone has an example for such a graph? 2. Is there a way of knowing whether a network flow has a uniqu...

- Mon Sep 25, 2006 8:30 am
- Forum: Algorithms
- Topic: I NEED HELP WITH DYNAMIC PROGAMMING
- Replies:
**2** - Views:
**1883**

- Sun Sep 24, 2006 4:06 pm
- Forum: Algorithms
- Topic: NETWORK FLOW AND MINIMUM CUTS
- Replies:
**0** - Views:
**1221**

### NETWORK FLOW AND MINIMUM CUTS

Given a network flow, is there a way of knowing whether

there is a unique minimum-cut?

there is a unique minimum-cut?

- Sun Sep 24, 2006 1:49 pm
- Forum: Algorithms
- Topic: I NEED HELP WITH DYNAMIC PROGAMMING
- Replies:
**2** - Views:
**1883**

### I NEED HELP WITH DYNAMIC PROGAMMING

Hi

This link has 3 questions of dynamic programming

I dont know how to solve the first question (Interleaving)

http://www.cs.berkeley.edu/~jordan/cou ... s/hw9.pdf

If someone knows please help me!

what should be the recurrence, base conditions and why?

Thanx...

This link has 3 questions of dynamic programming

I dont know how to solve the first question (Interleaving)

http://www.cs.berkeley.edu/~jordan/cou ... s/hw9.pdf

If someone knows please help me!

what should be the recurrence, base conditions and why?

Thanx...

- Mon Sep 18, 2006 1:34 pm
- Forum: Algorithms
- Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
- Replies:
**6** - Views:
**4547**

- Mon Sep 18, 2006 9:47 am
- Forum: Algorithms
- Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
- Replies:
**6** - Views:
**4547**

### The question

I'll write the question as it is in the 'Algorithm Design' book: (Chapter 7: Network flow page 428 question 22) Let M be an nxn matrix with each entry equal to either 0 or 1. Let mij denote an entry in row i and column j. A digonal entry is one of the form mij for some i. Swapping rows i and j of th...

- Fri Sep 15, 2006 5:50 pm
- Forum: Algorithms
- Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
- Replies:
**6** - Views:
**4547**

### VERY CHALLENGING QUESTION OF NETWORK FLOW

Hi all here is a a good link: http://www.cs.uiuc.edu/class/sp06/cs473g/exbook.pdf I have no idea how to solve question 3.1.11 (page 33 in the pdf file) the one with the matrice of 0-1... If somebody knows what network flow should be constructed please help me P.S: 3.1.12 (Unique cut) I have no idea ...

- Tue Oct 25, 2005 6:30 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10074 - Take the Land
- Replies:
**21** - Views:
**3577**

### 10074 - WA

Hi!!!! I have no idea why i get WA!! the algorithm I use goes like this: every two points (r1, c1) and (r2, c2) define exactly one rectangle if and only if r1 != r2 and c1 != c2 (its easy to figure this out) In my program r1 < r2 and c1 < c2 now the scanning goes like this: I check all the possible ...

- Fri Aug 19, 2005 10:05 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10069 - Distinct Subsequences
- Replies:
**26** - Views:
**11566**

### 10069 - Distinct Subsequences i get WA please help me here

#include <stdio.h> #include <string.h> #define MMAX 100 /* max size of Z */ #define NMAX 10000 /* max size of X */ #define MAXSIZE 100 /* max size of bignum* */ char Z[MMAX + 1]; char X[NMAX + 1]; unsigned int zlen; unsigned int xlen; typedef struct { char digit[MAXSIZE]; unsigned int digitNum; } b...

- Thu Jul 28, 2005 5:24 pm
- Forum: Volume 8 (800-899)
- Topic: 806 - Spatial Structures
- Replies:
**5** - Views:
**6177**

### 806 - Spatial Structures

#include <stdio.h> #define MAXN 64 #define white 0 #define black 1 typedef int color; color pixel[MAXN][MAXN]; /* for storing the image */ long sequence[MAXN * MAXN + 1]; char line[MAXN + 1]; /* for reading the input */ unsigned int size; /* saves the size of the sequence */ int n; /* size of the s...

- Wed Jul 27, 2005 3:24 pm
- Forum: Volume 8 (800-899)
- Topic: 871 - Counting Cells in a Blob
- Replies:
**27** - Views:
**14605**

### 871 - Counting Cells in a Blob

#include <stdio.h> #include <string.h> #define MAXN 25 typedef enum {WHITE = 0, BLACK = 1} color; int m; /* rows */ int n; /* cols */ color cell[MAXN][MAXN]; int visited[MAXN][MAXN]; void init() { int i, j; for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { visited[i][j] = 0; } } } int inLimit(int i...

- Wed Mar 02, 2005 7:02 pm
- Forum: Volume 8 (800-899)
- Topic: 855 - Lunch in Grid City
- Replies:
**41** - Views:
**19193**

### 855 - WA

#include <stdio.h> #define MAXN 1000 int median(int a[], int n) /* a[i] <= MAX_VAL */ { int i, sum, m; sum = 0; i = 1; m = (n % 2 == 0 ? (n / 2 - 1) : n / 2); while (sum < m) { sum += a[i]; i++; } return i; } void init(int a[], int n) { int i; for(i = 1; i <= n; i++) a[i] = 0; } int main() { int y[...

- Tue Mar 01, 2005 4:27 pm
- Forum: Volume 106 (10600-10699)
- Topic: 10634 - Say NO to Memorization
- Replies:
**18** - Views:
**8378**

### I still get WA

i tried unsigned long long and still got WA

i don't have a clue why i get WA!

it seems to work fine on my computer.

please try to help me here.

i don't have a clue why i get WA!

it seems to work fine on my computer.

please try to help me here.

- Sun Feb 27, 2005 10:59 pm
- Forum: Volume 106 (10600-10699)
- Topic: 10634 - Say NO to Memorization
- Replies:
**18** - Views:
**8378**

### 10634

Here is my code: #include <stdio.h> #define MAXN 1000 int main() { unsigned long f[MAXN + 1]; /* f[n] = f(n, v) */ int n, v; int i, start; while (1) { scanf("%d %d", &n, &v); if ((n == 0) && (v == 0)) break; f[0] = 1; f[1] = (unsigned long)v; start = (n % 2 == 0 ? 0 : 1); for(i = start; i <= n - 2; ...