In the latest Educational Round, there was a problem E that was split into two subproblems. After solving E1, I realized that my solution can solve E2. This made me curious about the participants who hadn't solved E2 yet, and what their idea was. After looking at a few submissions, I noticed their core idea was identical to mine. I even resubmitted four of their solutions for E2—and three of them got Accepted, even though those participants hadn't even attempted E2. Looking further, I found the exact same code used by this participant and another user, though I forgot the handle of the other one. My sample size was taken from participants ranked between 200th and 400th on the leaderboard.
In short, I wanted to point out that many gray and green participants submitted E1 but didn't submit E2, even though their code passes all the tests for E2.
I agree. It seems like the intended solution is already more or less linear and there's no difficulty in having n=2000 vs n=200k.
If someone found a solution that works for n=2000 but not n=200k I would be really curious to see what it was, or what the writers' reason for splitting the problem in half was
there were a coment in Russian about solution using brute force in O(log(n)!)
brute force O(log(n)!)
can you send the link for O(log(n)!) solution?
I've heard about it from a friend, I don't have a link, but the idea is — brute force and check if the max element == n.
I was trying to find one but I don't think it exists (or at least, I wasn't good enough to see it). 11! = 40 million, and I don't think there is any way to speed up the lookup for if a permutation is valid from O(n) to O(1).
TBH if anything I feel like E1 is harder than E2 :sob: it is easier to fall into the trap of trying to find an 11! or n^2 sol
maybe if add enough continue-conditions, count of permutations that we need to check in O(1) will be much less than 11!
I thought of that, but I think it gets way too complicated very quickly.
Also, n = 1023 would kill you, since it turns out that all of them work
One of our testers found a brute-force/dp solution for E which worked for $$$n = 2000$$$, but not for $$$n = 2 \cdot 10^5$$$. He was unable to solve the full version of the problem, and we were afraid of the gap between D and E, so we decided to split the problem into two.
We also were thinking about making a version of E1 which guarantees that the input is consistent with some permutation, but decided it wasn't different enough from the full version.
I still got cooked between D <-> E1 rip
I'm curious, what was his strategy?
You can check the E1 solution in the editorial. I'll be honest, I don't understand it fully, but it's working.
I'll try to describe it when I actually understand what's going on
I am 🤡 so wrote a bitmask dp for E1. Let $$$k=\lceil\log_2 (n+1)\rceil$$$. Base idea is to assign strings from higher to lower bits. Note that the string corresponding to the highest bit must have exactly $$$n-2^{k-1}+1$$$ ones. You can show that as long as the answer is nonzero, you can disregard indices with a zero in this string (they will always produce the values $$$1\ldots2^{k-1}-1$$$). From here, I can recurse on a smaller subset of indices with the remaining strings which must produce the values $$$(2^{k-1}+)$$$ $$$0\ldots n-2^{k-1}$$$. So for every subset of strings I've assigned so far I maintain the corresponding subset of indices + values I still need to make + how many permutations are valid.
The same happened for me. I solved E1, but not E2 during the contest. Later I found that my solution to E1 was accepted in E2 as well.
It's very easy to see your submission for E1 has good time complexity to pass the E2. I see no reason why would you not submit E2 if you wrote the code yourself.