Invalid testcase(s) for Problem-B from 2022-2023 ICPC, NERC, (Unrated, Online Mirror)

Revision en3, by The5threich, 2024-02-07 20:07:54

I recently encountered Problem-B BinCoin from 2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) while practicing random 2200 problems.

The problem is based on a binary rooted tree generated by the jury, and a random in-order traversal of that tree. I was sure my solution to this problem was reliable. But it seemed to RTE on test-16 (Which in these rounds is not visible). I tried several methods to circumvent the situation to no avail.

My Approach
Attempt to evade

Today I attempted to stress test my solution by generating (attached links to the sources below) random binary rooted trees, with random traversals.
While validating I mistakenly entered an even number for the number of nodes and realized it immediately.
I couldn't find any valid test case which would reliably thwart my approach.
So I went ahead and put an assertion for the input to see if the input is incorrect (number of nodes being even) by RTE.
To my surprise the system AC's my solution!
Source Codes to solution —
Runtime Error on Test — 16 — RTE
Time Limit Exceeded on Test 16 — TLE (attempting to force a solution)
Accepted — AC
Generator — Generator to Bincoin

Comparison shown in the image below:

Conclusion
The test case seems to be an invalid rooted tree, I am not sure if it was intended by the author, since the constraints don't specify that. But In my opinion, if we are to believe that all journals are valid and procedurally generated in a random fashion. The tree being valid is essential.

Tags bug report, fail in test case

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English The5threich 2024-02-10 18:37:44 217
en4 English The5threich 2024-02-08 16:30:48 6
en3 English The5threich 2024-02-07 20:07:54 8 (published)
en2 English The5threich 2024-02-07 19:59:12 3604 Tiny change: 'proach">\n...\nLet $a$,' -> 'proach">\nLet $a$,'
en1 English The5threich 2024-02-07 18:09:05 1052 Initial revision (saved to drafts)