На последнем educational round была задача E что разделена на 2 подзадачи. Решив первую я понял что она по сложности выполнения проходит и вторую подзадачу. Тогда мне стало интересно кто не решил вторую часть и какая у них идея. Посмотрев пару кодов, я понял что идея у них как у меня и отправив 4 из них, 3 получили accept на E2, хотя участники даже не пытались решить E2. еще посмотрев я увидел точно такой же коду этого участника и у еще одного, но забыл у кого именно. Выборка у меня была 200-400 места из таблицы результатов.
Короче я хотел сказать что много серо-зеленых участников отправили E1, но не отправили E2 хотя их решение проходит все тесты на E2.
В E1 можно попытаться написать перебор за O(log(n)!)
а ема, я как-то даже не думал что на ешку могут дать просто перебор
Admins should ban everybody who passed E1, and that didn't send E2, even though they would pass.
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.