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:
dang that's a weird greedy, I gave up on greedy after trying the first ones that comes to mind lol
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).
UPD: fixed (maybe)
Wth is wrong with this B2 it's not wrth being B
My solution for Div.1 E1 should be able to solve E2 in $$$O(n+m)$$$ time beyond sort without using data structures(only need two-pointers, which should be better than std in complexity beyond sort), but the sample for E1 was too weak that it took me about $$$20$$$ minutes for debugging, which means there wasn't enough time for me to solve E2 :(
Well, to me it seems like you have some weird code (writing multiple lines into one). Not saying you cheated, just saying you had some weird code.
I think AI won't write code like this though.
Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).
Am I the only who thought we need to minimise the sum of all passengers time in D2D metro problem? Also is there any solution for my version of the problem in 2s time limit?