Atomic-Jellyfish's blog

By Atomic-Jellyfish, 13 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

Full text and comments »

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

By Atomic-Jellyfish, 13 months ago, In English

1875A - Jellyfish and Undertale

Tutorial
Code

1874A - Jellyfish and Game

Tutorial
Code

1875C - Jellyfish and Green Apple

Tutorial
Code

1875D - Jellyfish and Mex

Tutorial
Code

1874B - Jellyfish and Math

Tutorial
Code

1874C - Jellyfish and EVA

Tutorial
Code

1874D - Jellyfish and Miku

Tutorial
Code

1874E - Jellyfish and Hack

Tutorial
Code

1874F - Jellyfish and OEIS

Tutorial
Code

1874G - Jellyfish and Inscryption

Tutorial
Code

Full text and comments »

  • Vote: I like it
  • +220
  • Vote: I do not like it

By Atomic-Jellyfish, 14 months ago, In English

Hello, Codeforces!

I'm pleased to invite you to Codeforces Round 901 (Div. 1) and Codeforces Round 901 (Div. 2). It starts on Sep/30/2023 17:35 (Moscow time). It also means, the National Day of China arrives during the round. Wish you a nice vacation! 🎉🎉🎉

For both divisions, you will have 3 hours to solve 7 problems.

I would like to thank:

Especially, I would like to thank errorgorn for his great contribution to the round, njwrz for providing user solutions for all the problems, Kevin114514 for making the announcement and tutorial more readable.

Finally and most importantly, I would like to thank PersistentLife for helping me with everything patiently all the time. This round can't happen without him.

The main character of the problems will be Jellyfish, a sweet little girl. 🍏🍏🍏

Score distribution:

  • Div.1: $$$500$$$ − $$$1250$$$ − $$$1500$$$ − $$$2250$$$ − $$$3000$$$ − $$$4000$$$ − $$$5000$$$

  • Div.2: $$$500$$$ − $$$1000$$$ − $$$1000$$$ − $$$1250$$$ − $$$2000$$$ − $$$2250$$$ − $$$3000$$$

Good Luck & Have Fun! 🔥🔥🔥

UPD1: Editorial is out.

UPD2: Congratulations to the winners!

first solves in Div.1
first solves in Div.2

Full text and comments »

  • Vote: I like it
  • +178
  • Vote: I do not like it