Kattis 挑战:电话列表，超过 4 秒时间限制，C# [英] Kattis Challenge: Phone List, 4-Second Time Limit Exceeded, C#

问题描述

使用在线自动化测试系统 Kattis，我面临的挑战是(在 C# 中)创建电话号码列表，然后找出其中任何一个是前缀还是另一个.

Using the online automated testing system Kattis, I'm challenged (in C#) with the task of creating a list of phone numbers then finding out if any of them is a prefix or another.

(参见:https://ncpc.idi.ntnu.no/ncpc2007/ncpc2007problems.pdf，任务 A)

提供答案相对容易，但无论我如何尝试，我都无法避免得到结果:超出时间限制，一些进一步的信息表明运行该程序需要 4 秒多的时间(通过自动程序).

Providing the answer was relatively easy, but no matter how I try I cannot escape getting the Result: Time Limit Exceeded, with some further information saying it took over 4 seconds to run the program (by an automated program).

我曾多次尝试从头开始重写它，并且尝试了所有可以在互联网上找到的现有建议.我发现自己完全不知道该怎么做，主要是因为最后我无法确定到底哪里出了问题.

I have tried rewriting it from scratch several times, and I've tried every existing suggestion I could find available on the internet. I find myself at a total loss at what to do, mostly because in the end I cannot be sure what is actually wrong.

此代码在类似(但未解决)thread，并没有发挥作用 - 但它是我迄今为止见过的最好的:

This code was suggested on a similar (but unresolved) thread, and did not do the magic - yet it's the finest I've seen thus far:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PhoneList
{
class Program
{
    static void Main(string[] args)
    {
        // Save number of test cases.
        var numTestCases = int.Parse(Console.ReadLine());

        // Do this for each test case.
        for (int i = 0; i < numTestCases; i++)
        {
            // Save number of phone numbers.
            var numPhoneNumbers = int.Parse(Console.ReadLine());

            // Save all phonenumbers in the list.
            var phoneNumbersList = new List<string>();
            for (int j = 0; j < numPhoneNumbers; j++)
            {
                string number = Console.ReadLine().Trim();

                // Add to list.
                phoneNumbersList.Add(number);
            }

            // Write output.
            if (phoneNumbersList.All(n => !phoneNumbersList.Except(new[] { n }).Any(o => o.StartsWith(n))))
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}
}

有什么建议吗?

推荐答案

并不总是最短和最好的就是最好的 :-) 尝试以下操作:

Not always the shortest and finest is the best :-) Try the following:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Samples
{
    class PhoneListProcessor
    {
        const int MaxCount = 10000;
        const int MaxDigits = 10;
        Dictionary<int, bool> phoneNumberInfo = new Dictionary<int, bool>(MaxCount * MaxDigits);
        public bool Process(IEnumerable<string> phoneNumbers, bool readToEnd)
        {
            phoneNumberInfo.Clear();
            using (var e = phoneNumbers.GetEnumerator())
            {
                while (e.MoveNext())
                {
                    if (Process(e.Current)) continue;
                    if (readToEnd)
                    {
                        while (e.MoveNext()) { }
                    }
                    return false;
                }
            }
            return true;
        }
        bool Process(string phoneNumber)
        {
            var phoneNumberInfo = this.phoneNumberInfo;
            int phoneCode = 0;
            int digitPos = 0;
            bool hasSuffix = true;
            while (true)
            {
                phoneCode = 11 * phoneCode + (phoneNumber[digitPos] - '0' + 1);
                bool isLastDigit = ++digitPos >= phoneNumber.Length;
                bool isPhoneNumber;
                if (hasSuffix && phoneNumberInfo.TryGetValue(phoneCode, out isPhoneNumber))
                {
                    if (isPhoneNumber || isLastDigit) return false;
                }
                else
                {
                    phoneNumberInfo.Add(phoneCode, isLastDigit);
                    if (isLastDigit) return true;
                    hasSuffix = false;
                }
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var processor = new PhoneListProcessor();
            int testCount = int.Parse(Console.ReadLine());
            for (int testIndex = 0; testIndex < testCount; testIndex++)
            {
                int count = int.Parse(Console.ReadLine());
                var numbers = Enumerable.Range(0, count).Select(_ => Console.ReadLine());
                bool readToEnd = testIndex + 1 < testCount;
                bool valid = processor.Process(numbers, readToEnd);
                Console.WriteLine(valid ? "YES" : "NO");
            }
        }
    }
}

基本上是动态构建并使用字典前缀trie的变体在任务限制和具体情况下.每个电话号码或前缀都被编码为以 11 为基数的整数，没有零(每个数字都是递增的，所以我们有 1-10，而不是 0-9)，以便将前导零的数字与没有前导零的相同数字区分开请求.

Basically what is does is building on the fly and using a variant of a dictionary prefix trie under the task constraints and specifics. Each phone number or prefix is encoded as integer number of base 11 with no zeroes (each digit is incremented, so instead of 0-9 we have 1-10) in order to distinguish numbers with leading zeroes from the same numbers without leading zeroes as requested.

这篇关于Kattis 挑战:电话列表，超过 4 秒时间限制，C#的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！