Optimizing this C# algorithm

Question

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

perhaps put some logging to see if there is any unnessessary execution. Adding timing blocks to see where something is taking a long time to execute. — Valamas
– Valamas, Commented Feb 19, 2013 at 6:06
In any case even if a for-loop only is a single liner, place those damn curly brackets. — sschrass
– sschrass, Commented Feb 19, 2013 at 6:08
@JanDvorak not necessarily. I'm in the pro-curly-braces camp. But there are people that feel that code looks more concise, with less clutter, when the braces are omitted for single-liners. The designers of the language would not give this option if it were totally useless. It is ok, to express one's opinion and believes, but caution has to be exercised when an advice is given to students on the matters that are not unambiguous. At the very least merits of the both approaches have to be made known. Also it's better to avoid being rude (re: "damn curly brackets"). — Andrew Savinykh
– Andrew Savinykh, Commented Feb 19, 2013 at 6:20
@JanDvorak What i mean is power of c# is missing especially in loops. Something like this can be used to create a list instead of iterating using for loops. List<int> x = Enumerable.Repeat(value, count).ToList(); — sasikt
– sasikt, Commented Feb 19, 2013 at 6:22
@IsaacCambron this is a question from hackerrank.com. the page is here hackerrank.com/challenges/requirement — rockXrock
– rockXrock, Commented Feb 19, 2013 at 6:32

Mikhail Vladimirov · Accepted Answer · 2013-02-19 14:55:35Z

3

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:

Output:

edited Feb 19, 2013 at 14:55

answered Feb 19, 2013 at 7:01

Mikhail Vladimirov

13.9k1 gold badge40 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Анатолий Over a year ago

Hardest test is: 13 1 not 13 199. Counting of all permutations is incorrect solution for this task, as result may have value n!

Mikhail Vladimirov Over a year ago

My algorithm almost instantly returns 5500000000000 for n = 13, m = 1.

rockXrock Over a year ago

@MikhailVladimirov thank you for your answer. there are 2 good points I learnt from it. 1) store constraints in a bool array; 2) store partial answer and reuse them to avoid computing them 2nd time. PS. last line of code is hardcoded 13 which should be n and the correct answer should be moduled by 1007.

vivek.m Over a year ago

@MikhailVladimirov would be great if you add some explanation about your algorithm also

alvas Over a year ago

Given your code and this input: pastebin.com/raw/jNnDN83E the right answer is 1000 but your code outputs 25168 ;P

Collectives™ on Stack Overflow

Optimizing this C# algorithm

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related