11

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);
        }
    }
}
4

1 に答える 1

3

これは、n = 13、m=199でも非常に高速に動作するJavaのソリューションです。

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));
    }
}

実際、13個の変数があると、意味のある制約は156（13 * 12）しかない場合がありますが、

サンプル入力：

13 1
3 8

出力：

5500000000000

別のサンプル入力：

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

出力：

497420
于 2013-02-19T07:01:47.237 に答える