ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1002. Phone Numbers

Running time of my C# algorithm
Posted by dark_ai 30 Sep 2009 01:05
My C# Algorithm, error on Test 5 "Time limit exceeded". Help me make it faster. My email dark4ai@gmail.com

using System;
using System.Collections.Generic;

namespace timus1002
{
    public class Word
    {
        public int wordscount = 0;
        public int[] strs;
    }
    class Program
    {
        public static Dictionary<char, char[]> rules = new Dictionary<char, char[]>(10);
        public static string[] strings = new string[16];
        static bool TestWord(string word, string number)
        {
            if (number.Length < word.Length)
                return false;

            for (int i = 0; i < word.Length; i++)
                if (Array.IndexOf<char>(rules[number[i]],word[i])==-1)
                    return false;
            return true;
        }
        static Word TestNumber(string number, string[] dictionary, int min, int[] stros)
        {
            Word[] words = new Word[dictionary.Length];
            int m = dictionary.Length + 1;
            int mi = -1;
            for (int i = 0; i < dictionary.Length;i++)
            {
                int[] resu = new int[stros.Length + 1];
                for (int f = 0; f < resu.Length - 1; f++)
                    resu[f] = stros[f];
                resu[resu.Length - 1] = i;
                if (TestWord(dictionary[i], number))
                {
                    if (dictionary[i].Length == number.Length)
                    {
                        Word result = new Word();
                        result.strs = resu;
                        result.wordscount = min + 1;
                        words[i] = result;
                    }
                    else
                    {
                        words[i] = TestNumber(number.Substring(dictionary[i].Length), dictionary, min + 1, resu);
                    }
                    if (words[i] != null && words[i].wordscount < m)
                    {
                        m = words[i].wordscount;
                        mi = i;
                    }
                }
            }
            if (mi >= 0)
                return words[mi];
            return null;
        }
        static void Main(string[] args)
        {
            rules.Add('0', new char[]{ 'o', 'q', 'z' });
            rules.Add('1', new char[]{ 'i', 'j' });
            rules.Add('2', new char[]{ 'a', 'b', 'c' });
            rules.Add('3', new char[]{ 'd', 'e', 'f' });
            rules.Add('4', new char[]{ 'g', 'h'});
            rules.Add('5', new char[]{ 'k', 'l'});
            rules.Add('6', new char[]{ 'm', 'n'});
            rules.Add('7', new char[]{ 'p', 'r', 's' });
            rules.Add('8', new char[]{ 't', 'u', 'v' });
            rules.Add('9', new char[]{ 'w', 'x', 'y' });
            string end;
            while (true)
            {
                end = Console.ReadLine();
                if (end.Length != 2 && end != "-1")
                {
                    int numbers = int.Parse(Console.ReadLine());
                    string[] dictionary = new string[numbers];
                    for (int i = 0; i < numbers; i++)
                        dictionary[i] = Console.ReadLine();
                    Word res = TestNumber(end, dictionary, 0, new int[0]);
                    if (res == null)
                        Console.WriteLine("No solution.");
                    else
                    {
                        string result = dictionary[res.strs[0]];
                        for(int k =1;k<res.strs.Length;k++)
                            result+=" "+dictionary[res.strs[k]];
                        Console.WriteLine(result);
                    }
                }
                else break;
            }
            Console.Read();
        }
    }
}
Re: Running time of my C# algorithm
Posted by Oleg Strekalovsky aka OSt [Vologda SPU] 30 Sep 2009 21:45
I think, it's not problem of C#. It's problem of your algorithm :)