## Search found 18 matches

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

### 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: 1796

### 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: 1932
Thank you!
I'm not from UCBerkeley (just studying DP)

I'm not sure what do you mean by writing: X = (x^k)x[1]x[2]..x[a]

My problem it how to use the sub-problems I mean
how D[a] depends on D[a'][b'] ?
if you can please write the recurrence
thanx...
Sun Sep 24, 2006 4:06 pm
Forum: Algorithms
Topic: NETWORK FLOW AND MINIMUM CUTS
Replies: 0
Views: 1247

### NETWORK FLOW AND MINIMUM CUTS

Given a network flow, is there a way of knowing whether
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: 1932

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

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: 4816
can you please define the network flow?
what will be the perfect matching?
Mon Sep 18, 2006 9:47 am
Forum: Algorithms
Topic: VERY CHALLENGING QUESTION OF NETWORK FLOW
Replies: 6
Views: 4816

### 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: 4816

### 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: 3817

### 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: 14034

#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: 6308

### 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: 15016

### 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: 19545

### 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: 8507

### 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.
Sun Feb 27, 2005 10:59 pm
Forum: Volume 106 (10600-10699)
Topic: 10634 - Say NO to Memorization
Replies: 18
Views: 8507

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