Atomic-Jellyfish's blog

By Atomic-Jellyfish, 5 months ago, In English

First of all, I'm sorry for the unreasonable difficulty. The problems are much harder than usual, so we choose 3 hours. But it seems that it didn't work :(

About the problems:

  • 1874C - Jellyfish and EVA : It seems that the out-degree of the vertex is not maximized, PersistentLife prepared it for me, but I forgot to check the data, I'm sorry for the unfairness caused to the round.

  • 1874D - Jellyfish and Miku : There are some hacks appearing in this problem. Some adjustments in the approximate solution past the problem, but there's really nothing I can do about it. Hack can only make the adjustments you need to make larger, but if you have a good approximate solution and adjust up to about $$$[-50, +50]$$$. You can pass all the test cases satisfying $$$1 \leq n \leq m \leq 3000$$$. Also, different approximate solutions have different hacks for them, we really have no way to hack all of them. But luckily, no matter what solution you use, you must know $$$ans = n + 2 \times \sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$$$, which is the most important of the problem, I support that there are more interesting and open solutions in the other half of the problem.

  • 1874E - Jellyfish and Hack : Sorry to all the participator whose constants were too large and caused TLE. We have tried that the most normal Lagrange Interpolation can get AC in this problem. $$$n=200$$$ is because $$$O(n^6)$$$ can easily pass $$$n=120$$$. And even some $$$O(n^4 \log n)$$$ solutions got AC in this problem under $$$n=200$$$. This is an awkward problem, and it is hard to find a absolutely good time limit and $$$n$$$. Maybe I should make $$$n=50$$$ and put it on Div.1 B, then swap the current Div.1 B and Div.1 C, the contest will be better for most people.

Overall, I think these aren't trashy problems, but I combine them incorrectly. My original intention was just to make the code for the problems easier. But this seems to have led that many people need a long time to give out the solution for the problems, many people are torn between multiple problems. I'll try to pay attention in the next round and keep the difficulty gap of adjacent problems in an appropriate range.

Moreover, There is a $$$O(n)$$$ solution for 1875D - Jellyfish and Mex, a $$$O(m^2)$$$ solution and a $$$O(nm \log n)$$$ solution for 1874D - Jellyfish and Miku, if you're interested, try to use Convex Hull Optimisation or "just use $$$O(\sqrt n)$$$ useful values" to solve 1875D - Jellyfish and Mex and decision monotonicity to solve 1874D - Jellyfish and Miku, It's not much harder than the solution in editorial.

Finally, here's a hard version of 1875D - Jellyfish and Mex, If you're interested you can try to solve this problem:

Statement
Tutorial
  • Vote: I like it
  • +398
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

problems about mex is quite fun. That contest is so hard but I have learned so much from it. Thank you to take time for preparing such a contest

»
5 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Can you add this blog to the contests' materials as well?

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Though the problems were hard, I enjoyed the round. Thanks for your hard work <3

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I like tough Questions because it has got something new for you to learn.