This is a algorithm question, I have solution but it has performance issue.
Question Description
There are n variables and m requirements. Requirements are represented as (x <= y), which means the x-th variable must be smaller or equal to the y-th variable. Assign nonnegative numbers smaller than 10 to each variable. Please calculate how many different assignments that match all requirements. Two assignments are different if and only if at least one variable is assigned different number in these two assignment. Module the answer by 1007.
Input Format:
First line of the input contains two integers n and m. Then following m lines each containing 2 space-seperated integers x and y, which means a requirement (x <= y).
Output Format:
Output the answer in one line.
Constraints:
0 < n < 14
0 < m < 200
0 <= x, y < n
Sample Input:
6 7
1 3
0 1
2 4
0 4
2 5
3 4
0 2
Sample Output:
1000
Below is my solution. it takes too long time get result when n=13 and m=199 but the acceptable time is 5 seconds.
So can anyone think of a better way to optimize this further? Thank you.
My current solution:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication81
{
class Program
{
const int N = 10;
static List<Condition> condition = new List<Condition>();
static void Main(string[] args)
{
string[] line1 = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
int n = int.Parse(line1[0]);
int m = int.Parse(line1[1]);
for (int i = 0; i < m; i++)
{
string[] line = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
condition.Add(new Condition()
{
X = int.Parse(line[0]),
Y = int.Parse(line[1])
});
}
//
List<int[]> rlist = new List<int[]>();
for (int j = 0; j < N; j++)
{
int[] assignments = new int[n];
for (int i = 0; i < n; i++)
assignments[i] = -1;
assignments[0] = j;
rlist.Add(assignments);
}
for (int j = 1; j < n; j++)
{
List<int[]> rlist2 = new List<int[]>(rlist.Count*5);
for (int k = 0; k < rlist.Count; k++)
{
for (int l = 0; l < N; l++)
{
rlist[k][j] = l;
if (CanPassCondition(rlist[k]))
rlist2.Add((int[])rlist[k].Clone());
}
}
rlist = rlist2;
}
Console.Write(rlist.Count % 1007);
}
private static bool CanPassCondition(int[] p)
{
foreach (var c in condition)
{
if (p[c.X] == -1 || p[c.Y] == -1)
continue;
if (p[c.X] > p[c.Y])
return false;
}
return true;
}
}
class Condition
{
public int X;
public int Y;
public override string ToString()
{
return string.Format("x:{0}, y:{1}", X, Y);
}
}
}
Optimization is a program transformation technique, which tries to improve the code by making it consume less resources (i.e. CPU, Memory) and deliver high speed. In optimization, high-level general programming constructs are replaced by very efficient low-level programming codes.
The compiler optimizes to reduce the size of the binary instead of execution speed. If you do not specify an optimization option, gcc attempts to reduce the compilation time and to make debugging always yield the result expected from reading the source code.
Here is a solution in Java that works quite fast for me even with n=13, m=199:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Assignments
{
private static Map <String, Long> solutions = new HashMap <String, Long> ();
private static boolean [][] constraints;
private static long solve (int n, int [] low, int [] high)
{
StringBuilder sb = new StringBuilder ();
for (int i = 0; i < n; i++)
{
sb.append (low [i]);
sb.append (high [i]);
}
String signature = sb.toString ();
Long result = solutions.get (signature);
if (result == null)
{
result = Long.valueOf (doSolve (n, low, high));
solutions.put (signature, result);
}
return result.longValue ();
}
private static long doSolve (int n, int [] low, int [] high)
{
if (n == 0) return 1;
else
{
long result = 0;
for (int i = low [n - 1]; i <= high [n - 1]; i++)
{
int [] l = new int [n - 1];
int [] h = new int [n - 1];
for (int j = 0; j < n - 1; j++)
{
l [j] = constraints [n - 1][j] ? Math.max (low [j], i) : low [j];
h [j] = constraints [j][n - 1] ? Math.min (high [j], i) : high [j];
}
result += solve (n - 1, l, h);
}
return result;
}
}
public static void main(String[] args) throws Exception
{
BufferedReader reader =
new BufferedReader (
new InputStreamReader(System.in));
String nm = reader.readLine ();
String [] pair = nm.split(" ");
int n = Integer.parseInt(pair [0]);
int m = Integer.parseInt(pair [1]);
constraints = new boolean [n][];
for (int i = 0; i < n; i++)
constraints [i] = new boolean [n];
int [] low = new int [n];
int [] high = new int [n];
for (int i = 0; i < n; i++)
high [i] = 9;
for (int i = 0; i < m; i++)
{
String ab = reader.readLine();
pair = ab.split (" ");
int a = Integer.parseInt(pair [0]);
int b = Integer.parseInt(pair [1]);
constraints [a][b] = true;
}
System.out.println(solve (n, low, high));
}
}
Actually, once you have 13 variables, you may have only 156 (13 * 12) meaningful constraints, but though.
Sample input:
13 1
3 8
Output:
5500000000000
Another sample input:
13 12
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
Output:
497420
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With