I think you can tighten the complexity analysis of D to around $$$O(n^3)$$$. Here's how:

Note the sum of the positive elements of $$$s$$$ is bounded by $$$n - 1$$$ (or else the answer is always $$$0$$$). Concretely, $$$\sum_{i = 1}^{i = n} \text{max}(s[i], 0) \leq n - 1$$$ going forward.

We take the same approach as the tutorial, except in our $$$dp[l][r][x][y]$$$ we only need to maintain $$$x \leq s[l - 1]$$$ and $$$y \leq s[r + 1]$$$. If either of these are $$$-1$$$ then we'll just code them specially (so shift everything up by $$$1$$$, per se).

Then, for some fixed $$$l, r$$$, we have the following scenarios:

$$$s[l - 1] \geq 0, s[r + 1] \geq 0 \Rightarrow (s[l - 1] + 1) \cdot (s[r + 1] + 1)$$$ states.

$$$s[l - 1] = -1, s[r + 1] \geq 0 \Rightarrow (s[r + 1] + 1)$$$ states.

$$$s[l - 1] \geq 0, s[r + 1] = -1 \Rightarrow (s[l - 1] + 1)$$$ states.

$$$s[l - 1] = -1 = s[r + 1] \Rightarrow 1$$$ state.

Hand-wavily we can say this is roughly bounded by $$$(s[l - 1] + 1) \cdot (s[r - 1] + 1)$$$ (if we pretend to "clip" $$$s$$$ to $$$0$$$).

The cost of a transition is to iterate over the entire range and iterate to fix some $$$r$$$ to the left and some $$$s[k] - r$$$ on the right (similar to tutorial). So the total cost to compute a state is approx. $$$s[l - 1] \cdot s[r + 1] \cdot ((s[l] + 1) + \ldots + (s[r] + 1))$$$. The latter term is bounded by $$$n - 1 + n = 2n$$$. So the total cost of everything is bounded by $$$\sum_{l = 1}^{l = n} \sum_{r = l}^{r = n} (s[l] + 1) \cdot (s[r] + 1) \cdot 2n \leq ((s[1] + 1) + \ldots (s[n] + 1))^2 \cdot 2n \leq 8n^3 = O(n^3)$$$.

Implementation is more of a pain witht his for sure because you need to make sure you're not iterating $$$x$$$ and $$$y$$$ too much and handle somewhat edge cases when $$$s[l - 1] = -1$$$ or $$$s[r + 1] = -1$$$ or $$$s[k] = -1$$$ when iterating between $$$l$$$ to $$$r$$$.

Anyone has links to gold/plat statements? Can't see on website

UC Berkeley: vkgainz Bungmint Badint

What's the necessary proof for D1C? Like if there doesn't exist a cyclic shift so the frequencies are the same, then there's no solution? I think the editorial only shows sufficiency.

Is there any way to see the day 1 problems? Doesn't seem to be on the contest page for me (only shows countdown for day 2).

$$$O(m)$$$ formula (can maybe reduce to $$$O(1)$$$)) after preprocessing:

if $$$m \lt n$$$. If $$$m = n$$$ then the answer is simply $$$k * n$$$.

Auto comment: topic has been updated by vkgainz (previous revision, new revision, compare).

Here's another (more systematic) way to arrive at what you want to compute in G.

Let $$$X_i$$$ be the indicator variable such that $$$X_i = 1$$$ if and only if $$$i$$$ (by index) is included in an increasing sequence and there exists $$$x$$$ such that $$$a_x \gt a_i$$$ and $$$x$$$ is past the end of the sequence. If $$$tot$$$ is the number of total increasing sequences of the array, we are interested in computing $$$tot \cdot E[X_1 + \cdots + X_n]$$$ by definition.

Let's focus on the $$$E$$$ term. By linearity, this collapses to $$$E[X_1] + \cdots + E[X_n]$$$. Note since $$$X_i$$$ are all indicator variables, $$$E[X_i] = P(X_i)$$$.

Let $$$lst_i$$$ be the largest index such that $$$a_{lst_i} \gt a_i$$$ (similar to editorial). Then,

If $ $$$tot_i$$$ denotes the total number of sequences including $$$a_i$$$, and $$$tot_{il}$$$ is the number of sequences including $$$i$$$ and $$$lst_i$$$ then this value is just

Proceed as mentioned in the editorial to find $ $$$tot_i$$$ and $$$tot_{il}$$$, and don't forget to multiply the entire sum by $$$tot$$$.

Here's my implementation (a bit messy).

This idea of assigning indicator variables to compute what we want works on a lot of mathy problems like these, especially on AtCoder. Also, excuse the wonky latex (was being annoying when typing this up).

I probably would have quit competitive programming if quarantine hadn't happened and I was able to participate in codeforces contests (they'd always clash with school otherwise).

I was a high school junior at the time and the only cp contests I gave were USACO, which were only like 4 times a year and got quite boring honestly since there was a limited pool of problems. Especially at the end of junior year when it was useless for apps and whatnot after that point.

But I started doing contests here regularly and really liked the type of problems here, and here we are today, 20 months later :)

The resulting string s will be a prefix of t with the first character difference after less than the corresponding character in that position in t. We can just iterate this and use a segtree or something to maintain the minimum number of operations needed to transform to that prefix. Time is $$$O(n * 26 * logN)$$$.

On the crypto side, Ethereum was founded by Vitalik Buterin, a 2012 IOI Bronze Medalist.

Yeah I ended up reading the editorial, the $$$nsqrtn$$$ optimization is really cool.

Hints on D? Didn't make much progress, just noticed that the edge you take has to either be an existing bridge or an edge that you add. Seems hard to find a subset of connected component sizes that add up to near $$$n/2$$$.

tfw your only WAs on a problem were on A

If $$$s_i$$$ is the sum of all $$$k_i$$$ with $$$m_i = i$$$, then the expected return you get from including $$$i$$$ is equal to $$$\frac{s_i}{t}$$$ if $$$t \geq 20$$$. Note that you greedily want to select the largest $$$t$$$ values of this for the messages, and you can show that this value is greatest when $$$t = 20$$$ (since averages decrease since you're taking lower and lower sums).

Really enjoyed solving D, the observation was cute and felt rewarding (though I'm not sure if I had the intended solution).

I've been doing cp for like 3 years now. I practiced mostly off codeforces/usaco/atcoder. Never really focused on particular topics except rarely (always found it too boring lol). Just did practice problems.

I wasn't able to understand a ton of topics (including bitmasking) for the first 2ish years I did cp; I only ended up learning it after I became a master. Don't stress too much about learning certain topics, things like bitmasking will only show up on a small subset of problems anyways. Most codeforces problems from A-D can be tackled with raw ad hoc intuition.

IMO the recent harder difficulty change is fine since it makes the problems more interesting.It's still capturing the spirit of codeforces, which seems to be solving hard programming puzzles with more emphasis to puzzles than programming; the 2500 B was straight up ad-hoc, and the 2600 B was dp (although the constraints weren't chosen well). The 2900 D was also a really cool dp problem and didn't require any advanced data structures/algorithms, just dp at the end of the day.

Alternate solution to $$$G$$$: We keep a bucket of size $$$\leq \sqrt{M}$$$ that stores {vertex, update_value} pairs that we haven't updated in the graph yet. When the size of this bucket becomes $$$\sqrt{M}$$$, then we iterate through every element in it and update the whole graph correspondingly. When we add a new vertex to the bucket, then search through each element in the bucket and find its updated value based on that. Total time complexity should be $$$O(N + Q\sqrt{M})$$$ or something, but my code is still TLEing on some cases. Is it because of using ordered_set?

Where did the compressed input form go (i.e. used here last year)? The input was huge on C and I'm not sure if that's the reason my code started to segfault (I don't think I used too much memory nor time), but it sucks to pass validation and not be able to even submit on the real thing :\

If the input size has no affect on that, then it's fine, but I was still a fan of that form of input.

Wow lol my code doesn't pass that case either since I had a typo in my segtree :\ also wondering why pretests didn't have anything similar to this.

EDIT: Systests weak too lol it passed

My solution was $$$O(n^2 \cdot 2^n + n \cdot 3^n)$$$.

Not particularly, since rating is (somewhat) continuous. But use it as an excuse to feel good about your progress/hard work :)

One of the IOI contestants from last year charged $175 an hour for tutoring. It's absurd how much rich families in the United States are willing to pay for this kind of stuff for their kids (usually to give an edge in college admissions).

Suffering from success

SecondThread is really into running from what I know.

I decided to take this contest with 4 hours of sleep since I wanted to hit GM today :P seems like it didn't backfire. Thank you for the nice problems, E especially was very cool. Hopefully I don't FST now and it's time to have an irrational fear of participating in contests again D:

The points decreased per minute is proportional to its starting score. A 250 problem ends at 150? I believe (either 3/5 or 2/5 of original), so each minute it's decreasing by 100 / (total_contest_time), which was 150 for that contest. This value is less than 1, so sometimes it'll round up I guess.

There exists $$$O(MAX(a_i) \log MAX(a_i))$$$ using SOS dp.

For a given mask, we want to compute the number of elements in the array that are a submask to it. Then, to answer a query $$$x$$$, we just check if $$$freq[\sim x]$$$ is non-zero.

Run a SOS dp to do this and it takes above time complexity.

AFAIK this is the same problem as the one you're asking: https://codeforces.me/contest/165/problem/E. You can look at the editorial there if you need more explanation.

Try reading the editorial if you haven't. But this was my general (compressed) thought process for C.

Ok so we have a string of length 10 and the answer is at most 10 meaning we can probably brute force. Let's suppose the answer ends after $$$x$$$ games. Then it's optimal to either make player 1 win as many games in the first x and player 2 win as few games in the first x and check whether player 2 can ever catch up to player 1 in the last 10 — x games -- if they can't then x is a possible answer. Of course, this works vice versa too, so we do another case where player 2 wins as much as possible and player 1 wins as few as possible. Just return the first x that we terminated after that.

You seem to be putting too much thought process in implementation while coming up with ideas. For problems that are challenging, it's best to separate implementation completely from your thoughts/observations. Once you come up with enough to solve the problem, make sure you concretely know how to implement them (which isn't as bad as it sounds). CF is great because problems don't have much implementation compared to thinking (in general) compared to some other contests.

Your implementation will naturally become more refined and concise as your problem solving skill expands. I remember writing over a 100 lines for easy problems when I was still new to cp, but I'm able to do the same in 1/3 — 1/4 the amount of space now.

Implementation shouldn't be a huge part of competitive programming (somewhat ironically I suppose) but it ends up making a large difference of contests -- and implementation skill helps a lot outside of cp when you're doing applied CS stuff.

If you want good examples of implementation, try looking at top people's codes who don't use macros (ecnerwala and jiangly come to mind). In particular I remember looking at their solutions and being amazed they wrote less than half the code I would for problems.

I was able to do $$$O(n\sqrt{n})$$$

I trolled on F because of a one char error for like 40 minutes -_- but the problems were good overall.

The observation on E was pretty nice (albeit maybe a bit convoluted?).

He's right, I definitely recall seeing A sometime in the last few months on Codeforces, although I can't remmeber which contest.

If you thought today had too much constructive check out Global Round 9.

Can you do F using broken profile DP? I tried doing that and I think it works but the implementation seemed bad so it might not be intended.

The binomial solution is also pretty heavily motivated by analyzing the simples. Two of them are 13C5 and one of them is 13C4 which leads one to think whether we can break the structure down in order to get that form. Once you look for something along those lines, the solution becomes way easier to find.

Speaking from experience, it's very frustrating when you put a solution in queue for 20 minutes that you think will pass only to get WA, at which point you'd probably have to stop what you were working on and then go to debug it now.

I agree a lot of it can be solved by a good mindset towards it (i.e. not caring about it too much and moving on to other problems), but at least for me it's harder to focus when I know one of my previous solutions might WA and I wouldn't know for a while, not to mention the frustration if it eventually does.

This comment section is one of the most wholesome ones I've seen on codeforces thanks to AquaMoon!!

SecondThread was touching upon this in his stream, he claims that it wouldn't because of the nature of $$$\gcd$$$ decreasing at most $$$\log \text{max}(a_i)$$$ times before it'll reach $$$1$$$ (or something like that). I'm not really sure how the analysis works, maybe he can shed some light on it.

xD I used that same reference code when writing my solution. Definitely felt overkill, I've only seen SCC actually required on like GM+ level problems.

After $$$k$$$ steps $$$a_i = \gcd(a_i, a_{i + 1}, \cdots, a_{i + k})$$$ (indices taken $$$\mod n$$$). Thus you can binary search on $$$k$$$ to get the answer.

Since $$$a_i$$$ is equal to a $$$\gcd$$$ range in the original range, for a given $$$k$$$ we query this value for each $$$i$$$. Solution thus takes $$$O(\log n * n \log n) = O(n \log ^ 2 n)$$$. Look at my solution if you're curious about implementation.

A and C felt somewhat bashy but otherwise contest was fine... G was a decent problem but I kept bricking on it until I realized I needed to change like two lines :| guess that's what I get for not learning SCC.

Curious on how people solved F -- I ended up using segtree but this is obviously not intended.

When you have these expected value problems and you have to compute the total value (or expected value) of all sums, you can generally compute the total contribution of each term and add it separately.

I think this can somewhat be seen by putting all the subsets of sums with the # of times they get counted vertically. When you add all of them up, you just get one equation in the $$$n$$$ variables (for whatever $$$n$$$ is, here it's the number of terms that start with $$$+$$$). The coefficient of each variable here is the number of times it's counted across all subsets -- which is the same as its independent contribution. Then, you can proceed as above.

I remember 4 years ago my mom told me that some of her parent friends who had high schoolers said they would stay up to 2:45 am at times. I laughed at that and told myself that I'd never get time management so bad.

Now I sleep regularly around 2:30 — 4:00 am -_- it'll only become worse in college. I don't even know why I stay up sometimes tbh

Yes for 1.

For 2 I'd just loop in increasing order. For the first index if it's an excess then add that excess to the answer and transfer all of that to the second neighbor. If it's deficit then add the absolute value of deficit to the answer and subtract the absolute value of deficit from second neighbor. Then you have the first neighbor solved and can repeat the operation for neighbors 2 and 3, then 3 and 4, etc. until you're done. It runs in $$$O(N)$$$.

I'll try to answer your questions. Your solution is correct.

1) Notice what happens when we swap with neighbors $$$i$$$ and $$$i+1$$$. Either $$$A_i$$$ decreases by $$$1$$$ and $$$A_{i + 1}$$$ increases by $$$1$$$, or vice versa, which is equivalent to doing the same operation on $$$D$$$ (since $$$B_i$$$ doesn't change). But if you look at the prefix array $$$P$$$, then either $$$P_i$$$ decreases by $$$1$$$, or $$$P_i$$$ increases by $$$1$$$. Thus, an operation only affects a singular element of the prefix array and moving them to the median will not affect any other prefix values.

2) If the array wasn't circular then your method wouldn't work. The above operation I described only holds when $$$i = 1$$$ to $$$i = N - 1$$$, meaning we can only do the operation on $$$P_1, P_2, \cdots P_{N - 1}$$$. Note that when we exchange with neighbors $$$1$$$ and $$$N$$$, then either $$$P_1, P_2, \cdots, P_{N - 1}$$$ all increase or decrease by $$$1$$$. Suppose we do this operation $$$x$$$ times. Then, our new array $$$P$$$ becomes $$$P_1 - x, P_2 - x , \cdots, P_{N - 1} - x, P_N$$$. What is the cost of this in total? Since we have to bring all $$$P_i$$$ to $$$0$$$ ($$$A_i = B_i$$$ at termination), it is $$$x + \sum_{i = 1} ^ {N - 1} |P_i - x| + P_N = \sum_{i = 1} ^ {N} |P_i - x|$$$ (since $$$P_N = 0$$$ is given). And now we can see why we want the median: the sum I just wrote is minimized when $$$x$$$ is equal to the median of $$$P_1, P_2, \cdots, P_N$$$.

3) The problem isn't very hard if it's not circular. You can note that you never want to do exchanges with $$$i$$$ and $$$i + 1$$$ as well as $$$i + 1$$$ and $$$i$$$ simultaneously, so it's a simple greedy from there.

Let me know if you have any equations. Hope this helped.

There's an extremely simple $$$O(N)$$$ solution to C that the editorial didn't cover.

Let $$$pos_i$$$ denote the final position of the value $$$i$$$ in the final permutation ($$$0$$$-indexed). It's easy to see that $$$pos_i \leq K + i$$$ in every permutation satisfying the property given.

Now, consider each position in our final permutation in increasing order. I claim that if $$$pos_i \lt K + i$$$, then the only position it can appear in the original permutation is $$$pos_i$$$; otherwise, if $$$pos_i = K + i$$$, it can appear anywhere from $$$K + i$$$ to $$$N - 1$$$ inclusive.

This isn't hard to show; if $$$pos_i \lt K + i$$$, then we don't have to move it at all, so we have to place it there in the original permutation, since we care about the minimum number of swaps. Otherwise, if $$$pos_i = K + i$$$, then we can place it anywhere from $$$K + i$$$ to $$$N - 1$$$ in the original permutation since we have to move it to $$$K + i$$$ eventually, so the minimum condition holds.

Getting the answer is simple: loop in increasing order. For each $$$i$$$, if its position in the final permutation is $$$ \lt K + i$$$ then don't change the answer; otherwise, multiply by $$$N - (K + i)$$$. Here is my code.

I calculated the DP in another way in problem NDMRK since I was scared the tree DP wouldn't be $$$O(N * K)$$$.

Run an euler tree and store the ranges that each node's subtree covers and sort these ranges by start point. Note that we have the special property that for any two ranges, one wholly covers the other or their intersection is empty.

Now let $$$dp[i][j]$$$ be the minimum number of ranges to select in the last $$$i$$$ ranges to color exactly $$$j$$$ nodes. Transitions here are extremely simple:

• Suppose we choose the last $$$i$$$ th range. Let $$$\text{nxt}$$$ be the first range after this one that does not intersect with the current range. Then, $$$dp[i][j] = dp[\text{nxt}][j - \text{len(ith range)}]$$$
• Suppose we don't choose the last $$$i$$$ th range. Then $$$dp[i][j] = dp[i + 1][j]$$$.

Set $$$dp[i][j]$$$ to the minimum of these two values. Since transitions are $$$O(1)$$$, this dp runs in $$$O(N * K)$$$. The rest of the solution proceeds as the editorial does. Here is my code.

I still don't know how to find SCC's, my dumbass just copies Kosajaru's algorithm from cp-algorithms everytime I need it :clown:.

Also don't know any string algorithms (not even KMP) -- hashing has been able to solve almost every string problem I've needed to thus far. Otherwise cp-algorithms it is :)

The fact that this team might not even be the true "top" 4 in China and still took top 4 in the world...that's freaking crazy.

It might be possible to do it in $$$N^3$$$ but my solution was $$$O(N^3\text{log}N)$$$. The bottleneck was finding the $$$O(N^2)$$$ lca's for each pair of nodes given a fixed root.

Felt like the entire contest was me making little progress on C1 and secretly hoping the solve count would stop rising :P at least I did well in the speedforces race.

I don't really know Kuroni but this post was very moving...I wish him the best of luck in his future endeavors!

Built different

I found D to be a lot easier to think about using binary search (which solves in $$$O(n\log(10^{14}))$$$. Similar to the editorial, sort with respect to $$$b_i$$$. Now, let $$$x$$$ be the number of items with price $$$1$$$ and $$$y$$$ be the number of items with price $$$2$$$. Then, our answer is equal to $$$x + 2 \cdot y = y + \sum_{i = 1} ^ {n} a_i$$$, so it suffices to minimize $$$y$$$.

Let's binary search on this. Suppose we set $$$y = k$$$. How do we know if this is enough? First we make two simple observations:

• We buy all $$$k$$$ items at the very beginning.

• We buy all $$$k$$$ items from a suffix of the sorted array.

Why does this work? Well, if you are going to buy $$$k$$$ items of price $$$2$$$, you should do it earlier than later, because then we might have more $$$b_i$$$ opened up that gives us items of price $$$1$$$. Similarly, we should be buying our items from a suffix because that way we can maximize the number of items of price $$$1$$$ we get (and, subsequently, minimize the number of items of price $$$2$$$).

From here it's simple to solve with binary search. To test $$$y = k$$$, start a counter for the number of items bought and an index at $$$0$$$. While the counter is greater than $$$b_{\text{index}}$$$, add $$$a_{\text{index}}$$$ to the counter (since we're getting all of those for price $$$1$$$) and increment the counter. If $$$k$$$ is enough, then the counter should be $$$\geq$$$ the number of items we have in total.

This explanation may seem a bit complicated, but the ideas involved are simple to arrive at and the implementation is very clean: my submission here.

I mean it'll take you like 2 contests to reach div 1 probably, and it's not like you can't do the problems afterwards. Codeforces also holds div1 / div2 contests where experienced newcomers will have to participate in div2, so I don't see how that's any different.

Maybe their parents pushed them to start but I'm pretty sure they have tons of internal motivation for it too -- you don't just become a master because your parents want you to, you kinda have to like doing it yourself too.

I know some of them do jobs/internships in quant firms too (i.e. Jane Street, Two Sigma). I heard it can pay quite a bit :P

Your question seems really similar to this recent ABC problem. The editorial there was pretty good; you should read it if you haven't. If you still have questions maybe I can try to explain it.

Yeah, maybe there's some OJ that they use which has really good problems for growth/learning, but it's probably just a combination of working hard and working smart at the end of the day -- informatics culture is pretty advanced there (I could be wrong about this) so with a lot of people being really good alongside you and there to give you tips/help probably helps a lot with improvement. They might have figured out the meta of training for cp efficiently (although this might just be a stupid conclusion).

Entertaining the idea of them getting super good from some secret OJ training sounds pretty cool too; it's very enigmatic :P or maybe I'm just childish haha

I think a lot of them do a lot of practice on other places and are pretty good when they start cf.

But every so often I click on one of their rating graphs and see that they went from true master (i.e. they were around master level in a lot of contests, similar to how I am right now) to like international grand master or lgm in a matter of months, and that's extremely surprising for me -- I want to know how they do it too :) Share your tips please :P

I have two dads; they are bobib and 2020akadaver.

Don't think average country IQ really plays a role here -- when you're primarily looking at a pool of bright high schoolers and motivated college students who do CP, it's very hard to say that as a whole they're representative of the intelligence of their country.

Here's my thoughts on the issue: my understanding is that in India a lot of people don't start CP until they reach college (I'm assuming that high school cp culture isn't very large there, although I may be very wrong, but considering the amount of people that start CP in India because of job prospects in college, it's a reasonable assumption).

In contrast, a lot of the top kids from China/Russia/United States started CP in middle school or early high school, and had a ton of time to practice and improve. College is more time intensive and as you have to juggle more responsibilities, you might have less time to just focus on a hobby like CP.

Just my 2 cents, feel free to correct me if I'm wrong.

Since the problem asks to find the lowest possible median, we can binary search a possible value mid and check if the lowest median can be less than or equal to mid.

To check if any of the medians are $$$\leq \text{mid}$$$, consider each $$$K \times K$$$ submatrix separately. How to check if the median here is $$$\leq \text{mid}$$$? Let $$$\text{numMore}$$$ be the number of values in the submatrix that are strictly greater than $$$\text{mid}$$$. Since the median is defined as the $$$\frac{K^2}{2} + 1$$$ th highest element, we must have that $$$\text{numMore}$$$ be less than that value. It's not too hard to see why this holds; if $$$\text{numMore}$$$ is less than that value, then there will be a value $$$\leq \text{mid}$$$ in the $$$\frac{K ^ 2}{2} + 1$$$ th highest position, and if $$$\text{numMore}$$$ is more than that value, then the median will be greater than mid.

So we go through all the $$$K \times K$$$ submatrices and check whether any of the medians are $$$\leq \text{mid}$$$, and update our binary search values accordingly.

To speed up the process of finding the number of values greater than $$$\text{mid}$$$ in a submatrix, we can use prefix sums. Final complexity turns out to be $$$O(N^{2}\text{log}MAX(A_i))$$$

My code with some comments is linked here: https://atcoder.jp/contests/abc203/submissions/23086034

Seems like it'll be a contest of who can get D and E for me...

I used just a set. If you run a euler tour on the second tree and map each vertex to a segment, it's equivalent to finding the longest subsequence of vertices on the first tree such that none of their segments intersect, and the subsequence is part of a path from the root to some vertex in the first tree.

Basically you store a set of all the segments that you take from the root to a parent of a vertex; when scanning the vertex in, check if a segment intersects it in the set. If it does, remove that (because it's never optimal to take a larger over smaller segment if both intersect, and if two segments intersect, one must completely overlap the other since it's from a euler tree). Then, add the segment belonging to the current vertex in the set. The answer is the maximum size of the set at any time.

Oh ok, sad

What happens if you AC a problem twice in pretests? I resubmitted one of the problems due to runtime and got -50 penalty but if the first solution passes systests, will I still get penalty?

"Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces." Wait, so we're gonna have one of these every 3ish months? :O

Omg I used to play AoE2 although I never got very competitive with it :P absolute banger of a game though.

Maybe, I woke up at 6:30 AM today for Code Jam and haven't slept since :P and I have exams next week, but contests are fun too :D

Upd: Ended up taking!

Life is hard on the west coast...

My favorite SecondThread quote: "Here's where the contest starts, ladies and gentlemen. We finished the speedrun; now, we start the thinking."

2 is direct copy of this AtCoder problem (they even used the same variables lmao)

Agreed, everytime I had to test I couldn't just do the queries in my head I had to rewrite some code that evaluated the queries automatically and then remove that to submit.

The problem idea wasn't so bad though, I think the function given just made it really painful.

You can downvote me if you want, but I thought C was a pretty shit problem overall. Idk what was so bad about it, my implementation didn't even end up being that bad...just thinking about all the cases and working around that god-awful min-max function ticked me off I guess :\

The interface is really slick and this seems like a very cool thing that the community can contribute to. I love it!

I think if CP were to become very popular, everyone would be more attracted to the speedforces aspects of it. Just look at tmw's kickstart round A video last year; it went viral because of his insane speedforces. I doubt many people would want to watch people sitting down for hours trying to solve 4-5 problems, but it would be more interesting to see them do it over the span of 20-30 minutes, just by the nature of the latter being a lot more volatile. Many upsets can happen, which is something people really like to see. Even I have to admit it's more fun watching speedforces than slowforces.

Not sure where to ask this (can't find a R1B thread), so I'll just put it here.

Are you allowed to unofficially participate in Round 1B if you qualified off Round 1A already? I.e. will I be able to look at the problems and make submissions during the contest, or is my account barred from participation during contest?

Holy shit I forgot to mod the answer in E....I feel so stupid rn ugh. The answer is around O(N^2) at most anyways, right? Why was mod even required?

Schrodinger's problems

What's up with the Friday Div 1s lately?

Yeah, I solved A, B, and C1 relatively quickly and basically lost incentive to code up C2/C3 even though I had sol paths. I ended up just watching the scoreboard and eating dinner during the contest.

Is your max(a_i) per test case, or in total? If it's per test case, then it would be O(nklogn+max(a_i)t) which is too much

I tried sleeping at 10 pm yesterday but couldn't due to the hype...ended up staying awake till 3 am and dipped the contest rip.

5:35 am infinitely harder than 6:35 am to wake up in west coast :(

Yes, I believe this is the mirror.

Another one bites the dust.

sigh this is really the fourth time in a row :|

As a participant, I hope the contest will run smoothly cough servers cough.

I might be wrong, but I think the answer is $$$\frac{N}{N}+\frac{N}{N-1}+\cdots+\frac{N}{N-K+1}$$$. Before you get $$$K+1$$$ distinct numbers, you need to get $$$K$$$ distinct numbers. From there, you have an $$$\frac{N-K}{N}$$$ probability of picking a new number and reaching $$$K+1$$$, so $$$E(K+1) = E(K) + \frac{1}{(\frac{N-K}{N})}$$$ and we arrive at the consequential formula.

I never kept track. I was pretty slow when starting cp (learned dfs after like 8-9 months lol) since I focused more on math contests at the time, but I just solved problems that seemed hard for me. And at that time, it was cf 1000-1300.

I have to disagree with that; when I first started cp, I found 1200s and 1300s extremely hard (and rewarding to solve!) and often learned some new insights or common algos from them.

As long as you see improvement and find the problems rewarding, that's enough.

Got my shirt yesterday (in West Coast of the United States).

Yeah lol, I was trying to do xor basis from here for like 1.5 hours before giving up and finding the dsu solution T_T

Do you know if a similar phenomenon happens with downvotes, and if so, what the numbers are? (i.e. an orange downvote going to -8 and blue downvote going to -3 over time)

Server down well this certainly aged well :\