I recently encountered [Problem-B BinCoin](https://codeforces.net/contest/1773/problem/B) from **2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)** while practicing random 2200 problems. <br>↵
↵
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.↵
↵
<spoiler summary="My Approach">↵
Let $a$, $b$ and $c$ be some $3$ employees then <br>↵
$bac$ or $cab$ is reliably a sub-array (at least any one of them at a time) in each journal if and only if $b$ and $c$ be leaf nodes and have a common parent $a$.↵
And there will always be at-least $1$ such triplet.↵
↵
<spoiler summary="Proof of the 'if and only if' part">↵
For $bac$ or $cab$ to be a sub-array, it is necessary that at-least one of $b$ or $c$ is a direct child of $a$ and also a leaf.<br>↵
WLOG $c$ be a direct sub-ordinate to $a$. Let's assume a case where $b$ is a child to the "non-$c$" child of $a$.<br>↵
The journal must be bourn by $a$ before anyone else. Let the journal be with $a$ initially. <br>↵
Then, consider 2 cases <br>↵
↵
<spoiler summary="Case: 1 - A sends it to c">↵
Then $c$ signs it and for our condition to happen the non-$c$ child of $a$ must not first deliver it to $b$ (probability $\frac{1}{2}$)↵
</spoiler>↵
↵
↵
<spoiler summary="Case: 2 - Does not send it to c">↵
Then the non-$c$ child must not first deliver it to $b$ (probability $\frac{1}{2}$). <br>↵
</spoiler>↵
↵
Net Probability $\frac{1}{2^{50}}$ which is extremely unlikely, other cases will require even further restrictions and will be less probable. <br>↵
</spoiler>↵
↵
So we can greedily take off such triplets and replace them by a leaf while assigning parent to the respective nodes.↵
</spoiler>↵
↵
↵
<spoiler summary="Attempt to evade">↵
I tried randomly looking for "triples" based on the above approach till a valid tree forms up, but it TLE's since always more than 1 nodes without parent assignment remain.↵
</spoiler>↵
↵
Today I attempted to stress test my solution by generating (attached links to the sources below) random binary rooted trees, with random traversals.<br>↵
While validating I mistakenly entered an even number for the number of nodes and realized it immediately.<br>↵
I couldn't find any valid test case which would reliably thwart my approach. <br>↵
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. <br>↵
To my surprise the system AC's my solution! <br>↵
Source Codes to solution — <br>↵
Runtime Error on Test — 16 — [RTE](https://pastebin.com/vZn0PRxr) <br>↵
Time Limit Exceeded on Test 16 — [TLE](https://pastebin.com/ajQVqyQ2) (attempting to force a solution) <br>↵
Accepted — [AC](https://pastebin.com/PYqz6QHT) <br>↵
Generator — [Generator to Bincoin](https://pastebin.com/32yVsf87) <br> ↵
Comparison shown in the image below:↵
↵
<br> <br>↵
**Conclusion** <br>↵
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. <br>
↵
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.↵
↵
<spoiler summary="My Approach">↵
Let $a$, $b$ and $c$ be some $3$ employees then <br>↵
$bac$ or $cab$ is reliably a sub-array (at least any one of them at a time) in each journal if and only if $b$ and $c$ be leaf nodes and have a common parent $a$.↵
And there will always be at-least $1$ such triplet.↵
↵
<spoiler summary="Proof of the 'if and only if' part">↵
For $bac$ or $cab$ to be a sub-array, it is necessary that at-least one of $b$ or $c$ is a direct child of $a$ and also a leaf.<br>↵
WLOG $c$ be a direct sub-ordinate to $a$. Let's assume a case where $b$ is a child to the "non-$c$" child of $a$.<br>↵
The journal must be bourn by $a$ before anyone else. Let the journal be with $a$ initially. <br>↵
Then, consider 2 cases <br>↵
↵
<spoiler summary="Case: 1 - A sends it to c">↵
Then $c$ signs it and for our condition to happen the non-$c$ child of $a$ must not first deliver it to $b$ (probability $\frac{1}{2}$)↵
</spoiler>↵
↵
↵
<spoiler summary="Case: 2 - Does not send it to c">↵
Then the non-$c$ child must not first deliver it to $b$ (probability $\frac{1}{2}$). <br>↵
</spoiler>↵
↵
Net Probability $\frac{1}{2^{50}}$ which is extremely unlikely, other cases will require even further restrictions and will be less probable. <br>↵
</spoiler>↵
↵
So we can greedily take off such triplets and replace them by a leaf while assigning parent to the respective nodes.↵
</spoiler>↵
↵
↵
<spoiler summary="Attempt to evade">↵
I tried randomly looking for "triples" based on the above approach till a valid tree forms up, but it TLE's since always more than 1 nodes without parent assignment remain.↵
</spoiler>↵
↵
Today I attempted to stress test my solution by generating (attached links to the sources below) random binary rooted trees, with random traversals.<br>↵
While validating I mistakenly entered an even number for the number of nodes and realized it immediately.<br>↵
I couldn't find any valid test case which would reliably thwart my approach. <br>↵
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. <br>↵
To my surprise the system AC's my solution! <br>↵
Source Codes to solution — <br>↵
Runtime Error on Test — 16 — [RTE](https://pastebin.com/vZn0PRxr) <br>↵
Time Limit Exceeded on Test 16 — [TLE](https://pastebin.com/ajQVqyQ2) (attempting to force a solution) <br>↵
Accepted — [AC](https://pastebin.com/PYqz6QHT) <br>↵
Generator — [Generator to Bincoin](https://pastebin.com/32yVsf87) <br> ↵
Comparison shown in the image below:↵
↵
<br> <br>↵
**Conclusion** <br>↵
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. <br>
