Thanks for participating! Despite the round being unrated, we hope you've enjoyed the problemset. We put a lot of effort into this round :prayge:
I want to give huge thanks to Dominater069 and satyam343 for their heavy contributions to the subtasks of G. If you're participating out of competition, we hope you enjoyed attempting these bonus subtasks. Otherwise, we hope you will enjoy upsolving them!
Problem Credits: cry
Analysis: cry
We choose $$$c$$$ between $$$a$$$ and $$$b$$$ $$$(a \leq c \leq b)$$$. The distance is $$$(c - a) + (b - c) = b - a$$$. Note that the distance does not depend on the the position $$$c$$$ at all.
Problem Credits: cry
Analysis: cry
Implement the statement. Iterate from $$$n-1$$$ to $$$0$$$ and use the .find() method in std::string in C++ (or .index() in python) to find the '#' character.
2009C - The Legend of Freya the Frog
Problem Credits: vgoofficial
Analysis: cry
Consider the $$$x$$$ and $$$y$$$ directions separately and calculate the jumps we need in each direction. The number of jumps we need in the $$$x$$$ direction is $$$\lceil \frac{x}{k} \rceil$$$ and similarily $$$\lceil \frac{y}{k} \rceil$$$ in the $$$y$$$ direction. Now let's try to combine them to obtain the total number of jumps. Let's consider the following cases:
$$$\lceil \frac{y}{k} \rceil \geq \lceil \frac{x}{k} \rceil$$$. In this case, there will need to be $$$\lceil \frac{y}{k} \rceil - \lceil \frac{x}{k} \rceil$$$ extra jumps in the $$$y$$$ direction. While Freya performs these extra jumps, she will choose $$$d = 0$$$ for the $$$x$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{y}{k} \rceil$$$ jumps.
$$$\lceil \frac{x}{k} \rceil > \lceil \frac{y}{k} \rceil$$$. We can use the same reasoning as the previous case, but there's a catch. Since Freya is initially facing the $$$x$$$ direction, for the last jump, she does not need to jump in the $$$y$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{x}{k} \rceil - 1$$$ jumps.
Problem Credits: vgoofficial
Analysis: cry
Initially, the obvious case one might first consider is an upright right triangle (specifically, the triangle with one of its sides parallel to the $$$y$$$-axis). This side can only be made with two points in the form $$$(x, 0)$$$ and $$$(x,1)$$$. We only need to search third point. Turns out, the third point can be any other unused vertex! If the third point has $$$y = 0$$$, then it will be an upright triangle, but if the third point has $$$y = 1$$$, it will simply be upside down.
One of the other case is in the form of $$$(x,0), (x+1,1), (x+2, 0)$$$. Let's see why this is a right triangle. Recall that in right triangle, the sum of the squares of two of the sides must equal to the square of the third side. The length between the first and the second point is $$$\sqrt 2$$$ because it is the diagonal of $$$1$$$ by $$$1$$$ unit block. Similarily, the second and third point also has length $$$\sqrt 2$$$. Obviously, the length between the first and third point is $$$2$$$. Since we have $$$\sqrt 2^2 + \sqrt 2^2 = 2^2$$$, this is certainly a right triangle. Of course, we can flip the $$$y$$$ values of each point and it will still be a valid right triangle, just upside down.
2009E - Klee's SUPER DUPER LARGE Array!!!
Problem Credits: cry
Analysis: cry
We can rewrite $$$x$$$ as $$$|a_1+\dots+a_i-(a_{i+1}+\dots+a_n)|$$$. Essentially, we want to minimize the absolute value difference between the sums of the prefix and the suffix. With absolute value problems. it's always good to consider the positive and negative cases separately. We will consider the prefix greater than the suffix separately with the less than case.
We can use binary search to search for the greatest $$$i$$$ such that $$$a_1 + \dots + a_i \leq a_{i+1} + \dots + a_n$$$. Note that here, the positive difference is minimized. If we move to $$$i+1$$$, then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.
To evaluate $$$a_1 + \dots + a_i$$$ fast, we can use the sum of arithmetic sequence formula.
Problem Credits: cry
Analysis: cry
Let's duplicate the array $$$a$$$ and concatenate it with itself. Now, $$$a$$$ should have length $$$2n$$$ and $$$a_i = a_{i-n}$$$ for all $$$n < i \leq 2n$$$. Now, the $$$j$$$'th element of the $$$i$$$'th rotation is $$$a_{i+j-1}$$$.
It can be shown for any integer $$$x$$$, it belongs in rotation $$$\lfloor \frac{x-1}{n} \rfloor + 1$$$ and at position $$$(x-1) \mod n + 1$$$. Let $$$rl$$$ denote the rotation for $$$l$$$ and $$$rr$$$ denote the rotation for $$$r$$$. If $$$rr - rl > 1$$$, we are adding $$$rr-rl-1$$$ full arrays to our answer. The leftovers is just the suffix of rotation $$$rl$$$ starting at position $$$l$$$ and the prefix of rotation of $$$rr$$$ starting at position $$$r$$$. This can be done with prefix sums. You may need to handle $$$rl=rr$$$ separately.
2009G1 - Yunli's Subarray Queries (easy version)
Problem Credits: cry, vgoofficial
Analysis: vgoofficial
We first make the sequence $$$b_i=a_i-i$$$ for all $$$i$$$. Now, if $$$b_i=b_j$$$, then $$$i$$$ and $$$j$$$ are in correct relative order.
Now, to solve the problem, we precompute the answer for every window of $$$k$$$, and then each query is a lookup. We use a sliding window, maintaining a multiset of frequencies of values of $$$b$$$ in the current window. To move from the window $$$[i\ldots i+k-1]$$$ to $$$i+1 \ldots i+k$$$, we lower the frequency of $$$b_i$$$ by $$$1$$$, and increase the frequency of $$$b_{i+k}$$$ by $$$1$$$.
2009G2 - Yunli's Subarray Queries (hard version)
Analysis: Solution 1: vgoofficial, Solution 2: awesomeguy856
First, read the solution to the easy version of the problem to compute the answer for every window of $$$k$$$. Let $$$c_i=f([a_i, ..., a_{i+k-1}])$$$. Now, the problem simplifies to finding
$$$\sum_{j=l}^{r-k+1} ( \min_{i=l}^{j} c_i)$$$
We will answer the queries offline in decreasing order of $$$l$$$. We maintain a lazy segment tree. We have a variable $$$x$$$ sweeping from $$$n-k$$$ to $$$0$$$. As the variable sweeps leftwards, in node $$$i$$$ of the segment tree, we keep track of $$$\min_{j=x}^{i}c_i$$$.
To decrease the value of $$$x$$$, we note that the range $$$[x-1, y]$$$ in the segment tree will be set to $$$c_{x-1}$$$, where $$$y$$$ is the largest value such that $$$c_y>c_{x-1}$$$ but $$$c_{y+1}\leq c_{x-1}$$$ (or $$$y=n-1$$$). To find the $$$y$$$ for each $$$x$$$, we may either walk/binary search in the segment tree, or use a monotonic stack.
Let $$$p_i$$$ be the smallest value $$$j>i$$$ such that $$$c_j<c_i.$$$ We can calculate these values using a monotonic stack and iterating through $$$c$$$ backwards. If such $$$j$$$ does not exist, then we let $$$p_i=n.$$$ Then $$$f(h,i)=c_i$$$ for all $$$i\le h-k+1<p_i.$$$ Further, $$$f(h,i)=c_{p_i}$$$ for $$$p_i\le h-k+1<p_{p_i},$$$ and so on.
Now, let $$$w(0,i)=i,$$$ and $$$w(h,i)=p_{w(h-1,i)}$$$ for $$$h>0.$$$ To calculate the answer for a query $$$(l,r),$$$ consider the largest value of $$$j$$$ such that $$$w(j,l)\le r.$$$ Then we can take the sum $$$c_{w(j,l)}\cdot(r-w(j,l)+1)+\sum_{i=1}^jc_{w(i-1,l)}\cdot(w(i,l)-w(i-1,l)).$$$
Now it remains to quickly calculate this sum. We can use binary lifting to solve this. Specifically, we create an $$$n\times20$$$ data table where $$$d[i][j]=\sum_{h=1}^{2^j}c_{w(h-1,i)}\cdot(w(h,i)-w(h-1,i)),$$$ if $$$w(2^j,i)$$$ exists, and $$$-1$$$ otherwise. We can precompute this table recursively, as $$$d[i][0]=c_i\cdot(w(1,i)-i)$$$ and $$$d[i][j]=d[i][j-1]+d[w(2^{j-1},i)][j-1].$$$
Then, to answer queries, we iterate $$$j$$$ from $$$19$$$ to $$$0,$$$ and if $$$w(2^j,l)\le r,$$$ we add $$$d[l][j]$$$ to our answer, and set $$$l=w(2^j,l).$$$ At the end, we add $$$c_l\cdot(r-l+1)$$$ to our answer.
2009G3 - Yunli's Subarray Queries (extreme version)
Analysis: Dominater069
I decided to write the Editorial for this problem in a step-by-step manner. Some of the steps are really short and meant to be used as hints but i decided to have a uniform naming for everything.
Continuing from the easier versions of the problem, we know we need to compute sum of min of subarrays, and answer subarray queries on this. Consider the standard approach of finding sum of min over all subarrays.
Sum of min of all subarrays for a fixed array is a well known problem. Here is how you can solve it, given an array $$$a$$$ of length $$$n$$$.
Let $$$nx_i$$$ denote the smallest integer $$$j (j > i)$$$ such that $$$a_j < a_i$$$ holds, or $$$n + 1$$$ if no such integer exists. Similarly, define $$$pv_i$$$ denote the largest integer $$$j (j < i)$$$ such that $$$a_j \le a_i$$$ holds, or $$$0$$$ if no such integer exists.
The answer is simply $$$\sum_{i = 1}^{n} a_i \cdot (nx_i - i) \cdot (i - pv_i)$$$. Calculating $$$nx_i$$$ and $$$pv_i$$$ can be done with Monotonic Stack.
Given a query $$$(L, R)$$$, divide all indices $$$i$$$ ($$$L \le i \le R$$$) into $$$4$$$ groups depending on the existence of $$$nx_i$$$ and $$$pv_i$$$ within the interval $$$[L, R]$$$, i.e. :
Case $$$1$$$ : $$$L \le pv_i, nx_i \le R$$$
Case $$$2$$$ : $$$pv_i < L, nx_i \le R$$$
Case $$$3$$$ : $$$L \le pv_i, nx_i > R$$$
Case $$$4$$$ : $$$pv_i < L, nx_i > R$$$
Try to calculate the contributions of each of these categories separately.
Case $$$1$$$ can be reduced to rectangle queries. Case $$$4$$$ is simple to handle as there is atmost $$$1$$$ element which satisfies that condition, which (if exists) is the minimum element in the range $$$(L, R)$$$ which can be found using any RMQ data structure like Sparse Table or Segment Tree.
Given a list of $$$n$$$ tuples $$$(l, r, v)$$$ and $$$q$$$ queries $$$(L, R)$$$ you have to add $$$v$$$ to answer of the $$$i$$$-th query if $$$L <= l <= r <= R$$$.
This can be solved in $$$O((n + q) log(n))$$$ using Fenwick Tree and Sweepline.
Iterate from $$$i = n$$$ to $$$i = 1$$$. For every tuple with left end at $$$i$$$ say $$$(i, j, v)$$$, add $$$v$$$ to a range query sum data structure at position $$$j$$$. Then, for every query with left end at $$$i$$$, we can simply query the range sum from $$$i = l$$$ to $$$i = r$$$ to get the required answer.
For every index $$$i$$$ from $$$1$$$ to $$$n$$$, generate a tuple as $$$(pv_i, nx_i, a_i \cdot (i - pv_i) \cdot (nx_i - i)$$$. Then, solve the Rectangle Queries problem with this list of tuples. The answer will be the required contribution of all indices belonging to Case $$$1$$$.
This leaves us with Case $$$2$$$ and $$$3$$$, which are symmetric, so we discuss only case $$$2$$$.
Let us sweepline from $$$i = n$$$ to $$$i = 1$$$, maintaining a Monotonic Stack of elements, popping elements when we find a smaller element, similar to how we find $$$pv_i$$$.
The indices belonging to Case $$$2$$$ are precisely the elements present in the Monotonic Stack (obviously ignore any element $$$> R$$$) when we have swept till $$$i = L$$$, with the possible exception of the minimum in the range $$$[L, R]$$$ (that might belong to Case $$$4$$$).
Let's analyze the contribution of the indices in Case $$$2$$$.
It is $$$a_i \cdot (L - i + 1) \cdot (nx_i - i)$$$.
Take a look at what happens when we go from $$$L$$$ to $$$L - 1$$$, how do all the contributions of elements belonging to Case $$$2$$$ change.
Some elements get popped from the Monotonic Stack because $$$a_{L - 1}$$$. We need to reset the contribution of all these elements to $$$0$$$.
The elements that do not get popped have their contribution increased by exactly $$$(nx_i - i)$$$.
$$$1$$$ element gets added to the Monotonic Stack, which is $$$a_{L - 1}$$$, so we need to initiliatize its contribution to $$$(nx_{L - 1} - (L - 1)).$$$
Resetting and Initiliazing Contribution is simple enough with most data structures, so let us focus on adding $$$(nx_i - i)$$$ to the elements present in the Monotonic Stack.
We can keep a Lazy Segment Tree with $$$2$$$ parameters, $$$sumcon=$$$ sum of all contributions in this segment tree node, and $$$addcon = $$$ sum of $$$(nx_i - i)$$$ of all "non-popped" elements in this node. The lazy tag will denote how many contribution increases I have to do. We can simply do $$$sumcon += lazy * addcon$$$ for the lazy updates.
Then, we can query the range sum from $$$L$$$ to $$$R$$$ to get the sum of contributions of all elements belonging to Case $$$2$$$. Case $$$3$$$ can be solved in a symmetric way. Adding up the answers over Case $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$ will give us the required answer.
We need to be quite careful with the Case $$$4$$$ element, as we might double count its contribution in Case $$$2$$$ and $$$3$$$. I handle this in the model solution by querying the sum of contribution in $$$[L, X - 1]$$$ where $$$X$$$ is the largest element present in the monostack which is $$$\le R$$$, and handling $$$X$$$ separately. You can easily note that $$$X$$$ is the only element belonging to Case $$$4$$$ (if any at all).
Auto comment: topic has been updated by cry (previous revision, new revision, compare).
The G2 problem can also be solved by the MO algorithm. My solution is:https://mirror.codeforces.com/contest/2009/submission/279633321
Can you explain your solution in detail
binary search forces
Apart from E which question needed Binary Search?
Nice Div. 3 contest !
In problem E i used prefix sum and got MLE bruh...
n<=1e9 binary search will work
its obvious coz you are taking 10^9 memory
Can we solve D faster than O(n^2) if xi's were real numbers instead of integers ?
It appears I am wrong. Disregard this
actually, no i think there are other cases,
any x and y values that stisfy x*y = 1 here will count :
proof :
a^2 = 1 + x^2 , b^2 = 1 + y^2
and
a^2 + b^2 = (x+y)^2
hence,
2 + x^2 + y^2 = y^2 + x^2 + 2*x*y
or x*y = 1 .
In the C problem, there is a neat way to check whether there will be any other case or not.
Following the given explanation, one can see, that if any of the points on the side which contributes 2 points to the triangle are moved, the angle increases, and since we can't get them any closer without falling into Case 1, we can't have any more cases.
Another way that can be used is the fact that the slopes of the two perpendicular lines must give a product of -1.
So, if the points were $$$(x_{1}, 0), (x_{2}, 1), (x_{3}, 0)$$$, then we would have :
$$$(\frac{x_{2} - x_{1}}{1 - 0}) * (\frac{x_{3} - x_{2}}{0 - 1}) = -1$$$
which leads to :
$$$(x_{2} - x_{1})(x_{3} - x_{2}) = 1$$$
And since the differences will always be integers, we have :
$$$x_{1} + 1 = x_{2} = x_{3} - 1$$$
It's a good explanation for showing there is no other cases. I came up with similar idea using geometric properties of the median in a right triangle. Other than triangles with sides in a vertical line $$$(x, 0), (x, 1)$$$, triangles must have sides on a horizontal line. Then the median of the right triangle separate out the two parts $$$(x - t, k) ,(x + t, k)$$$ with the last vertex is $$$(x, k'), k,k'\in \{0,1\}$$$. Then the median of length m calculated as $$$m^2 = 1^2 + t^2\ $$$, thus $$$(m - t)(m + t) = 1$$$, with similar argument $$$m$$$ must be 1. Sides on horizontal line is 2, then $$$t = 1$$$
~~~~~~
~~~~~
why this fails??
if they are equal you should not do -1
yes actually true, but when i removed that eequality then too it was giving wrong.
you should not use doubles as vgoofficial mentioned
We should avoid doubles whenever possible. For ceiling calculation, you may instead use the modulo operator (%) or use (x+k-1)//k
okay <3! thank you!
You should not check for x > y, rather compare the number of steps to complete them.
I'm really happy to unrate b/c I'm really mad because I don't submit my code. :)))))
G2 and G3 are not div4 problems. They should only appear in div2 or div1.
On the contrary, they cannot appear in div2 or div1
They are far too standard for both of them.
They were never meant to be solved by actual participants, A — G1 is the actual div4 round. They are meant to educate higher rated people.
so why have div 4 :/
wdym? why have these "bonus" tasks in div4? or why have div4 at all?
how does it hurt you? Ignore it if you want to. It is not fit for a div2 or div1 clearly, why not have it here incase someone finds it useful?
Because we have an abundance of easy tasks and an abundance of low rated people? D
clearly not div4, admit your mistake instead of making baseless points.
Dominater069 orz thanks for admitting it
i admitted it lol.
Not every task exists has to exist for intended participants.
Authors (and me) wanted to add bonus educational tasks for high rated participants. I really dont understand how the intended audience was affected
I appreciate the extra tasks. G2 is fairly new to me, and G3 was totally new to me. These were good tasks for learning.
Why Div.4 have to educate Master or Grandmaster? I cannot understand.
I think that that an overwhelmingly difficult problem is standard so can't put it in Div.2 doesn't mean that it can plugged in Div.4. I want a good problem must to be placed where a more people can solve it.
It doesnt have to, but isnt it good if it does? Who did it harm smh? Experts who want to be able to AK every div4 round. welp sad for them
Authors tried to do a nice thing by including extra tasks (something which they didnt have to do and still would be paid the same)
except G3 or G2 aren't good problems. Educational? sure. But educational problems should not affect rating.
I hate you so much
I think it's more like "it could've benefited more people in a higher division" rather than "it harmed those people."
While I see your argument, and it may be true that it won't be very good to be in a Div. 1 round, I honestly don't think there would be many solves even if it was in a Div. 2. I agree that standard problems shouldn't heavily affect ratings, but I think the benefits are far bigger to have this problem in a Div. 2 round instead of a Div. 4 round.
See how many of the 'target' people for these problems have actually participated in this round. If you want to attract those 'target' people and educate them, it needs to be rated for them to be motivated. Candidate masters won't expect a Div. 4 round to actually educate them, so there is little reason for them to even register for the contest and read the problem. It's not like having a few official solves ruins the whole authority of the rating system. It's way more important to motivate the fitting people to read and try the problem.
Also, G2 was actually an interesting problem for me. It may involve only a few standard techniques, but I don't think such standardness necessarily made the problem bad.
i agree with you that it would be on the edge of being fine for div2 because its hard enough so affecting only small number of people
But
you cant easily port a problem in between rounds, or decide the division based on one problem
even if it doesnt affect much, i dont see many div2 coordinators who would accept G3 as a d2F (even though it would be somewhat fine imo)
there was a high likelihood that G3 existed on the internet since it is a very natural problem, and indeed it's max variant existed on hackerrank. https://www.hackerrank.com/challenges/little-alexey-and-sum-of-maximums/problem (somebody solved it using this too)
Oh, you think G2 and G3 aren't good problems... Then why they are in contest? Isn't it wierd? Is it OK that not good problems in Div.4?
Then why Educational CodeForces (Div.2) exists? Just do plug all Educational CodeForces problem in Div.3 or Div.4. But there is reason that Educational CodeForces exists.
And why you're saying like that? Nobody said "I want to solve all of them!"
I'm just saying that problem must be its suitable position, so it can teach more people. If you do not think so, then I'm sorry. But I believe every problemsetter and coordinator, tester knows that Div.4 is not for Master or Grandmaster, but for Newbie or Pupil.
From problem solving perspective, it is mostly standard and implementation for me.
From eudcational perspective, it is useful as a problem to teach you the power of sweepline algorithms. There can be educational value in a problem despite it not being a "good" problem.
It's fake educational and has been for a long time.
years before, it used to be unrated and containing actually standard tasks. Now, it's just slightly more standard than average div2, but the name stuck.
This change happened almost solely because they became rated rounds.
But it comes at the cost of affecting people's ratings. Who likes to lose rating to a standard problem? I certainly don't
I can see G2 barely being on the edge of a Div. 3 but G3 is straightforward way too difficult. It's maybe a harder one even for a 2F.
G3 is definitely below d2F level
I think it's more like most of the other 2Fs are too difficult in general, but okay.
if most 2F are more difficult then that’s the 2F difficulty level lmao
You can say the same thing to this: if we keep having these kind of problems in 4G, then this becomes a 4G level problem. However, that would be far from what I'd expect from a 4G, and 2F is kind of such state already.
I agree that G2/3 are beyond div 4 level but I think it’s clear that they’re not intended to be solved by div 4 participants
But they are in a DIV4 contest
It's an extra problem to be upsolved for education value. What harm did putting these questions here do? Did it affect anyone? No. Only 1 trusted user solved G2 and G3.
Maybe my opinion is stupid but when you say a DIV4 contest, I expect a contest that contains problems that a DIV4 participant can solve or upsolve. Similar logic for other divisions. But it is fine. Feel free to put a Div1F in the next DIV4 contest.
How many people in division 2 can solve F you think? What about the old div 4 G about 2-sat? Do you think newbies and pupils have a chance of inventing that on the fly without seeing 2sat before? Almost every final question on each round is far too hard for its division. We only included G2 and G3 because they follow quite naturally from G1, and if is impossible to port questions between rounds.
I never said the past div4 rounds were perfect. Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems. So, because every final question on each round is too hard for its division, every round should follow this pattern? Anyway, it is your round, do as you want.
"Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems."
Ok? isn't that the purpose of G2 and G3? For div.4 participants to upsolve? Of course, you don't have to upsolve it right now. You can always come back when you're better. The problem doesn't disappear.
I don't see any harm in contests with a harder final problem than its intended division. It gives strong participants of the intended division something to think about for the rest of the contest (instead of doing nothing), and makes more of a competition for higher rated participants.
Sharing my video of winning the round along with explanations of my solutions: https://www.youtube.com/watch?v=JhL-oPzptlI
E was great !
I tried solving E by interpreting it as a function and using the quadratic equation, but it keeps giving the wrong answer for n = 1000000000, k = 1000000000
I also used the same logic. You probably have to use unsigned long long. I was able to pass the cases using that.
But wouldn't a <= sqrt(D). so, a — sqrt(D) will never be a solution since it is negative why are u checking it ??
was stuck in that for some time, but then used unsigned long long and it worked.. But came to the comments to see that it can be done by using binary search, need to see how they are applying it to the V curve, i mean ternary can work but binary.. no intuition honestly
For G1: There's a mathematical logic behind "ai — i". Let's say we have a sequence "(C, C + 1, C + 2, C + 3 + ...)". Any 'ith' element ai will be equal to "C + i — L", where 'L' is the starting index of the window. So (ai = C + i — L) => (C — L = ai — i). This (C — L) is a static part, which means we have to find the maximum occuring "ai — i".
You can think of E as an inverted mountain array and look for the minimum point using binary search
I think G1 can be solved by finding the longest increasing subarray for each query in O(logN)
Ans will be (right — left + 1) — longest;
counter example: arr = [1, 4, 9].
f(arr) = 2, while your method returns 0.
Longest *consecutive... Correction
counter example: arr = [1, 10, 3].
f(arr) = 1, while your method returns 2.
counter example arr = [1 2 5 4] here l = 1, r = 4, your answer = 4 — 2 = 2. but answer should be 1
My solution 279640569 of F, is giving correct output as 13 on my local and online compilers but wrong answer as 12 on codeforce's judge for following test case:
1
5 1
4 8 3 2 4
7 10
Can someone explain it?
dit con me codeforces lam gan het thoi gian moi bao deo cong rating, dung la cf rac
why wasnt this AC for the frog and freya question?
can somebody explain how they used binary search for E? i found the function to be unimodal and hence i applied ternary search to find the point of minima, i dont get the intuition for binary search (i dont see monotonicity)
There is a V formation, check my solution. To find minima just use formula of summation n there are different cases where mid will lie
Just look for the point where
current_sum > (total_sum)/2
. The correct answer is nearby there. .The entire universe is against me for becoming pupil. Was doin super well today until that announcement appeared, L cry, L servers... MikeMirzayanov I think its time to add a new god damm server.
I miss SlavicG,mesanu,flamestorm ... (╥﹏╥)
Here is a clean(er than the edi) solution to C and a unique solution to D.
For C we can see that
$$$\lceil \frac{x}{k} \rceil$$$ + $$$\lceil \frac{y}{k} \rceil$$$ + $$$|\lceil \frac{y}{k} \rceil-\lceil \frac{x}{k} \rceil|$$$ — ($$$\lceil \frac{x}{k} \rceil$$$ > $$$\lceil \frac{y}{k} \rceil$$$)
This is because note that x goes first, and at some point we will have to use 0 for some turns once already at the coorindate for x or y.
Firstly, lets imagine we do not take more steps for x than we do y, it would go x,y,x,y and continue until we are all done, therefore we do not need to add 1. However if we were to take more steps for x than we do y, it creates a pattern x,y,x,y,x which requires an extra x, ys would simply become 0 after y is reached which is where the absolute value part of the problem comes from. x.
As for D, which I found much more interesting, though do note I misread it and as such overcomplicated it.
There were 2 main cases, 1: The right angle is rotated some multiple of 90 degrees from 0, and 2: The right angle is some (45 + 90x)%360 degrees, I saw the latter as a way to be able to use the x,y -> s,t transform used in geometry. This transform essentially turns x,y coordinates into coordinates of the y intercepts of slope y=x+b and y=-x+b. By doing so, we can create s,t = {x+y, x-y} though a bit of algebra. Using this transform, we have essentially rotated by 45 degrees making the last case trivial (I did not read that it was only 0 or 1 so I had not thought about the x+2 y^1 thing.) After this some basic map spam gives AC, do note that as long as the X is equal we can just add n-2 due to all points being on 0 or 1 on the Y.
If you are wondering the simpler solution to D for case 2 is that it simply has the points x,y x+1,y^1, x+2,y
Here are submissions for both, hope that puts these problems into a bit of a different perspective! C: 279561294 D: 279622363
This contest had quite a few issues with the queue and pages loading, however I still enjoyed the problems and I hope you did too! I would have gotten plus VE if this contest was rated however instead of complaining I had fun solving these problems even if I did overcomplicate D a bit, however it would give insight to a possible harder version of the problem if it was not only 0 and 1 on the Y.
G题太难啦。写了个 BZOJ4262 的做法才过。
This was a good round, sad that it got unrated.
thanks for writing, issues not your fault!
I have a different solution for G2. Use a set and a map to get the minimum moves for the window of size k starting from every index. Then use a stack to build a vector to store the index of next smaller number. Then use jumps to next smaller number to compute answer for every range.
Nice Div3 Contest !!!
My code is failing in case of- 1000000 100000 10 givng me answer- 200000 !! Can someone point the mistake ?? Thanks
I loved the HSR and Genshin references. Please do continue naming problems on our favourite characters. Thank you!
I have implemented the same logic as the solution above for 2009D - Satyam and Counting, but keep getting
I cannot see the corresponding input.
Can anyone please tell me what I am missing? https://mirror.codeforces.com/contest/2009/submission/279654100
I spotted one mistake but that does not fix the Wrong Answer above. The mistake is that each array should have size
n+1
instead ofn
because each0 <= x <= n
. I also fixed therange
s accordingly. But, as mentioned, the Wrong Answer stays the same.I figured it out. Because of my confusion with the range of
x
, the code decrementsx
. That mapsx=0
tox=-1
, which does not result in an error but in undesired behavior when used as alist
index.We can use binary search to search for the greatest i such that a1+⋯+ai≥ai+1+⋯+an
Isn't the solution for E wrong? If the above statement is the correct solution, the greatest i is just len-1 no?
In problem E's editorial ...
We can use binary search to search for the greatest i such that a1 + ⋯ + ai ≥ ai+1 + ⋯ + an . Note that here, the positive difference is minimized. If we move to i+1 , then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.
It should be a1 + ⋯ + ai ≤ ai+1 + ⋯ + an because we want to minimize the difference.
cry
(ignore the formatting)
ahh oops, thanks for letting me know
Can't understood editorial solution for G2
G2 can also be solved using sqrt decomposition in $$$O(Q*N/B*log(B))$$$ where $$$B=\sqrt{N}$$$.
For each query, maintain the answer from left to right. If the current minimum is greater than the current block's minimum, we can use a binary search to find where the current block's first minimum is.
Submission: 279662760
Can we use ternary search at the problem E, though we need to find the minimum here?
We can.
Submission: 279662737