用语法+语义规则自动生成竞赛编程的高精度测试用例
LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming
- 通过带计数器的上下文无关文法建模输入规范的语法与语义
- 在CodeContests数据集上显著提升错误算法识别率，效果优于基线方法
- 适合需要自动化评测复杂算法的竞赛系统或学习平台使用
自动化测试用例生成（ATCG）对于评估软件可靠性至关重要，尤其在竞赛编程中，算法鲁棒性依赖于多样且准确的测试用例。然而，现有方法常无法满足复杂规格要求，或难以生成有效的边界情况，限制了其应用。本文提出带计数器的上下文无关文法（CCFG），可同时捕捉输入规格的句法与语义结构。利用微调后的CodeT5模型，将自然语言规格转换为CCFG，实现高质量测试用例的系统生成。在CodeContests数据集上的实验表明，基于CCFG的测试用例在识别错误算法方面表现更优，有效性和正确性均有显著提升。本方法为竞赛编程的自动化评估提供了一种可扩展、可靠的语法驱动框架。
原文摘要 · Abstract (English)
Automated Test Case Generation (ATCG) is crucial for evaluating software reliability, particularly in competitive programming where robust algorithm assessments depend on diverse and accurate test cases. However, existing ATCG methods often fail to meet complex specifications or generate effective corner cases, limiting their utility. In this work, we introduce Context-Free Grammars with Counters (CCFGs), a formalism that captures both syntactic and semantic structures in input specifications. Using a fine-tuned CodeT5 model, we translate natural language input specifications into CCFGs, enabling the systematic generation of high-quality test cases. Experiments on the CodeContests dataset demonstrate that CCFG-based test cases outperform baseline methods in identifying incorrect algorithms, achieving significant gains in validity and effectiveness. Our approach provides a scalable and reliable grammar-driven framework for enhancing automated competitive programming evaluations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。