jbweimar
BAN USERyour code fails for the second set of coin values (12 = 2 x 6 and not 1 x 10 + 3 x 1 as your code finds).
a brute force approach would be:
for a number n, try coin with value v_i exactly floor(n/v_i) times. running time is thus
n/v1 * n/v2 * n/v3 * ... * n/v_k
so O(n^k).
this might not be optimal but it works.
take the first element from the partial order and take the projection onto the first coordinate (a, b) -> a. remember a.
continue through the list until you find (x, a), remember x. etc
after you've iterated through the whole set. repeat this process with x until the process doesn't change x. this gives you a minimal element (potentially the minimum).
add this to an array and remove x from the partial ordering (all elements of the form (x, .)). now repeat this process. until the partial ordering is empty.
it works because you're first checking where 1 goes in the permutation. then you check where 2 goes. but you only go to an new index farther or equal to the current index. this makes sure you don't double swap. the reason why the while loop always ends is because the iteration a = As[a] will always and come back to i again (in n or less iterations). you're basically iterating through the different cycles in the cycle decomposition of the permutation
- jbweimar May 05, 2014Took me 80 minutes. My method:
I start from each point in the land to go down the stream and I number a second array with basin numbers. If I hit an basin number other than the current one I reassign the basin numbers (on my way out from recursion). I also increment an array with basin counters (hash) each time I assign a basin number in this double loop. Then I sort and output.
Code:
public class Main {
public static int MAX_ELEVATION = 1000000; // maximum elevation
public static int MAX_BASINS = 1000;
public static void main ( String [] arguments ) throws IOException
{
// get user input
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
int size = Integer.parseInt(line.trim());
int [][]land = new int[size][size];
int [][]basins = new int[size][size];
int []basinCounts = new int[MAX_BASINS];
for (int i = 0; i < size; i ++) {
String elevations = reader.readLine();
String[] splitted = elevations.split("\\s+");
for (int j = 0; j < size; j ++) {
land[i][j] = Integer.parseInt(splitted[j].trim());
basins[i][j] = -1;
}
}
// walk through land and count basins
for (int i = 0; i < size; i ++) {
for (int j = 0; j < size; j ++) {
basinCounts[walkThroughBasin(i, j, 0, land, basins, size)] ++;
}
}
// sort basins
Arrays.sort(basinCounts);
for( int i = 0; i < basinCounts.length/2; ++i ) {
int temp = basinCounts[i];
basinCounts[i] = basinCounts[basinCounts.length - i - 1];
basinCounts[basinCounts.length - i - 1] = temp;
}
// output
for (int i = 0; i < currentBasin; i ++) {
System.out.print(basinCounts[i] + " ");
}
}
public static int currentBasin = 0;
public static int walkThroughBasin(int i, int j, int basin, int [][]land, int [][]basins, int size) {
if (basins[i][j] != -1)
return basins[i][j];
int vl = i > 0 ? land[i-1][j] : MAX_ELEVATION;
int vr = i < size - 1 ? land[i + 1][j] : MAX_ELEVATION;
int vu = j > 0 ? land[i][j - 1] : MAX_ELEVATION;
int vd = j < size - 1 ? land[i][j + 1] : MAX_ELEVATION;
if (vl <= vr && vl <= vu && vl <= vd && vl < land[i][j]) {
basin = walkThroughBasin(i - 1, j, basin, land, basins, size);
} else
if (vr <= vl && vr <= vu && vr <= vd && vr < land[i][j]) {
basin = walkThroughBasin(i + 1, j, basin, land, basins, size);
} else
if (vu <= vr && vu <= vl && vu <= vd && vu < land[i][j]) {
basin = walkThroughBasin(i, j - 1, basin, land, basins, size);
} else
if (vd <= vr && vd <= vu && vd <= vl && vd < land[i][j]) {
basin = walkThroughBasin(i, j + 1, basin, land, basins, size);
} else {
basins[i][j] = currentBasin;
return currentBasin ++;
}
basins[i][j] = basin;
return basin;
}
}
Found 2074 numbers total
public class Main {
public static void main ( String [] arguments )
{
int [] digits = new int[6];
int count = checkNextDigits(digits, 0, 0);
System.out.println("Found " + count + " numbers");
}
public static int checkNextDigits(int [] progress, int N, int count) {
if (N == 6) {
String number = "";
for (int i = 0; i < 6; i ++) {
number += progress[i] + ((i < 5) ? "-" : "");
}
System.out.println(number);
return count + 1;
}
for (int i = 0; i <= 9; i ++) {
if (N == 0) {
if (i > 0) {
progress[0] = i;
count = checkNextDigits(progress, 1, count);
}
} else {
int pv = progress[N - 1] == 0 ? 10 : progress[N - 1] - 1;
int cv = i == 0 ? 10 : i - 1;
if (pv == cv)
continue;
int rp = pv % 3;
int dp = pv / 3;
int rc = cv % 3;
int dc = cv / 3;
if (rp == rc || dp == dc) {
boolean occurs = false;
for (int j = 0; j < N + 1; j ++) {
if (progress[j] == i)
occurs = true;
}
if (!occurs) {
progress[N] = i;
count = checkNextDigits(progress, N + 1, count);
}
}
}
}
return count;
}
}
you misunderstood the question. the above solution works for 25, 10, 5, 1 but not for 25, 10, 6, 1 since for 12 cents your solution would be 1x10 cent and 2x1 cent whereas the optimal solution is 2x6 cents.
- jbweimar May 13, 2014