Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the overly simplistic Div2D and the trivial Div1D(and the statements with poor readability). I think that the whole difficulty of Div1D lies in how people hack the solutions of other participants: if nobody hacks, this problem is easier than Div1C, but if somebody hacks, it becomes hard. I will explain this in more detail in the tutorial below.
2288A - Youmu Konpaku and the Duel
2288B1 - Yukari Yakumo and the Boundary Stones (Easy Version) / 2287A1 - Yukari Yakumo and the Boundary Stones (Easy Version)
2288B2 - Yukari Yakumo and the Boundary Stones (Hard Version) / 2287A2 - Yukari Yakumo and the Boundary Stones (Hard Version)
2288C - Reimu Hakurei and the Youkai
2288D - Satori Komeiji and the Metro / 2287B - Satori Komeiji and the Metro
2288E - Cirno and the Math Problem / 2287C - Cirno and the Math Problem
2287D - Patchouli Knowledge and the String
2287E1 - Marisa Kirisame and the Game (Easy Version)
My initial problem only had an $$$n \le 10^5$$$ version and an $$$n \le 500$$$ version; thanks to Error_Yuan for proposing this $$$n \le 10^4$$$ version.
The idea comes from the power level settings of some fantasy works. In many fantasy works every character has a power level, and the levels differ wildly (for example, Tier 10 is an ordinary human, while Tier 9 is a superhuman). In this setting I created this problem, so that you can see how a battle between two groups should happen in such a fantasy world, and what the best arrangement is if a group wants to defeat another group.
2287E2 - Marisa Kirisame and the Game (Hard Version)
Codex did not pass this problem during testing, which surprised me a lot.
Before reading, please go through the hints of 2287E1 - Marisa Kirisame and the Game (Easy Version), but no need read its tutorial, because what follows is completely different.
This problem was originally conceived as a two-attribute version (attack power and defense power), but I only know an $$$O(2^n)$$$ solution for it.








Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).
great A
I wonder why Um_nik didn't fucking slime you out for such terrible problemsetting
I wonder why your mother didn't fucking slime you out for such terrible words
WHY DP IN PROBLEM B
you can do greedy brute force aswell
Why $$$n \leq 10^5$$$ on multiple problems if the intended time complexity is $$$O(n)$$$ or $$$O(n \log n)$$$?
Isnt B1 just greedy? DP is a lil bit overkill
What kind of greedy solution do you have?
Im not very good at explaining stuff so im not sure if i can help you understand my approach
I simply iterate through the string S
At the current character Si
-if Si = '+', then i'd want to duplicate a stone with power 2, if there is no stone with power 2 then i will just increase a random power 1 stone by 1, making it a power 2 stone
-if Si = '-', then ill check if there exist more than one power 2 stones (because id still have atleast one power 2 stone left), and decrease that stone's power by 1, because deleting a power 1 stone makes the answer lower, if there is one (or none) power 2 stone then ill delete a power 1 stone instead, because i need a power 2 stone to duplicate more stones, and if there is no power 1 stone, then ill simply decrease the only power 2 stone left by one
If at any step there is no stones left, ill stop
Every step ill update the answer = max(answer, current stones)
We will apply all of the operations as we traverse through $$$s$$$. When we encounter a $$$+$$$, it is obviously better to use it on a $$$2$$$ rather than on a $$$1$$$ whenever possible. One useful observation is that we only really need one $$$2$$$ so that we extract the most benefit from $$$+$$$. Then the casework on '-' follows:
Of course, Greedy is possible, but initially I thought it might be too difficult, so I lowered the data range.
Is it just me or this contest is kind of weird
The time complexity of div1C's 5e4 square is absolutely absurd. I tried for an hour and a half to remove the O(logm), hoping to find special properties through mod2, but it completely failed. Why isn't this problem given a reasonable data range, such as 1e4/1s or 2e4/4s.
Maybe you can test it on your own PC first? In my PC, 1e5/3s is completely fine. The solution to this problem runs unbelievably fast. Of course. I admit that 5e4/3s is too confusing.
It doesn't seem like the correct time complexity, 5e4 seems to indicate that you need to find a way to remove this log in order to pass.
What were the problemsetters thinking?
You are not allowed to view the requested page. https://codeforces.me/contest/2288/submission/399348749
PS Why was my rating recalculated? Previously, if the first test case was not passed and no other attempts at a solution were made a participant’s status was set to "non-competitive."
really? We will fix this issue as soon as possible (maybe an hour, maybe ten minutes).
Wth is wrong with this B2 it's not wrth being B