The Application of Reconstructed Trees in Collegiate Programming Contests

DOI: https://doi.org/10.62517/jnse.202417311

Author(s)

Zijie Shen, Ruixiang Li, Junping Shi*

Affiliation(s)

School of Computer Science and Engineering, Jishou University, Jishou, Hunan, China *Corresponding Author.

Abstract

In collegiate programming contests, reconstructed trees find extensive application in tackling path-edge-weight constraint problems within graphs. These trees, defined as structures where edges carry precisely unit weight, reflecting the original graph's node set, serve as potent tools. This article elucidates the methodology behind constructing reconstructed trees, primarily leveraging minimum spanning trees. Additionally, it delves into the optimization of queries employing binary lifting coupled with Lowest Common Ancestor (LCA) algorithms. By delving into specific problem instances, it discerns the multifaceted advantages inherent in employing reconstructed trees within the competitive ambiance of collegiate programming contests. Beyond merely resolving path-edge-weight constraints, these trees augment algorithmic efficiency and code comprehensibility. They furnish contestants with robust utilities and techniques, fostering enhanced performance and enabling them to navigate contests with greater adeptness, thereby contributing significantly to their competitive endeavors. Their utility extends beyond the confines of contests, finding application in diverse real-world scenarios, enriching problem-solving capabilities, and fostering a deeper understanding of graph theory concepts.

Keywords

Reconstructed Trees; Minimum Spanning Trees; Binary Lifting with Lowest Common Ancestor

References

[1] Blum J Competitive programming participation rates: an examination of trends in US ICPC regional contests. Discover Education, 2023, 2(1): 11. [2] Nadimi-Shahraki M H, Zamani H, Asghari Varzaneh Z, et al. A systematic review of the whale optimization algorithm: theoretical foundation, improvements, and hybridizations. Archives of Computational Methods in Engineering, 2023, 30(7): 4113-4159. [3] Paiva B, Manrique I, Dimopoulos M A, et al. MRD dynamics during maintenance for improved prognostication of 1280 patients with myeloma in the TOURMALINE-MM3 and-MM4 trials. Blood, 2023, 141(6): 579-591. [4] Pham T T, Nguyen L L P, Dam M S, et al. Application of edible coating in extension of fruit shelf life. Agri Engineering, 2023, 5(1): 520-536. [5] Qiao H, Wu Y X, Zhong S L, et al. Brain-inspired intelligent robotics: Theoretical analysis and systematic application. Machine Intelligence Research, 2023, 20(1): 1-18. [6] Khan S, Khan M A, Khan M, et al. Optimized feature learning for anti-inflammatory peptide prediction using parallel distributed computing. Applied Sciences, 2023, 13(12): 7059. [7] Situmorang Y M, Mansyur A. Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal. Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA), 2023, 2(2): 225-237. [8] Labbé M, Landete M, Leal M. Dendrograms, minimum spanning trees and feature selection. European Journal of Operational Research, 2023, 308(2): 555-567. [9] Wan G, Du B, Pan S, et al. Reinforcement learning based meta-path discovery in large-scale heterogeneous information networks. Proceedings of the aaai conference on artificial intelligence. 2020, 34(04): 6094-6101. [10] Shah B, Bhavsar H. Time complexity in deep learning models. Procedia Computer Science, 2022, 215: 202-210.