Hi, we hope you enjoyed our problems! For the playlist of songs used in the problem statements, click this link.
Author: MofK
Prepared by Kuroni
First solve: xiachong at 00:01
Tutorial and Implementation
Rate this problem
Author: MofK
Prepared by Kuroni
First solve: pavement at 00:05
Hint 1
Hint 2
Tutorial and Implementation
Comments from the authors
Rate this problem
Author: MofK
Prepared by Kuroni
First solve: arvindf232 at 00:11
Hint 1
Hint 2
Hint 3
Tutorial and Implementation
Rate this problem
Author: MofK
Prepared by MofK
First solve: conqueror_of_tourist at 00:14
Hint
Tutorial and Implementation
Comments from the authors
Rate this problem
Author: MofK
Prepared by MofK
First solve: DottedCalculator at 00:16
Hint
Tutorial and Implementation
Comments from the authors
Rate this problem
Author: Kuroni
Prepared by Kuroni
First solve: CeItic at 00:42
Hint 1
Hint 2
Tutorial and Implementation
Rate this problem
Author: MofK
Prepared by Kuroni
First solve: Little09_love_YCY at 00:19
Hint 1
Hint 2
Tutorial and Implementation
Rate this problem
Author: Kuroni
Prepared by Kuroni
First solve: ecnerwala at 01:34
Hint 1
Hint 2
Hint 3
Tutorial and Implementation
Rate this problem
Author: Kuroni
Prepared by Kuroni
First solve: rainboy at 02:27
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial and Implementation
Rate this problem
UPD: Added implementations.
Auto comment: topic has been updated by MofK (previous revision, new revision, compare).
tourist didnt participate in the contest yet he first solved H. ig there is some mistake
Fixed! He's too good he first solves problem he doesn't even code.
unprovedforces
D should not appear
i think it was a great problem
worst problem ever. if it was solvable using binary search or dp then it would be great problem. it was not intitutive at all
edit:- why so much downvotes ? only for saying a useless question , useless? looks like bunch of newbies got offended. hahaha, keep crying
I am deeply sorry to inform you that not all problems are solvable using binary search or dp.
Although you should have tried H, that problem is just binary search and dp :)
nice roast, upvoted
who is newbie now ?
Have u checked my id? Before saying mindless thing . I only attempt div 2 c and d this is why I am newbie
Doesn't Matter..Newbie = Newbie
he is not totally wrong
How is it not intuitive, you just had to read the problem and test cases.
bunch of newbies down voted a newbie xd
255814648 In problem C why this logic fails ? I am creating the array wich stores the count of elements smaller than curr index . Then I am greedyly choosing elements such that I only pick elements when I see very less no of smaller no ahead . Could you provide some counter test case ?
Agree
What are the more elegant solutions to G? Is it possible to explain without formulas and latex?
One would notice that symmetric polynomial is a good candidate, and you can compute the answer by it
You've just hidden the latex here XD
The rough idea is this: the game ends when some ball $$$i$$$ becomes the last ball standing by taking over ball $$$i-1$$$. Obviously only one such event can happen, thus the answer is
probability that ball i overtakes ball i-1$$$\times$$$expected time ball i overtakes ball i-1 assuming it does happen. Let $$$d_i$$$ be the distance between ball $$$i-1$$$ and ball $$$i$$$, the first factor equals to $$$\frac{d_i}{m}$$$ (see Gambler's Ruin). The second factor equals to $$$\frac{n}{2}\frac{m^2 - d_i^2}{3}$$$ (the $$$\frac{n}{2}$$$ comes from the fact that each subgame has $$$\frac{n-2}{n}$$$ probability of not progressing each second).Here is my approach (still needs some formulas): suppose the ball that remains in the end is ball i. What happens to the distance between this ball and previous ball on each step? With probability 1/n, it increases by 1. With probability 1/n, it decreases by 1. Otherwise it is unchanged.
So now we just have the following random walk: we start at point x, at each step move left with probability 50% and right with probability 50%, until we reach either 0 or m. We need to find the probability that we reach m before 0 (a classic problem, it is x/m), and the expected number of steps to do so (this is where I needed formulas, we create the obvious system of equations and solve it by elimination, but it has 10**9 equations... But it turns out the process of elimination can be computed by taking a matrix to a power). We multiply those two, then multiply by n/2 to account for steps that do not affect this ball, and sum this over all i.
Not a tester, but I found my solution to G satisfying, so I'll write it up below:
Sort the balls in order of position. We express the answer as $$$\sum_{i = 1}^n p_i e_i$$$, where $$$p_i$$$ is the probability that ball $$$i$$$ is the last ball remaining and $$$e_i$$$ is the expected time it will take for there to be only ball remaining conditional on the last ball being ball $$$i$$$.
Let $$$d_i$$$ be the distance between ball $$$i$$$ and the ball immediately before ball $$$i$$$, which we will call $$$b_i$$$. Note that the probability that ball $$$i$$$ is the last one remaining is equal to the probability that ball $$$i$$$ overtakes ball $$$b_i$$$ before $$$b_i$$$ overtakes $$$i$$$. Let $$$d_i$$$ be the distance from $$$b_i$$$ to $$$i$$$. Then we claim that $$$p_i = d_i / m$$$. The general idea is that when we move ball $$$i$$$, the value $$$d_i$$$ increases by $$$1$$$, while when we move $$$b_i$$$, $$$d_i$$$ decreases by $$$1$$$. Moving any other ball will not affect $$$d_i$$$. Thus, with each move of ball $$$i$$$ or $$$b_i$$$, $$$d_i$$$ is equally likely to increase or decrease by $$$1$$$, and we want to find the probability that $$$d_i$$$ reaches $$$m$$$ before it reaches $$$0$$$. This is a well-known result (try to prove it if you haven't seen it before!), establishing $$$p_i = d_i / m$$$.
Now we compute $$$e_i$$$. Let $$$f(x)$$$ be the expected number of times either ball $$$i$$$ or ball $$$b_i$$$ moves before ball $$$i$$$ is the only one remaining, conditional on ball $$$i$$$ being the last one left in the end, conditional on $$$d_i = x$$$. Then, when $$$d_i = x$$$ for $$$0 < x < m$$$, we have a $$$1/2$$$ chance of moving to $$$d_i = x+1$$$ and a $$$1/2$$$ chance of moving to $$$d_i = x-1.$$$ However, the probability that ball $$$i$$$ is the last one left becomes $$$\frac{x+1}{m}$$$ and $$$\frac{x-1}{m}$$$ in the two cases. Thus, the probability that we move to $$$d_i = x+1$$$ conditional on ball $$$i$$$ being the last one left is
This gives
We can prove that $f(x) = \frac{2x+1}{3} + f(x+1),$ and with $$$f(m) = 0$$$, we can compute the value of $$$f(x)$$$ for any $$$x$$$ efficiently. Then, for a given $$$d_i$$$, we have $$$e_i = \frac{n f(d_i)}{2},$$$ since in expectation we use $$$f(d_i)$$$ moves of ball $$$i$$$ and the ball immediately before $$$i$$$, and each turn we have a $$$\frac{2}{n}$$$ chance of using such a move. (Note that it's fine to assume that whether or not we use one of these two balls each round is independent from the number of turns it takes to finish the process, since using any other ball will not affect $$$d_i$$$.)
We can then sum up $$$\frac{n p_i f(d_i)}{2}$$$ to finish the problem.
I'm not sure this will be particularly comprehensible, so feel free to post questions below and I can try to answer them.
Suppose you're betting at a casino and down to your last dollar. You're going to keep betting $1 until you either have $n, or you lose everything.
Each time you bet, you flip a coin. If heads you get $1. If tails, you lose $1.
Suppose you win. Congrats! What was the chance that happened? Well, this is clearly a fair game, which means on average you gain no money. That means, if you get $n once, to "pay" for it, you'd have to end up losing everything n times.
So the chance you win is 1/(n+1). If you started with $k instead of $1, that just means each time you lose, you're giving the bank more money to pay for your win, which would make it k/(n+k).
It's unclear to me how you can think of these as independent, particularly since ball $$$b_i$$$ may be overtaken by some other ball than $$$i$$$. Are you making some sort of implicit claim about swapping $$$b_i$$$'s identity with the one that overtook it if that happens? (sort of having $$$b_i$$$ change pointer to wtv ball is right before it rn)?
Your last assumption is correct. You can think of it like this: the minigame of "can ball $$$i$$$ survive" involves ball $$$i$$$ and whatever ball right behind it in clockwise order. If at some point ball $$$b_i$$$ is overtaken by some ball $$$j$$$, it doesn't change the minigame's state, just that from that point on, we are concerned about ball $$$j$$$ instead. No matter what ball is behind it, the transition matrix is the same.
Yes, that's a good question. I am making such a claim, and letting $$$b_i$$$ be whichever ball is currently behind ball $$$i$$$. You can observe that the position of $$$b_i$$$ will not change when any ball except $$$i$$$ or the current $$$b_i$$$ is moved: even if some ball replaces $$$b_i$$$, it will have the same position as the current $$$b_i$$$, so nothing changes.
Great! I was able to come across pretty much the same solution, but really messed up my formulae, mixed up conditional and regular mathematical expectations somewhere and, as a result, failed to get Accepted.
How does one get to $$$f(x) = \frac{2x+1}{3} + f(x+1)$$$ from $$$f(x)=1+\frac{x+1}{2x}f(x+1)+\frac{x−1}{2x}f(x−1)$$$?
I wrote out $$$f(x)$$$ in terms of $$$f(x+1)$$$ for small $$$x$$$ and observed the pattern. Once you know the formula, we can substitute it in and verify that it satisfies the equations. (I'm sure there exists a more formal way to do this, but I haven't studied the formal theory especially closely.)
I think it's super important in G to note that $$$g(0)=0$$$ is a choice one needs to make since once a $$$0$$$ comes along in $$$d$$$, you normally need to take it out. It is then crucial that even if you temporarily kept it in (just for the computation of $$$h$$$), under our assumption of how $$$f$$$ looks like, $$$f(d_1\ldots d_k, 0, d_{k+1}\ldots d_{m-1})=f(d_1\ldots d_{m-1})$$$.
Thank you for the suggestion, the tutorial has been updated ❤
My solution to G:
We can note the game ends when ball $$$i$$$ reaches ball $$$i-1$$$ for any $$$i$$$. Clearly only one of these events happens and picking the other balls doesn't change anything in the distance between $$$i$$$ and $$$i-1$$$ so we can solve $$$n$$$ games that only have balls $$$i$$$ and $$$i-1$$$ separately. Our final answer is sum of (probability ball i overtakes i-1) * (expected time) for all subgames.
The problem with only two balls is known as "gambler's ruin": to solve for the expected time, you can write the markov chain equations relating the expected time in terms of the distance $$$d$$$ between the balls and solve them, but also the final result of $$$E_d = \frac13 (m^2 - d^2)$$$ is well-known and can be found online.
But why is it just (expected time for subgame) instead of (expected time for subgame conditional to this one being the game)? It doesn't seem to me that those things are independent, I would think that you kind of want to find the minimum of the end times. Like you run the n games at the same time, and once one of them has ended, you are done. So you want to find expected minimum, and it is not just the sum of (probability that i-th one is the minimum) * (expected value of i-th).
Right, but changing the way to calculate give us the same result.
I wasn't precise with my original explanation, but of course you are correct: by "expected time" I really meant "expected time for ball i to reach i-1 given that ball $$$i$$$ reaches $$$i-1$$$ before $$$i-1$$$ reaches $$$i$$$", which is what evaluates to $$$\frac{1}{3}(m^2 - d^2)$$$.
We can get away with calculating this expectation in the isolated game with only 2 balls because we know the condition "ball i reaches i-1 before i-1 reaches i" can only ever be true for one game, so taking the minimum just equals taking the value for the one game where it happens.
(The expected time for either ball $$$i$$$ to reach $$$i-1$$$ or ball $$$i-1$$$ to reach $$$i$$$ would be $$$d(m-d)$$$).
Did you actually get this to work? I'm going to be honest, I don't fully understand how we got to $$$\frac{1}{3}(m^2-d^2)$$$ because my math isn't quite good enough, but it doesn't seem to agree with samples. This submission implements what I think you are describing: 255951875
Yeah, his formula for the "expected time" part was missing a factor of $$$\frac{n}{2}$$$ — at every second, each subgame has only $$$\frac{2}{n}$$$ probability of progressing in either direction.
Is there any way to solve D without mathematics?
I solved the cases $$$n < k$$$, $$$n = k$$$ and $$$n \ge 2k - 1$$$ pretty much without math. The remaining case was $$$k + 1 \le n \le 2k - 2$$$, and, after struggling to solve it for a while, I basically gave up, made myself believe that the answer did not exist under these circumstances, and just got Accepted.
Sometimes it just hurts to prove everything before submitting.
The first 2 cases are trivial. How you can come up with the third case, and is there any intuition here?
Of course! If you immediately apply $$$p_1 = 1$$$ then Alice gets $$$n$$$ jewels which is useful for the case $$$k = n$$$. The next thing you might want to try is to take $$$p_2 = 1$$$ and $$$p_1 \in \{ 2, 3, \ldots, n\}$$$. You might notice that after the first step Alice can, and will, buy $$$\left\lfloor\frac{n}{p_1}\right\rfloor$$$ jewels. This will cost her $$$p_1\left\lfloor\frac{n}{p_1}\right\rfloor$$$ and leave her with $$$n - p_1\left\lfloor\frac{n}{p_1}\right\rfloor = n \bmod p_1$$$ coins. Then she will spend them on the cheap jewels, so it total she will have $$$\left\lfloor\frac{n}{p_1}\right\rfloor + n \bmod p_1$$$ jewels.
However, this is still a huge mess, since an expression like $$$\left\lfloor\frac{n}{p_1}\right\rfloor + n \bmod p_1$$$ is difficult to analyze. (You will have to analyze something like this if you want to prove your solution works.) To simplify your life even further, you may decide to narrow down to case when $$$\left\lfloor\frac{n}{p_1}\right\rfloor = 1$$$ — that is, $$$p_1 \le n \le 2p_1 - 1$$$. In this case everything can be easily calculated since $$$n \bmod p_1 = n - 1 \cdot p_1 = n - p_1$$$, so Alice gets $$$n - p_1 + 1$$$ jewels in total. Since you want this number to be equal to $$$k$$$, you can deduce that $$$p_1 = n - k + 1$$$. Since now you know all $$$p_i$$$'s, you only need to guarantee that $$$\left\lfloor\frac{n}{p_1}\right\rfloor$$$ is indeed equal to one — that is, $$$p_1 = n - k + 1 \le n \le 2p_1 - 1 = 2n - 2k + 1$$$. The left inequality holds automatically for any positive integer $$$k$$$ whereas the right one holds if and only if $$$n - 2k + 1 \ge 0$$$, or $$$n \ge 2k - 1$$$.
Then you can check manually that for $$$n \ge 2k - 1$$$ it indeed works to take one jewel which costs $$$p_1 = n - k + 1$$$ and then to spend the remaining $$$k - 1$$$ coins on $$$k - 1$$$ cheap jewels. However, this will not work for $$$n \le 2k - 2$$$ since the number $$$n - k + 1$$$ will be less or equal than $$$\frac{n}{2}$$$, forcing Alice to buy more than one jewel of the first type and to spend too much money.
Thanks for your explanation, which the main point here is deciding that $$$\lfloor \frac{n}{p_1} = 1 \rfloor$$$ for simplicity. I have just one more question here (just my curiosity): When you try out the case $$$\lfloor \frac{n}{p_1} \rfloor = 1$$$, do you immediately see that $$$n \leq 2 \cdot p_1 - 1$$$, or it is the result from "adjusting" the inequality? (maybe I missed some math concepts here). I saw some people actually wrote this inequality in their code, but for me, I wrote like:
$$$\left\lfloor\frac{n}{n - k + 1}\right\rfloor \ne 1$$$ is formally equivalent to $$$n \ge 2k - 2$$$, but the first way of writing is much less clear, and the second one is much more transparent, you can actually understand what is going on.
This “adjustment” is trivial, in the sense that it directly follows from the most basic rules of working with floor and ceiling (in the examples below $$$c$$$ is integer, $$$b$$$ is positive):
$$$\left\lfloor\frac{a}{b}\right\rfloor \ge c \Longleftrightarrow \frac{a}{b} \ge c \Longleftrightarrow a \ge bc$$$
$$$\left\lfloor\frac{a}{b}\right\rfloor \le c \Longleftrightarrow \frac{a}{b} < c + 1 \Longleftrightarrow a < bc + b$$$
$$$\left\lceil\frac{a}{b}\right\rceil \ge c \Longleftrightarrow \frac{a}{b} > c - 1 \Longleftrightarrow a > bc - b$$$
$$$\left\lceil\frac{a}{b}\right\rceil \le c \Longleftrightarrow \frac{a}{b} \le c \Longleftrightarrow a \le bc$$$
Thanks for your help. I've got something new to learn!
[] does mean ceil ?
G. I. F(Greatest Integer Function)
$$$[x] = \lfloor x \rfloor = \mathop{\mathrm{floor}} (x)$$$, $$$\lceil x \rceil = \mathop{\mathrm{ceil}}(x)$$$.
I solved it with a tricky binary search (https://mirror.codeforces.com/contest/1951/submission/255325555) because I wasn't able to do the math.
The main idea is to manipulate binary search so that it gives the biggest possible cost for the stall such that you still have enough coins to buy the remainder (higher cost means less jewels can be bought). There are some casework where the first cost that limits the amount of jewels bought takes away too much money for the remainder amount needed, etc)
I'm curious about the meaning of the number 60 in D. Was there any other intended solution or was the number just there to deceive people?
We didn't want people to guess the solution; also there might have been other solutions we are not aware of that uses more than $$$2$$$ and we want to accept all of them (note that performing $$$x \mod y$$$ always decreases $$$x$$$ by at least $$$2$$$ times, so any solution that doesn't use redundant stalls should always pass this constraint).
Or maybe just dont write shit guessable problems?
For the 1e9'th time, maybe have the balls to comment from your actual account?
Thanks for the insight. People have polarizing opinion on this problem, but if my problems please a single person, I will continue to make them!
Hopefully you enjoyed other problems, whoever you actually are.
Polarizing? I wonder who thought D was appropriate for its position. Write it as A with 2 instead of 60, and it would have been perfect as Div2A. Pretty sure the reaction would be different if Traktor was the author/coordinator.
I think it was fine for its spot. Maybe try solving problems instead of metagaming the solution through constraints?
I liked that problem
Who asked you?
I did, so shut up for god's sake.
Bro is dead and alive at same time lol.. Go get a life oh sorry he can't
Dude, this is a matter of taste. Many people enjoy data structure problems but I dislike them because I am very slow on them. Still, if I come across such a problem in a problemset, it is quite a poor reason for me to swear over the problem or, even worse, over the problemsetter/coordinatior. It is fine for a problem to require some knowledge, or to require to come up with something.
While it is certainly a matter of taste, I wonder what other people see as the the intended point of thinking in these programming contests.
I have always thought the "programming" in "competitive programming" means figuring out an intelligent sequence of instructions to make something happen, with the implied idea that the instructions use insights to cut out or reuse cases smarter than the most naive layout. The key part is the instructions themselves should be interesting, I want to feel proud of what I coded.
Of course, while writing
cout << (n - k + 1) << " " << 1 << endlis technically also an instruction, i think most people will agree it does not have the same feeling of giving a recipe or other day to day instruction list, and it surely is not very interesting. In my mind if a problem does not end up with a sequence of instructions that are interesting but rather it's only interesting part is based on the thinking before the instructions, it belongs in a proof-based math contest.However, it seems many have shown they believe anything with a proof backed by psuedo-checker through example is what belongs in a programming contests, and it's easier (i think lazier) to come up with these all thinking and minimal clever instruction problems.
If the thinking part is interesting, why does it only belong in a proof based math contest? its not like someone can randomly happen to stumble on such an exact idea (the D specific one atleast, i agree for E). Well maybe some people can but very very very few.
What i see in competitive programming is math but there is an easy way to be verified that indeed your solution is correct and you get instant feedback. This makes me dislike data structures on principle (but not necessarily all of them, some of them have a nice thinking component), while mathematical logical problems are much more preferred (or pretty much anything which needs you to think on the solution, and not be killed by standard methods). This isn't from being worse at data structure problems (i think i am better than average for my rating due to preparing for IOI), but rather them not being as fun.
My opinion is quite prevalent at least among high rated people, and you can see this in AGC and most problems of ARC especially.
I know your thinking is prevalent, and has generally become the accepted. However, it is unfortunate for people like me who come to programming contests looking for creating something interesting but only end up thinking for a boring end result, since it's unsatisfying as it's not what I came for, and what I think there original intention of such contests were.
It'd be nicer to me if such proof-based problems either were put in math contests or for what you wish are stated on a separate platform (eg atcoder) while other platforms maintained problems that are meant to have interesting programming (eg what i wish of cf). However, it's also not like i'm asking for cf to become a list of standard problems, it is very possible to have interesting problems with interesting codes, and as long as an entire set is not completely proof based some less interesting code is fine for fillers in moderation.
I think another thing higher rated people forget is that my line of thinking is even more common among lower rated people, and it feels insulting to end up with code that's only a few lines of if statements and outputs since they can't get to the later problems. Who expects to show that to their friends and make them interested or believe you have any skill?
"It is very possible to have interesting problems with interesting codes"
Can you provide examples? I remember liking to implement certain things even when their implementation was long, but they are very very rare. Most of the times its either annoyance or indifference.
"I think another thing higher rated people forget is that my line of thinking is even more common among lower rated people, and it feels insulting to end up with code that's only a few lines of if statements and outputs since they can't get to the later problems."
(This is not meant to be insulting, but it probably will be for some people, sorry in advance) The vocal majority naturally comes from people who have been in the community for a non trivial amount of time. This combined with the fact that they are lower rated means that their thinking skills might be somewhat weak, while they might be good at standard problems/implementation due to lots of practice of those specific things. It is natural to favour problems which will be better for you. (I know of several low rated people who have the same opinions as me though)
"Who expects to show that to their friends and make them interested or believe you have any skill?"
Not only do i expect it, i live it. Only yesterday, i was explaining D to 2-3 people after contest, and they got impressed both by the elegance of the solution and the fact that they missed the solution.
My favorite problem is BkOI11 "time is money" (i think u've seen if u done OI). The code is non-trivial and interesting but not outrageous and it is not just combining standard structures either.
Similar medium-hard ones I can find quick are cf1325E, cf1261F, COI19 "tenis", IOI18 "seats", cf1149D, CEOI17 "mousetrap", USACO22 "cow camp", BOI17 "friends", JOISC20 "constellation 3", AGC001F, BOI16 "swap", etc. Easier examples cfgym104511E, USACO19 "meetings", IOI02 "utopia", USACO23 "feb", USACO22 "searching for soulmates", NOIP18 "constructing tracks" (probably more easier examples would get my point across better, but unfortunately i don't remember many quick, maybe i'll post more later).
None of these have super long/complex code or obscure/heavy DS, but I think figuring out the code adds to the problem satisfaction. (Personally I also like problems with even heavier implement than these but perhaps they're not fit for CF.)
I don't think your statement is wrong about vocal majority (eg ppl complaining s=16), but it does not necessarily mean if they got stronger they'd appreciate such problems more (many do because they get tired of writing out ideas and associate with copying standard code ig, but i know of other stronger contestants who share my thoughts).
Were you sharing D with a group already interested in math? Many have friends that are not all math majors, and I have never had good experience getting such interested in these ideas when they can only understand general overviews but not work out details.
I'm not sure if I qualify as a "higher rated person" but I agree with your opinion completely. Also I solved ABCD by proving it and E by complete guess without checking with brute force, so I'm not a complete invalid in that kind of problem.
its not like someone can randomly happen to stumble on such an exact idea (the D specific one atleast, i agree for E). Well maybe some people can but very very very few.
While I don't think this is super relevant, I did also solve D by brute force simple constructions then proof by AC.
For what it's worth, I, the author of problem D, also share the sentiment. That was exactly why I did away with Atcoder contests long before I retire from competitive programming altogether — the process of trying to work out the solution for an hour and spending 3 minutes on coding can sometimes feel disappointing. Then "Why is problem D here?", you may ask. I think it's fair for me to provide some context around the problem:
It was first proposed seven years ago. You heard that right, it's older than 90% of all Codeforces account, and barely a year younger than Atcoder. Back in the day such brain-teasing problems were nowhere near prevalent as they are now. I never had the chance to use it since my div.2 proposal of 7 years ago didn't go through despite having all problems approved, due to lack of commitment from other authors. When invited by Kuroni to author a contest together, I finally had the chance to publish one of the very first problem I invented on my own. It had a special place in my heart, even though I have grown to dislike problems of its kind.
During the testing, some testers liked it, some didn't. I expected as much since personally I wasn't the biggest fan of the problem anymore. Its perceived difficulty also went from div.2 B to C and finally D — I felt I massively misevaluated the problem. I wanted to retract the problem and offered to create a new one, but others convinced me to keep it, and no tester, both div.1 and div.2 strength, specifically said they were unhappy with the problem being selected even though some might not like it.
Regarding the problem itself, while I understand your POV (I have been there in my 3 Atcoder contests before quitting), I still feel such problems deserve their spots in contests — it's unfair to restrict what should be called a programming problem. It saddens me that you attribute the existence of such problems to authors being lazy — at least for me and this particular problem, no, it was as much a labor of love as any of my other problem on Codeforces (and an old one at that!) which I thought would bring diversity to the problemset.
I will never in my life set more than one "Jewel" in a contest though, you have my word on that. This is my first one anyway.
Thanks for your civil discussion :)
lol, it helps me for finding solution:
Based on last sample, I tried to
When if Alice gets [k] items, how prizes need to be setted?
When if Alice gets [1, k — 1] items, how prizes need to be setted?
When if Alice gets [1, 1, k — 2] items, how prizes need to be setted?
etc.
I need to do that for 60 times and it fits time limit. And needed prizes which received by state [1, k — 1] is same as intended solution.
So very very luckily, I got CM: 255350571
Let's hope I don't fall. :)
In my case the number confused the hell out of me so I ended up unable to solve it (guess I'm just having skills issue lmao).
Also, congrats on CM.
how was abababa...baba for 10^6 characters not part of pretests for E https://mirror.codeforces.com/contest/1951/submission/255334003
It does suck when you pass the pretests but then fail the whole test cases, but in their defense that kind of solution was not intended and maybe they didn't thought it would be necessary as they provide an O(n) solution.
Can someone explain why p1 = n — k + 1 in D? It's like out of nowhere for me.
We set two stalls with price $$$p_1$$$ and $$$1$$$. We want Alice to buy a single jewel from the first stall and $$$k-1$$$ jewels from the second one. She spends $$$p_1$$$ coins at the first stall. This gives $$$n-p_1 = k-1$$$ or $$$p_1 = n-k+1$$$
Thanks a lot!!
For problem E,
Unfortunately, my dumber solution has passed. Just for 100 random positions I checked if I partitioned the string into 2 at that position, are those strings not palindrome?
This solution is in fact correct with high probability (if a string can be partitioned, there are at least $$$\frac{n}{3}$$$ such partitions, thus probability of failing is $$$\leq \frac{2}{3}^{100}$$$), so it's not exactly dumb. Congrats on the AC!
Proof by counter example : aaaaaaaaabbaaaaaaaa
Credits : jeroenodb
Schmucks. My failure then. I was so close, having tests with exactly $$$2$$$ b's and all :'D
I hacked your solution with a string of the form
aa...abaaaba...aa.Credits to jeroenodb.
In the tutorial of the problem D the authors incorrectly opened brackets, so we should check the inequality $$$2k > n + 1$$$ instead of $$$2k > n - 1$$$.
Fixed —— some negative signs unexpectedly escaped from the editorial. Thanks for reporting!
lord_vecna dulatcodes FYI
MofK ⇒ p1q−p1−2q ≥ 2 this should be -2. Please change this ...
Sharp eyes bro!!
I: I wonder whether there's a solution that provably runs in time. If $$$F(n,m)\propto n^2m$$$ when Dinic is used, then $$$m\cdot \log W\cdot n\cdot F(n+m, n+m)$$$ could be very large (maybe on the order of $$$10^{12}$$$).
Also, the time limit is rather tight, depending on the implementation. I tried submitting two different solutions, both using AtCoder's flow template and running in the intended time complexity. The slower one is 2.5x slower, and runs just under the time limit. 255377849 255377303
(and when I used my own Dinic template in the slower solution, it TLEd due to constant factor. guess I need to rewrite it :P)
There is none, but setting any other constraint would have destroyed the problem:
Apologize for the gamble, but most author solutions ran in under 2s, which was my justification for the TL.
It seems like explanation for D contains a mistake. How is this transition possible? ⇒p1q−p1−2q≥2 shouldn’t it be -2 in this inequality’s right hand side?
Awesome round
I had a solution to H that didn't involve binary search. 255380772
First, precompute for each subtree a list of the values within the subtree sorted from greatest to least. This takes $$$O(k2^k)$$$ time.
Then for each $$$t$$$, go bottom-up starting from the nodes at depth $$$t$$$. Compute for each subtree and each $$$k'$$$ in the range $$$[0, depth(\text{subtree root})]$$$ the quantity $$$dp[\text{subtree root}][k']$$$, which we define to be the maximum value $$$m$$$ for which Alice can win the subtree if she can replace $$$k'$$$ nodes in the subtree with $$$\infty$$$. For a node at depth less than $$$t$$$ with children $$$c_1$$$ and $$$c_2$$$, this is possible if there are at least $$$2^{t-depth(\text{subtree root})}-k'$$$ values in the subtree at least $$$m$$$ and there are non-negative integers $$$k_1'$$$ and $$$k_2'$$$ such that $$$dp[c_1][k_1']\ge m$$$, $$$dp[c_2][k_2']\ge m$$$, and $$$k_1'+k_2'=k'+1$$$. Computing the DP values can be done in $$$O(t2^t)$$$ time for a single $$$t$$$.
The overall time complexity is $$$O(k2^k)$$$, though the constant factor is quite poor.
I was fully confused at problem D.
.
Why is brute forcing partitions of 2 considered a dumb solution? :facepalm:
Problem E. For those who got the intuition of dividing the string in two parts but were not able to implement or think of an algo during the contest for problem E. we could just use manacher's algorithm and then we can try to divide the string in two parts at any index i for which 0...i is non palindrome and i+1...n is also non palindrome that works in O(n).I remember in contest div2 934 D there was this question which can also be solved using manacher's algo ... Upsolving or just looking at the idea helps in improving. Unpopular opinion
we dont have a solution for E in 3 cases
1 — all chars are the same 2 — chars are alternating and the string length is odd 3 — all chars are the same except for the middle char and the string length is odd (aaabaaa)
if none of these constraints is satisfied we always print the string if its not palindrome otherwise we take the first 2 chars in the first partition and the rest of the chars in the second partition if the first string is still a palindrome we take the third char from the second partition and insert it into the first partition and so on until the first string length reaches 4 then its never a palindrome after
greedy solution here 255354790
I'd like to point out that in the second and third case you mention, if strings were to be even they wouldn't be a palindrome in the first place.
i just realized
D is a little bad, just a problem for guess.
I'm going to defend my pal MofK here. I honestly think that D was among the better problems of this contest, and I solved it without guessing at all. I can understand why people would rather choose to guess the solution, but honestly, I'm very sad about that. I will try to present my thought process here, someone might learn a thing or two.
My first "observation" is that modulo is a very volatile operation, and it's very difficult to control both the quotient and the remainder. Instead, it's easier to look at modulo as a "weird" subtraction, then one way to subtract and get the right answer is to make $$$k - 1$$$ after the first move (so that you can use $$$1$$$ after that). Hence, $$$n - k + 1$$$ should be your first move.
When would this fail? It fails when modulo is not subtraction, i.e. when $$$2(n - k + 1) \le n$$$. This means $$$k$$$ is more than $$$\lceil n/2 \rceil$$$ but less than $$$n$$$, and you can convince yourself that it's impossible to get $$$k$$$ in such range (my short intuition is that such $$$k$$$ is unreachable with first move being $$$2$$$, but too small if first move is $$$1$$$).
I agree $$$60$$$ is a big question mark here, but if you try to control both aspects of the modulo operation, I think you would naturally solve the problem without any guessinng.
The problem description could include the constraint of "minimizing s", as many individuals who didn't solved this problem attribute their lack of success to their focus on the range of s. However, it's evident from the final standings that high-level participants quickly solved this problem, indicating that it has good discriminative power. In conclusion, it's a neat and interesting problem. Thank you!
Giving hints towards the solution is bad.
I like D precisely because it was presented exactly like it was. I hate people who guess how a problem will be solved by looking at constraints/samples/any other thing, and i love it when they are punished.
Jfyi, constraints written on purpose to deceive participants are stupid. Constraints could help solve a problem, whether you call it guessing or not. There are different ways to approach a problem, and seeing constraints that guide you to a solution could be one of them, it's not stupid.
skill issue
Giving hints towards an incorrect solution is far worse. Especially, when so many problems on codeforces which have an upperbound on the number of elements in the required construction give a tight upperbound. Making people waste mental energy thinking about whether a problem gives them a tight or nonsensical upperbound doesn't seem like a very good problemsetting strategy to me.
The problem could have simply been: "Find the minimum number of shops needed to be opened, if a valid construction exists" or something of the sort which would have not helped in guessing the solution.
Also, giving the incorrect hint does not prevent people from guessing. Problems like this have appeared before and most people will get desensitized to such misdirection now. Every time they encounter a problem which asks them to construct something with an upperbound on the number of elements, they will simply mentally bruteforce through all the possible functions of $$$n$$$ that the size of construction can be (typically $$$O(1), O(\log{n}), O(\sqrt{n}), n/2$$$). This will not take anyone a significantly longer time to solve the problem, so I don't see anything positive about misdirection in problem statements.
I guess Um_nik should update "Problemsetters do not write random things in statements" because they do now.
The constraint is there for a reason and it is not to deceive people; see my comment above. It is easy to dish out criticism when you are not in a position to make decisions and take responsibility for them, but asking to minimize number of stalls is not as amazing a solution as you may think, because it has very little to do with the problem nature.
As I said earlier, setting it to $$$60$$$ was to signal that we wanted to accept any solution that doesn't use redundant stalls, which you couldn't do if you asked for minimum number of stalls. You may ask "Why not set it to $$$10^5$$$ stalls then?", to which I would like to point out that making the constraint as small as possible helps us increase the number of test cases in a single test, which makes the testset stronger (fyi us setters follow a guideline that discourages having more than $$$10$$$ pretests on problem D because of huge traffic nowadays).
I have tried my best to make my case. I just want to say we hear and appreciate constructive feedback, and we only hope our voices and addresses to your concerns will not be drowned in a deluge of downvotes — unless you find them unreasonable, in which case I implore you to reply with reason as well.
Then I suppose there was nothing wrong with your intention but you clearly failed to get this message across effectively (judging by the reaction to this problem).
A simpler way to do this would have been to give no hard upperbound on the number of shops, and just say: "Construct a sequence of shops such that alice buys exactly $$$k$$$ jewels and she buys atleast one jewel in every shop". Both versions might seem trivially equivalent to you, but lower rated people see the two versions in a very different light.
On an unrelated note, please stop putting pure math problems at anything other than A or B. This is a website for algorithmic problems.
That doesn't work unfortunately. We cannot just say nothing about the constraint on $$$m$$$ and then casually give $$$t \leq 10000$$$. People would start questioning my problemsetting skills and/or sanity if such an experienced setter is apparently asking them to print a billion numbers haha
To your second point, no I would have to disagree. Math has always been part of algorithmic problem solving and will stay this way. If you think I set math problems because I am incapable of doing other topics, please find my other works on Codeforces, Kattis, and VNOJ. I will continue to set math problems and non-math problems, hopefully I have your support on this.
If you reasonably expect everyone to immediately deduce that $$$60$$$ indicates that any valid solution with no redudant shops is accepted, then why would you expect people to question your sanity when they would be expected to deduce that any valid solution with no redundant shop will take no more than $$$\log_2(n)$$$ shops?
Secondly, sure, there are some math problems which are solved by fundamentally algorithmic processes but this particular problem has almost no algorithmic thinking involved. It is purely casework. You should realise by the general opinion on codeforces about such "if else math problems" that you don't have the support of many people on such problems.
Yeah this is getting frustrating. The $$$60$$$ is there because some constraint needs to be there, it is basic statement writing common sense. And among possible candidates, $$$60$$$ makes the most sense. What about $$$2$$$? No it doesn't work, it fundamentally changes the thinking process of the contestants, making the problem a joke. What about $$$100000$$$? Then we would have 5 test cases per file and the Codeforces server crumbles from thousands of people submitting a problem with 200 tests. What about no constraint whatsoever? Seriously? How in the hell is that even an option? Find me a problem with such output format so that I can enlighten myself please.
It has never been the case that authors have to guarantee the constraints are to guide the contestants to solve the problem. That is not the constraints' purpose. You can base your approach on the constraints, sure, no one forces you not to do that, but it is not and has never been a foolproof plan. There are times it doesn't work. There is no point arguing "trash problem, I could have solved it if this constraint is lowered to $$$2$$$" because they are two entirely different problems.
I am grateful that you are actually suggesting alternatives instead of just jumping into the circlejerk, that's exactly why I have been replying to you. But you have to understand that there are conventions and guidelines we follow that are recommended by experienced and respected authors. I hear your suggestions, but you've got to learn to accept that reinventing the wheel rarely works and it is perfectly normal that I or other authors don't find your suggestions viable or better than the current alternatives. It might be arrogant of me to say this, but setting problems is something one needs to get involved to fully appreciate others' works and be more considerate in voicing criticisms. Please consider it if you are interested; I enjoyed it greatly, maybe you will, too.
Have a good day.
"Find the minimum number" thats a different problem altogether, and a much worse one.
The current one solve path : (for me) ok what is max value of k (when k != n), oh its ceil(n / 2), how to construct? ok easy enough, submit get ac
How your version will be solved : wtf minimal construction, when can you get 1? when can you get 2? ok gg.
You might think its not giving a hint, but it certainly is. It is very likely that the answer would be very small in that version because proving its not doable in like 10 operations but doable in 11 would be quite hard....
"most people will get desensitized to such misdirection now" then why the hate? nobody would care about it if they didnt guess.
Keep my name out of your f***ing mouth with such takes.
As explained above, 60 is basically infinity in this problem, because you can't have more than $$$\log_2 n$$$ active items. That's it, that's the perfect explanation of intent: you were asked to construct any solution, limit of 60 exists only because you need some limit to test the solution, and the smaller the limit, the more tests you can fit in one file.
"Problemsetters do not write random things in statements" thing stands here. 60 is not random, it is a bound on $$$\log_2 n$$$. You should think about why it is there, true. And any reasonable solver is expected to understand why it is there and that you are asked to construct any solution.
"Problemsetters do not write random things in statements" doesn't mean that every detail is there to help you solve the problem, it just means there is a reason for every (well, most) detail.
$$$n \le 24$$$ in this problem not because the expected solution is slow, but because the only possible checker is slow. $$$c_i \le 10^{7}$$$ in this problem not because it is important to the solution in any way, but to keep the answer under $$$10^{18}$$$ so it fits in long long. Those things are not random, but they don't help you either.
you have been mentioned only for comic relief
I never thought D would be so concise. My attention has always been focused on 60.
can someone please explain why DP approach fails at C for everyday a for loop can be used from 1 to maximum allowed tickets..
whats wrong with that?
Constraint for "Allowed Tickets"
oh yeah didn't check that...thankss
I think D is easier than B, i kept debugging B for an hour lol.
For me also D was easier than B/C!
Congratulations for becoming an Expert!
Thank You!
constructforces
:(
I think you can easily solve problem G if you have solved 1349D - Slime and Biscuits or 951F - Company Acquisitions before and understand the content related to potential functions.
The contest is just trash.
guessforces
Why do people hate D so much? I'm personally okay with the problem
I dislike it because it's hard to justify sitting in front of a computer when all the work is done by you and the code is just if-else casejob.
bro, that's what makes it beautiful, we're so used to trying to solve it algorithmically, thinking about algorithms, reasonings, etc. I personally love this problem because it requires paper, it teaches people who don't have paper/pen near them and don't think on paper the damage, it teaches them that cp is not just coding, otherwise, it would be named: brute-forcing every idea and algorithms until it works, which I see a lot of my friends do, cp is about thinking, creativity, having new ideas, trying on paper, and coding altogether, I've run some experiments on myself, every time I had pen in my hand and paper in front of me, even if there wasn't a math-related problem in the contest I had better performance
Thank you for fast editorial
contest is so bad :v it will be better if it does not have much trick like that
Midway doing B, i stared at the numbers, saw 727 and suddenly "WHEN YOU SEE IT" came out of my mouth. My favorite beatmap so far, thanks MofK and Kuroni for that one.
There is a game called osu!, its a game about clicking circles to the beat of a song. There is performance points (pp) for how good you played a certain song. Someone did 727pp score and it was incredible at its time. From that moment, every time someone scores 727pp score, they obliged to say "WHEN YOU SEE IT" when they see it.
wy didn't si and had to inspect element (it was at 729)
Should have used the wysi song but we went with songs of different languages so it didn't make the cut
i will turn on blue zenith next time i attempt to solve one of your problems. who's idea was that and does Kuroni know this meme?
I think he knows it better than me, considering he was former national #1 in Taiko while I was only former national #4 in Catch (totally not bragging xd)
i was playing standard and mania, no idea how we don't share any common gamemodes. i was a 5 digit in standard, but i haven't played in a long time
thanks for making me feel worthless btw, but are you the top 4 TETRIS player of your country? well i am (although that's top 3k global), totally not off-topic
Kuroni was relatively cracked at std too (I think he was in the Vietnam OWC team that one year?) I used to play every mode, even though I was garbage xdddd
Apparently bro also plays competitive tetr.io which I don't really follow, looks like some kind of tetris with no drop speed?
wth, that's all i have to say
yes, i was playing tetr.io. the main difference is that you can hard drop your pieces, which means to place in fully down instantly. the usual measure of speed is how fast you can clear 40 lines. my record is 29 seconds, which is 3.4 pieces per second (i have to brag about something too)
Ooh I see, idk whether Kuroni still plays but he did hit the highest rank (is it X?) No idea where that would place him tho. Either way the game looks too insane to me, I'm gonna stick with map staring games made for old men :)))))
WHAT DO YOU MEAN KURONI IS X (its top 500)
bruh literally better than me in everything, im outta here
Haha I do know 727. osu! always been a big part of my life (even before comp programming), although I have stepped away from playing for ranks for a while now.
I also played tetr.io and reached X :)
Alternative solution to problem E:
First eliminate the case where $$$s = a...a$$$ and $$$s = abab...aba$$$ since they don't have solution.
Then consider find first character $$$s_t$$$ ($$$s_t \neq s_1$$$) and cut off $$$s[1, t]$$$, obviously this is not a palindrome. If we keep doing it until we can't, the rest of the string is either empty or $$$s = a...a$$$.
For the first case, we are done. For the second, consider merge this string back to the last partition we make, if it is still an palindrome, it would be like $$$s = a...aba...a$$$, then just try to merge one more time, if it is still an palindrome, it would be like $$$s = a...aba...aba...a$$$, in such case, just cut this string into half and both of them won't be palindrome.
Can you please explain why the string s is reduced to only 2 characters (a, and b). Does that means that for a string containing more than 2 distinct characters there is always a solution ?
W.L.O.G. assume we merge $$$a...a$$$ back to the last partition (let's say $$$c...cb$$$).
If $$$c \neq a$$$ then it is not a palindrome and we are done, so to let this partition a palindrome we assume $$$c = a$$$, which means after the first merge this partition would be $$$a...aba...a$$$.
For the second merge, again, assume it is $$$e...ed$$$, if $$$d = a$$$ then $$$e \neq a$$$ and it won't be palindrome, if $$$d \neq a$$$ and $$$d \neq b$$$ then it still not a palindrome, and if $$$e \neq a$$$ it also won't be palindrome and we also done, so the only case we need to handle is the case mentioned above $$$(d = b, e = a)$$$ .
Ok, get it. Thanks. Now your first explanation is much clearer.
Can anyone share their intuition for C? I completely messed up my contest because I took way too long to figure C out, I was able to get AC only after I figured out the proper mathematical proof. I initially was able to figure out that we need to select $$$\lceil\frac{k}{m}\rceil$$$ days with minimum prices, but I couldn't figure out how to distribute the $$$k$$$ tickets among those days.
Initially, I came up with an idea that I can buy $$$k\mod{m}$$$ tickets on the first day and $$$m$$$ on the rest of the days because I felt that buying more tickets earlier isn't good as it'll increase the cost, it passed samples but I got WA on pretest 2. Then for a long time I couldn't really figure out how to fix this, later when I came up with the mathematical proof I realized that the $$$k\mod{m}$$$ tickets should be assigned to the largest one among the $$$\lceil\frac{k}{m}\rceil$$$ smallest elements.
I think most people wouldn't have come up with the mathematical proof for this problem, so how does one get this intuition?
You can think the extra cost as the number of pair of ticket from different group, then you can keep moving a ticket from a smaller pile to a greater pile to have less extra cost, thus the distribution should be $$$k \% m, m, m, ...$$$, and by the above rephrase, it is obvious the order doesn't matter, so you just let the $$$k \% m$$$ pile have smallest cost, and the rest have second, third, ...-smallest cost.
sir but how order does not matter as if the minimum is present at the last index then everything fails ,Sir please tell where I am thinking wrong
You can think the extra cost as the number of pair of ticket from different groupI believe this is enough to explain why the order doesn't matter.
Thank you sir
Sir can you please tell me the complete mathematical proof,Please Sir.
Dude I am not able to understand the solution for even C and D .I need to work a lot on my skills.
hello
For something like
11or01100, it is not possible because you can only turn on pairs of non-adjacent lights.yeah mb i didn't read the statement correctly instead of non-adjacent i read it adjacent
This was my submission problem B there seems to be some error in my code. 255365950
Can you help me find were the error in the code is?
(variable loss — in the code is the first position in the array where the cow loses and nwin — means wins after we swap with the first loss cow )
Ohh my bad,this is my submission — 255365950
For anyone who blames D as bad or should put it on A or B after altering the constraint from 60 to 2, I think you should blame yourself first for getting codeforces'd (me too ToT) by the "D" title. Who said that problem D can't have an easy solution just like A or B? And it requires some nice and non-trivial observations to come up with the solution (e.g. actually you just need 2 stalls) so I think that it's totally reasonable to put it in the contest.
what are the string matching algorithms mentionned in problem E for checking the string is palindrome in a fast manner
manachers algorithm, you can also use string hashing which i did during the contest
Thank u for ur answer can u explain more how by hashing we can check that the substring is palindrome ?
hashing is used for checking two string are equal or not, with this property we can check wether hash of string is equals to hash of reverse of string then string is pallindrom.
but you should use atleast two hash checks( with different parameters ) before comming to conclusion wether strings are equal or not due to collisons.
article: https://cp-algorithms.com/string/string-hashing.html
thank u so mch
thanks man, till date I never have given priority to Hash as i always used to think somebody will hack it and they will create some testcases which will cover hashing loop holes,
But I think I better start using it and solve some problems, I saw you used some Hashing template which is cool.
yeah, you should never write your hashing thing during contest, because you will commit some mistake easily, i once implemented hasing in contest took me more than 1 hour to write error free hash class, because that was my first time implementing the hash...
can some one please explain the solution to F problem?
with small test case, I am getting lost in variables in explanations.
why downvote?
I had spent 1.5 hour on C.
Can please anyone provide any similar problem to C? C is not intuitive for me at all. How to step-by-step approach C to reach to solution?
I was thinking of an approach like let's take the first couple of elements which would make K tickets, then select next and remove some previously selected days.
But the two concepts *(ordering does not matter and additional cost is independent) is not doable for me (at least at the time when I was participating in VC)
Any help appreciated , thanks.
let's take the first case and try to solve it. there $$$m = 2$$$ and $$$k = 3$$$.
The array is: $$$[8, 6, 4, 2]$$$.
You can go through the steps in the notes for how will it go in the standard way.
Let's sort it: $$$[2, 4, 6, 8]$$$.
Now at every day, we will increase the cost with the number of stuff we have bought so far and that can be easily done with the help of a count variable which we can keep track of and, before calculation, we just add that count with the initial cost. You can try this with any ordering or any thing and verify that it works.
Then, lets solve it: At $$$day_1$$$ we will take two items of cost 2 (because 2 is the limit) and after $$$every$$$ day we can't buy the same item again. So total cost, right now, is 2. Then we can increment our $$$cnt$$$ variable to $$$cnt = 2$$$. We move on. On the second position, we need only 1 purchase of that item. but we also have to increase the value so we can add $$$a_2 + cnt$$$ into the answer and this will give us $$$8$$$ which is indeed the correct answer.
so, we get the formula
I hope it cleared the doubt for you.
I understood the solution already, thanks for your explanation,
But the fact that ordering does not matter makes sense only when you know ordering does not matter.
Why would I think in the direction like, okay the ordering may not matter when the ordering actually could have mattered and it's just that I am not able to find out a way?
Can anybody tell me what is wrong with my solution for problem E.
sol link: https://mirror.codeforces.com/contest/1951/submission/255497756
apart from knowing that the answer will be equal is there any induction type prove for why sorting works? I also did it only on the basis of giving the correct answer but it would be appreciated if there was some formal mathematical proof for why sorting works.
Can I ask how the equation $$$(p_1 - 2)(q - 1) \ge 0$$$ on problem D pop up when we want to find a bound for $$$(q + r)$$$? Is there any intuition on it? For me I feel it is just a random equation come from nowhere and turns out it can bound the answer D:
Yeah I agree it's not the most intuitive way to prove the correctness. Since we are trying to bound $$$q+r$$$, maybe starting from $$$n - 2(q+r)$$$ would be better? Like this:
$$$n - 2(q+r) = (p_1 - 2)q - r$$$
$$$\geq (p_1 - 2)q - p_1 + 1$$$ (since $$$r \leq p_1 - 1$$$)
$$$\geq (p_1 - 2) - p_1 + 1$$$ (since $$$q \geq 1, p_1 \geq 2$$$)
$$$= -1$$$
Hopefully this helps!
wow, it really become more intuitive! thanks you!
Thank you as well for raising the issue — the tutorial has been updated!
how do you see the rating of the problem?
Wait some days or weeks until it's uploaded.
can someone give us a ressource for a good and clear hashing template in order to solve problem E
Can somebody help to understand editorial problem F?
For any two integers 1≤i<j≤n, let's observe the "inverseness" of (p_i,p_j) on q and (i,j) on q⋅pBut $$$(p_i, p_j)$$$ is inverse in $$$q$$$ if $$$q[p[i]] > q[p[j]]$$$. And $$$(i, j)$$$ is inverse in $$$q⋅p$$$ if $$$q[p[i]] > q[p[j]]$$$. It's just the same indexes here.
And why shouldn't we consider inversions $$$(i, j)$$$ in $$$q$$$ and $$$(p_i, p_j)$$$ in $$$q$$$?
$$$(p_i, p_j)$$$ is an inverse in $$$q$$$ if $$$q_{p_i} > q_{p_j}$$$ and $$$p_i < p_j$$$, or $$$q_{p_i} < q_{p_j}$$$ and $$$p_i > p_j$$$. I think you're just forgetting to compare the indices as well. In that sense, inversenesses of $$$(p_i, p_j)$$$ on $$$q$$$ and $$$(i, j)$$$ on $$$q \cdot p$$$ are actually different: one is relating $$$q_{p_i}$$$ and $$$q_{p_j}$$$ to $$$p_i$$$ and $$$p_j$$$, and the other is relating $$$q_{p_i}$$$ and $$$q_{p_j}$$$ to $$$i$$$ and $$$j$$$.
I don't understand the purpose of your second question. We don't have to consider those inversions right?
Thanks, I really forgot to compare indexes.
I thought that the contribution to inv($$$q$$$) for indexes $$$(i, j)$$$ is considered in the analysis, and my second question was about this. Now I understand the analysis, thanks.
The greedy idea of problem C was not intuiive to me during the contest. Can someone share any tips on how to improve on solving greedy ideas.
Clearly we'd want to choose small value if there wasn't the secondary cost. What you need to do then is separate the secondary cost to make it not depend on previous/future choices. Then you realize that the secondary cost is the number of pairs that weren't taken in the same choice. That means it's all pairs except the pairs that were taken in the same choice, so N^2 — sum of (size of choice)^2. Then it doesn't depend on the values that we take, just on how much we take in one round. From here it's trivial.
Could you please explain the equation in C
The solution to B is so vague. Like i already figured it out. Tell me something that give me a better idea. I hope someone can help me out
https://mirror.codeforces.com/contest/1951/submission/255331338
problem f hint 2: "They either contribute 0 or 1"
it may be "0 or 2"
Fixed, thanks!
Kuroni hi
antontrygubO_o had the most beautiful solution (imo) to G. He just said one line in AC server "sum of length^3 increases by 6m / n on average".
Indeed, we can verify that is correct by doing some algebra. Suppose there are currently $$$i$$$ balls still left over. Suppose that we operated on $$$x$$$ and $$$y$$$ (adjacent distances). Then, they change to $$$x - 1$$$ and $$$y + 1$$$ respectively, and the difference in sum of $$$len^3$$$ is equal to $$$(3x^2 - 3y^2) + (3x + 3y)$$$. Note that the expected value of $$$(x^2 - y^2)$$$ is $$$0$$$, while the expected value of $$$3 \cdot (x + y)$$$ = $$$6$$$ * EV($$$x$$$) = $$$\frac{6 \cdot m}{i}$$$.
Note that the probability of operating on anything at all is $$$\frac{i}{n}$$$, so multiplying that, we get $$$\frac{6 \cdot m}{n}$$$ as required. Now, simply find the final sum of len^3 (m^3) and the initial sum and subtract and divide by that factor of 6m/n.
How does antontrygubO_o's mind work?
This is a million times more understandable than the editorial. Thanks.
I have absolutely no idea where you found the "sum of lengths cubed" rabbit to pull out of your hat, but it's brilliant and makes a ton of sense now.
anton said that he was trying to find functions which change by constants. sum of len^2 would work infact if we always forced the ball to be chosen among the preexisting ones only.
I forgot to mention it in the editorial, but this is exactly my original proposal! That version was a bit too guessable, as the answer is...
$$$\sum_{1 \leq i < j \leq n} d_i d_j$$$, an integer!
So I had to tweak the settings a bit.
This is basically the same as the editorial, without the "how to come up with such function" part. Note that the final function the editorial found is $$$\frac{n}{m} \binom{d_i + 1}{3} = \frac{n}{6m} (d_i^3 - d_i)$$$ (the $$$d_i$$$ part sums to $$$m$$$ and is cancelled out), but I elected not to just chuck in a magic function and call it a day, instead demonstrating how one can work it out for other problems.
can someone pls explain in editorial of 1951C - Ticket Hoarding, How second sum (additional tax) = \frac{1}{2} ((\sum_{i = 1}^{n}b_i)^{2} — \sum_{i = 1}^{n}{b_i^2}) = \frac{1}{2}k^2 — \frac{1}{2} \sum_{i = 1}^{n}{b_i^2}?
Hi, for problem F, does the following construction work? Find the same index t, then $$$q \cdot p$$$ = [t−1,…,v+1,v,t,v−1,v−2,…,1,t+1,t+2,…,n]. where v's position is the proper index that exactly eliminates the unnecessary special inversions, and thus leaving exactly k' special inversions in $$$q \cdot p$$$? I did not work out a correct submission, but I think this construction should be valid.
for problem B battle cows
include <bits/stdc++.h>
include <ext/pb_ds/assoc_container.hpp>
include <ext/pb_ds/tree_policy.hpp>
define ll long long
define CEIL(m,n) ((m)+(n)-1)/(n)
using namespace __gnu_pbds; using namespace std;
template using pbds = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>; //find_by_order, order_of_key typedef priority_queue<int,vector,greater> PQ; typedef priority_queue MPQ; typedef pair<int,int> pii; const int MOD = 1000000007;
define heeho(n) ((((n)%MOD)+MOD)%MOD
int gcd(int a, int b){ if(b == 0){return a;} return gcd(b, a%b); }
ll findlcm(vector arr, ll n) { ll ans = arr[0];
for (int i = 1; i < n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans;}
void solve() { ll n; ll k;
vector arr (n,0); k--; vector brr (n,0);
ll maxm=0; for (ll i = 0; i < n; ++i) { ll x; cin>>x; maxm=max(x,maxm); arr[i]=x; brr[i]=maxm; }
if (n==2){ if(arr[k]==max(arr[0],arr[1])){ cout<<1<<'\n'; return; } else{ cout<<0<<'\n'; return; } } int low = 0; int high=n-1; int i=0; while(low<=high){ int mid=low+((high-low)/2); if(brr[mid]>arr[k]){ i = mid; high=mid-1; } else{ low=mid+1; } } ll maxm2=0; swap(arr[i],arr[k]); for (ll j = 0; j < n; ++j) { maxm2=max(arr[j],maxm2); brr[j]=maxm2; } int l=0; low=0; high=n-1; while(low<=high){ int mid=low+((high-low)/2); if(brr[mid]>arr[i]){ l = mid; high=mid-1; } else{ low=mid+1; } } //cout<<"i "<<i<<'\n'; //cout<<"l "<<l<<'\n'; if (k<i){ cout<<i-1<<'\n'; } if(k>i) { if (i==0){ cout<<max(i-1,l-i-1)<<'\n'; return; } cout<<max(i-1,l-i)<<'\n'; }}
signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int q; cin >> q; while (q--){ solve(); }
}
this is my binary search code also i am providing the linear seach code below
include <bits/stdc++.h>
include <ext/pb_ds/assoc_container.hpp>
include <ext/pb_ds/tree_policy.hpp>
define ll long long
define CEIL(m,n) ((m)+(n)-1)/(n)
using namespace __gnu_pbds; using namespace std;
template using pbds = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>; //find_by_order, order_of_key typedef priority_queue<int,vector,greater> PQ; typedef priority_queue MPQ; const int MOD = 1000000007;
define heeho(n) ((((n)%MOD)+MOD)%MOD)
int gcd(int a, int b){ if(b == 0){return a;} return gcd(b, a%b); }
void solve(){ ll n, k; cin >> n >> k; k--; vector arr1(n); vector arr(n); for (int i = 0; i < n; i++){ cin >> arr[i]; } int firstmax = n; for (int i = 0; i < n; i++){ if (arr[i] > arr[k]){ firstmax = i; break; } } //swap(arr1[0], arr1[k]); if (firstmax > k) { cout << firstmax — 1 << endl; //cout << firstmax << k << endl; return; } int win1 = firstmax-1; // first max > k swap(arr[firstmax], arr[k]);
int secondmax = n; for (int i = firstmax; i <= k; i++){ if (arr[i] > arr[firstmax]){ secondmax = i; break; } } int win2; if (firstmax - 1 < 0) win2 = secondmax - firstmax - 1; else win2 = secondmax - firstmax; //cout << firstmax << secondmax << k << endl; //cout << win1 << win2 << endl; cout << max(win1, win2) << endl; return;} signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int q; cin >> q; while (q--){ solve(); } } this is completely accepted code ,
but is my BS code i am getting wrong answer 8th numbers differ — expected: '41', found: '-1' in test case 2
now what have i took advantage of in my binary search approach was that the battle bw cows is iterative so to find where the first element greater than arr[k] exists i made a array brr which consits for brr[i] =max(arr[0],arr[1],.......arr[i]) so it just tells which cow wins at ith match so i will use bs on brr array to find where the first brr element greter than arr[k] exists thus at that point the first element arr[k] exists in arr.
i have tried a lot
please help me i am new on codeforces and this is very frustrating , please help
now what have i took advantage iof in my binary search approach was that the battle bw cows is iterative so to find where the first element greater than arr[k] exists i made a array brr which consits for brr[i] =max(arr[0],arr[1],.......arr[i]) so it just tells which cow wins at ith match so i will use bs on brr array to find where the first brr element greter than arr[k] exists thus at that point the first element arr[k] exists in arr.
but this is giving WA in test case 2
wrong answer 8th numbers differ — expected: '41', found: '-1'
please i have tried around 10 times but not getting correct solution also i am not able to find what is problem in my code also i know my logic is 100% correct please help.
nice editorial
Can't we solve problem D using the diophantine equation of k variables representing a particular k permutations of these 60 stalls?? i.e. for every k permutation over 1,2,3,...,60, the equation can be ~~~~~ a_i.x_i+ a_(i+1).x_(i+1)+.....+a_(k-i+1).x_(k-i+1) = n — (min(x_i, x_(i+1),...., x_(k-i+1))-1) ~~~~~
And if
nis divisible bygcd(a_i, a_(i+1),...., a_(k-i+1))that means we can always find some stalls in which we can shop exactly k jewels inn - (min(x_i, x_(i+1),...., x_(k-i+1))-1)coins.Here,
x_i, x_(i+1),...., x_(k-i+1)represents the prices at stalls, anda_i, a_(i+1),...., a_(k-i+1)represents the amount ofi_thjewel we are buying.In every k permutations we are taking our coins as
n - (min(x_i, x_(i+1),...., x_(k-i+1))-1)to represent that we don't need to spend all the n coins.Here is how i solved problem C. The intuition is why to choose tickets from the days where price is high. So just make use of the optimal days. What are the optimal days it is req = ceil(k*1.0/m) days. Make use of the req smallest days for getting my ans. if k%m==0 take m tickects from all the days and calculate the ans. else take K%m tickets from the first occ of the days where the price is the highest this is the my solution for C.275918483
I quite like problem C -- the intuition is simple enough and the mathematical proof is also quite elegant.