mt19937's blog

By mt19937, history, 11 months ago, In English

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.

UPD — The test cases are valid the assertion in the RTE solution fails for n=1, which probably is at Test-16 (note that I couldn't see the testcase myself in the submission link, sorry for my stupidity).

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it