Thank you for your information! Also thanks ag._.!

Wish the information could help the future participants. Maybe you should add the information on BIO-helper! Like USACO Guide has some unofficial insights from previous contestants, but they do provide some useful information.

I have another question about R1 cutoffs.

I have read some of the past problems, and I found the difficulty of the Q2 varies a lot: there may be "insanely" complicated Q2, or sometimes very simple. This problem seems significantly affect the participants' score distribution, or the cutoff.

I think usually (ideally) the R1 cutoff will be three programming problems (~75 points) add some writing problems, as a total of about 80~85 points. And it is a bit hard for even CF Masters (like me) to get a perfect score. But it's hard to say when there is some "imbalanced" problems.

Are there any public (or private) information about the cutoffs? Or any estimations? Are the difficulty provided by BIO-helper related to the actual (or guessed) cutoff?

P.S. In China some websites provide "cutoff estimation" feature before the official results are disclosed, where users upload their scores and the website gives an estimation according to the statistics. This may be interesting to BIO as well!

It's surprising to know that there is still a such black-boxed scoring rule and also contest feedback...

But at least they give 5 submissions.

I'm a bit curious about the BIO R2 scoring rules in real contest.

The problem statements are not mentioning any subtask or partial score testcases. Is it revealed in actual contest, or the scoring still follow the old-fashioned way of number of passed testcases (maybe with hidden special property or size, requiring contestant to do their best in runtime efficiency)?

Also, do the problems have equal scores? Will easier problems have lower scores? Sometimes there will be another bonus problem, how will the problem be scored?

Isn't this Steiner Tree Problem and it's NP-hard?

UB should be more suspected in this case, since the order of evaluation of parameters should not matter.

See the comment from rewhile above.

See 1062F - Upgrading Cities.

It's incorrect.

Try this:

64
1 11 64 55 44 46 37 58 4 24 16 31 37 54 54 61 28 31 52 59 59 55 24 7 16 13 64 10 11 49 41 40 52 44 49 1 25 21 47 10 6 18 4 7 41 25 19 34 35 13 46 21 28 6 30 34 61 35 47 18 19 58 30 40

Maybe it will be difficult to construct a counterexample if you compute powers up to like $$$100$$$ and do some hashing.

As we are assuming that the vertex $$$u$$$ we are going to infect is the lowest one, it does not matter which subtree is shallower or deeper. If a chosen vertex infects $$$u$$$, it infects all vertice need to be infected in a whole subtree, and no vertice lower than $$$u$$$ need to be considered.

To the first question, I think it should be some data structure work to find the highest choose-able vertex within distance $$$d$$$.

To the second question, The proof just shows that if several vertices with same depth meet the condition, they are both optimal since they infects an identical subset of vertices need to be infected, so any one can be chosen as an optimal local choice.

The only vertice can be chosen are those whose distance to nearest uninfected vertex is $$$ \gt d$$$. When we choose vertices we only consider those vertice.

I'm not sure if this is related to chordal graph, but I think the greedy strategy is correct. I'll post a proof below.

Let $$$u$$$ is a lowest vertex needs to be infected. Let $$$v$$$ be the highest vertex can be chosen and $$$dis(u, v) \leq d$$$. The strategy claims that $$$v$$$ is one of the chosen vertex.

Assume $$$v$$$ is not chosen, then another vertex $$$w$$$ with $$$dis(u, w) \leq d$$$ is chosen, and $$$dep(w) \leq dep(v)$$$. It can be proved that $$$v$$$ can infect all uninfected cows infected by $$$w$$$.

Let $$$a$$$ be the LCA of $$$u$$$ and $$$v$$$.

• Case 1: If $$$w$$$ is in the subtree of $$$a$$$, then:
  • In the subtree of $$$a$$$, $$$v$$$ infects all vertices of the subtree, since $$$dis(v, a) + dis(u, a) \leq d$$$ and $$$a$$$ is a lowest vertex to be infected. So $$$v$$$ infects no less vertice than $$$w$$$ in the subtree.
  • Outside the subtree of $$$a$$$, $$$v$$$ infects no less vertice than $$$w$$$ since $$$dep(v) \leq dep(w)$$$.
• Case 2: If $$$w$$$ is not in the subtree of $$$a$$$, let $$$b$$$ be the LCA of $$$u$$$ and $$$w$$$, so $$$b$$$ is an ancestor of $$$a$$$.
  • In the subtree of $$$b$$$, $$$v$$$ and $$$w$$$ both infects all vertices of the subtree, since $$$dis(w, b) + dis(u, b) \leq d$$$, and $$$dis(v, b) \leq dis(w, b)$$$ since $$$dep(v) \leq dep(w)$$$.
  • Outside the subtree of $$$b$$$, $$$v$$$ infects no less vertice than $$$w$$$ since $$$dep(v) \leq dep(w)$$$.

So it is not worse to changing the chosen vertex $$$w$$$ to $$$v$$$.

I didn't come up with the greedy idea in the contest. I was inspired by the discussion here. I had a DP idea in contest with optimization to $$$O(N)$$$ but I didn't managed to implement it in contest.

I may try to stay up a bit late the day before contest, so I will feel a little tired before the contest, so I can take a one-hour nap and have a good status at contest.

If you want to ensure your sleep, the most important thing is to forget the round as soon as it ends. Then you will be able to sleep for 6-7 hours. Check the systest result and upsolve the problems after you wake up. (Well, this is difficult to me because I always want to insist on solving the problems until I solve it. But some of my friends just do so and I think it is theoretically much useful)

I think you are right.

This extends the solution to process submask addition and supermask & submask query, with $$$O(\sqrt{2^N \cdot N})$$$ per query.

I noticed that forgot to mention another difference between the UTS Open problem and the problem in this post: the UTS Open problem is asking to process single element modification while the problem in this post is asking to process single element addition. I'll edit my post.

Single element modification can be easily processed, and submask addition can be handled by computing total contribution of the queries. Is it possible to process submask modification?

UTS Open '18 P6 — Subset Sum is a similar problem with slightly different update and more complicated query: asking for single element modification and the sum over all $$$a_i$$$ such that $$$i$$$ is a submask of $$$p$$$ and is a supermask of $$$q$$$. $$$q = 0$$$ is similar to the topic discussed in this post, which is a subtask of this UTS Open problem.

tfg solution can be applied to solve the subtask but fails for general $$$q$$$, while adamant solution can be extended to solve the full problem. They are both mentioned in the editorial.

EDIT: I forgot to mention another difference between this problem and the problem in this post. Now it is updated. tfg extends the solution to process submask addition and supermask/submask sum query, see below.

It's a good point. I checked the operation sequence and find the $$$128$$$-th term is $$$10000000$$$. Checking the number of set bits in advance can indeed save half operations.

Then I guess if there are good operations at $$$64$$$-th and $$$128$$$-th, and I find $$$11000000$$$. As in my solution, this operation is used to make even set bits in odd and even bits, and I use it when there are both odd set bits in odd and even bits. This information may not be deduced by just the total number of 1's.

So now it looks like an enumeration strategy: if before $$$11000000$$$ there are even set bits in odd and even bits, then after it there are odd set bits, and vice versa.

In my solution I spend a $$$10101010$$$ and tell if it needs $$$11000000$$$ from the result. So it may be like my solution use extra instructions and tell from the total number of bits whether we need to use the "core" instruction to toggle the difference between some sets of bits.

If for any $$$(2^k-1)$$$-operation sequence the middle operation is a core operation, then my solution is indeed follow the above strategy: it successively checks if the instructions $$$10000000$$$, $$$11000000$$$, $$$10100000$$$, $$$11110000$$$, $$$10001000$$$, $$$11001100$$$, $$$10101010$$$ and $$$11111111$$$ should be applied. If this is true, then my solution looks like a binary search strategy, comparing to the $$$(2^8-1)$$$-operation complete search strategy.

Then a few more questions:

1. What is a core operation? I think it should be an operation in the operation sequence which is the only operation to toggle the difference between two specific sets of bits, but I have no proof to it now. If this is true, then the binary search strategy works.
2. What is the minimum number of operations needed to check if a core operation should be applied?

Wow the living problem author! Thank you for your painful problem! :(

I think enabling skipping operations may lead to a completely different solution, because the results of operations are cumulative. It is difficult to say whether skipping some operations can still enumerate all potential target states. Moreover this may break the induction hypothesis. I'd rather consider this strategy as a heuristic modification of the first "state search + pruning" solution.

Well, when there is a complete $$$(2^8-1)$$$-operation sequence, it is easy to guess any simpler strategy is trying to form a subsequence of the $$$(2^8-1)$$$-operation sequence. I'm interested in whether there is any better way to achieve or explain this strategy, but now it mostly seems like some special case work.

An amazing fact: Problem C can be solved within just $$$16$$$ operations!

And my sad story: I insisted on working on this strategy but I failed to finish before the end of contest :( I thought the "300 operations" is just a red herring (or for the ease of first subtask) and missed the regular $$$(2^8-1)$$$-operation solution.

I want to share this solution to the community because I found it by mainly case work. I don't know if:

1. It only works for number of bits $$$k = 8 = 2^3$$$ or other $$$k$$$'s, because in most steps there are only 2 cases need to consider;
2. It has further insight or there is any theory to explain this (may lead to a simpler thinking process and coding; I thought it may have some connections with high-order difference);
3. $$$16$$$ is the minimum steps to achieve the goal.

#include <iostream>
#include <string>

using namespace std;

int qry(const string &s) {
    cout << s << endl;

    int n;
    cin >> n;
    return n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int cs = 1; cs <= t; cs++) {
        int n = qry("00000000");

        if (n % 2 == 1) {
            n = qry("10000000");
        }

        if (n == 4) {
            n = qry("10101010");

            if (n == 2 || n == 6) {
                n = qry("11000000");
            }
        } else if (n == 2 || n == 6) {
            n = qry("10101010");

            if (n == 4) {
                n = qry("11000000");
            }

            if (n == 4) {
                n = qry("10101010");
            }
        }

        if (n == 4) {
            n = qry("11001100");

            if (n == 2 || n == 6) {
                n = qry("10100000");
            }
        } else if (n == 2 || n == 6) {
            n = qry("11001100");

            if (n == 4) {
                n = qry("10100000");
            }

            if (n == 4) {
                n = qry("11001100");
            }
        }

        if (n == 4) {
            n = qry("10101010");
        }

        if (n == 4) {
            n = qry("11110000");
        }

        if (n == 4) {
            n = qry("10101010");
        }

        if (n == 2 || n == 6) {
            n = qry("10001000");
        }

        if (n == 4) {
            n = qry("10101010");
        }

        if (n == 4) {
            n = qry("11001100");
        }

        if (n == 4) {
            n = qry("10101010");
        }

        if (n == 8) {
            n = qry("11111111");
        }
    }

    return 0;
}

Subjectively I think it is a strategy from AtCoder admins to thoroughly isolate the rating-concerning users from the real contest, just like saying "if you are not our target audience, we give you a chance to leave. Nevertheless you are still free to make use of our service." I personally think it is a bit controversial.

Additionally, the rating rule may cause the significant decrease of rated participants. And I suspect the rated participants may distribute at a higher rating, which will be really negative to newbies -- unless they have strong confidence and eagerness to take part in contests.

Are participants who register the contest after five minutes passed always unrated?

Each single number made up of at most 9 distinct prime numbers does not infer if GCD([B[0], B[1], ..., B[N]) = 1, where N >= 9 then there must exist at least one subset of length at most 9 whose elements have GCD = 1. For example, let $$$a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$$$, $$$p = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29$$$, and for each $$$i$$$, $$$b_i = \frac{p}{a}$$$. The GCD of $$$b_1, b_2, \dots, b_{10}$$$ is $$$1$$$, each $$$b_i$$$ is a product of $$$9$$$ distinct prime numbers, but GCD of any $$$9$$$ of $$$b_i$$$'s is greater than $$$1$$$.

It is easy to prove that there must exist at least one subset of length at most 10 whose elements have GCD = 1: starting with any given number, then repeatedly do the following process: choose a number to add to the current subset, such that it can eliminate at least one prime factor of the current GCD. Since this process can be done at most $$$9$$$ times, the resulting subset should have a size no larger than $$$10$$$.

However, the conclusion in your statement is still correct, it is because the given numbers are less than $$$10^9$$$. That means, if all subsets of size $$$9$$$ have GCD greater than $$$1$$$, then each number should have exact $$$9$$$ different prime factors. Moreover, since they are coprime, then at least one of them does not have prime factor $$$2$$$. This number should be at least $$$3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 = 3234846615$$$.

A tricky question.

Assume $$$m \gt 0$$$. Actually it can be shown that for the last occurrence where $$$ps_x = m - 1$$$, there must be $$$v_x = 1$$$, otherwise there will be another position $$$x \lt y \lt r$$$ such that $$$ps_y = m - 1$$$. My in-contest solution made use of this conclusion, besides that I tried to find the first occurrence online.

Another way to avoid this discussion, is to find the position where $$$ps_x + ps_{x+1} = 2m - 1$$$. This idea is already discussed in this comment, and you can see the implementation in this comment below.

Just put the queries in buckets by $$$l$$$. Then loop over the indices and do the same above.

I think I have an easier implementation. Let $$$ps$$$ be the prefix sum array. Notice that for each query $$$(l, r)$$$, we can determine $$$k$$$ and need to find some index $$$x$$$ such that $$$l \leq x \leq r$$$ and $$$ps_x = k$$$.

Then we can have an offline solution to answer all queries $$$(l, r, k)$$$. Put the queries into buckets by $$$r$$$. Then loop over $$$1 \dots N$$$ and maintain last occurrence of each prefix sum value. Due to the proven existence of our target index, the last occurrence before $$$r$$$ must meet our requirement.

Since $$$|ps_x| \leq N$$$, this solution works in $$$O(N + Q)$$$.

After component compression, the result graph should be a bi-colored tree coloured in bipartite pattern.

We claim that the answer should be $$$\lceil D/2 \rceil$$$, where $$$D$$$ is the diameter of the tree.

Considering the diameter. Initially all edges connect different coloured vertices, and each operation at most removes 2 such edges. Moreover, if we root the tree at the centre of diameter and repeatedly operate on the root, we can reach this answer.

I think the component compression can be done in $$$O(N)$$$, and finding diameter cost another $$$O(N)$$$ time. So this solution works in $$$O(N)$$$.

Additionally, it seems that there's no need to compress the connected components: we can simply find the path with most different coloured edges. This can be done with DP in $$$O(N)$$$ time.

A counter-example for "ABC AC Library Contest": ABC212H, which is obviously a Fast Walsh-Hadamard Transform problem.

Maybe AtCoder admins regard this as a common beginner trick.

According to Code Jam Rules 3.1,

Code Jam will start with the online Qualification Round on Friday, March 26, 2021 at 13:00 UTC and run for thirty (30) hours, ending on Saturday, March 27, 2021 at 19:00 UTC.

So this post writes a wrong start and end time of qualification round.

By the way, schedule of other rounds are consistent with the rules and schedule page of Code Jam.

Removing a light merges two segments into one.

Adding 2 to 0-2 2-3 3-6 results in 0-3 3-6. Just store the split points.

As a note, processing the queries in order also works, but you need an extra ordered data structure (such as a priority queue) to maintain the segments.

Process the queries reversely.

The contest window was just closed. Don't ask me why I know that, I was kicked out.

Hope you are well :(

I have thought Div. 4 is totally needless because I thought Div. 3 is easy enough so participants fail in Div. 3 should just practice Div. 3 hard. But after I read some posts from users and users, I'm now holding the opposite idea.

Codeforces holds contests, but not only hold contests. We compete, we win, we lose, but we are veterans, we have get used to this. We enjoy this because most of time we are dedicated in the problem set in the 2-hour or 2.5-hour span. Nobody will enjoy a contest when he/she find the first 2 problems can be done in 10 minutes and that's all. Contests do not judge people, they also entertain people and encourage people.

According to my feeling, for a problem set containing 6 problems, I'll enjoy most if I can solve 4 or 5 problems and keep working until the last time. I believe we have the same feeling — many red users compete in Div. 2 but Div. 3 red participants are significantly less. Boring for solving 2 problems, interesting for solving 4 problems, boring for solving all problems — this just infers the gaps between divisions should be about 2 problems, i.e., (2 problems in Div. 1) ~ (4 problems in Div. 2) ~ (6 problems in Div. 3).

So, is Div. 4 necessary? I've checked scoreboards of recent Div. 3 contests, and usually about 1/3 of all participants solved 2 problems or less. So if we add 2 easier problems in Div. 4, obviously for them, and new comers during the difficult time, giving the contest can be more interesting, and there's no doubt that Div. 4 can attract many participants.

I guess there can be several regular problems, like simple problems in AtCoder Beginner Contest A/B/C, algorithmic problems like LeetCode Weekly, or some implementation problems which require some speed. Also several ad hoc problems will be set. Maybe they can be less interesting (maybe bad, in some users' view), but maybe real competitors don't think so.

I don't think 1400 is far away from 1600, and the contests are usually not prepared for the strongest participants in the division, so I regard Div. 4 as the contests for users whose rating is around 1200, for whom any existing contest can be boring. Unfortunately, the target users are usually absent for discussion, this post can be a good example — blue and purple users are discussing the future of greens and greys.

As a member in the community, I try to understand the feeling and need of others. So I come to this conclusion.

Solution in simple words:

A. Just check the input string.

B. Compute the food each person has. One can use a frequency array to do this.

C. Iterate through all paths. Each path makes one observatory non-peak (or two, if they have same height).

D. Since $$$a^5 - b^5 = X \gt 0$$$, we have $$$a \gt b$$$, that is $$$b \leq a - 1$$$. So $$$a^5 - (a - 1)^5 \geq a^5 - b^5 = X$$$. Obviously $$$f(x) = x^5 - (x - 1)^5$$$ is increasing when $$$x \gt 1$$$ and decreasing when $$$x \lt 0$$$, so we can find the upper and lower bound of $$$a$$$ from $$$X$$$. Simply enumerate all possible $$$a$$$'s and check if $$$a^5 - X$$$ is the fifth power of some integer. This can be done with precomputing all fifth powers in the potential range. In practice we can use a looser bound to estimate the range of $$$a$$$.

E. Consider the number of pairs $$$(i, j)$$$ satisfying $$$i \lt j$$$ and $$$A_i + A_j = j - i$$$. Fix $$$j$$$, the number of $$$i$$$'s pairing with $$$j$$$ satisfying $$$A_i + i = j - A_j$$$. Just iterate from left to right and keep the frequencies of all $$$A_i + i$$$.

F. In each operation we can greedily take $$$1$$$ from the greater number and add $$$1$$$ to the smaller one. The only exception is there being two $$$1$$$'s and one $$$0$$$ and we are going to operate on the $$$1$$$'s. We have to create another $$$0$$$ in this operation, so we need to consider the next operation in order to make it doable. The answer is No if any operation creates a negative number.

Find the earliest and latest day of the $$$i$$$-th working day. If for some $$$i$$$ they are the same, this is a day bound to work.

You can greedily iterate the days to find the earliest days. Also, reversely iterating the days gives the latest days.

I think this should the intended solution. Actually I coded exactly this $$$O(n^2)$$$ solution in contest. Here I'm just discussing a better solution after contest.

Why not? I think can be quite easy to code.

My Submission

Problem D can be solved in $$$O(N)$$$.

Hint: use difference array and prefix sum.

I think it is quite important to embrace the variety of problems.

Perhaps the word "genre" is suitable to describe this: we have implementation problems, algorithmic problems, observation problems, also "story-rich" problems — which are hated by most of participants, especially the reds.

I believe we are contributing here to the community, not to red users or any specific group of users. If we observe the community well, we can easily find people attracted by different "genres". As a result, we are meeting different contributors and different participants in every contest.

It is rather precious of Codeforces being a community of competitive programming. So I don't want only a single idea or aesthetics exists. We should take the interest and need of most users into account, from newbie through LGM.

Oh, I didn't notice that monotonicity. I tried to prove $$$LHS - RHS \leq 0$$$ and break it into several cases because of $$$\max$$$ and $$$ \operatorname{floor}$$$ function. That needs lots of work. Thanks!

I think it can be rather difficult to prove the correctness of binary search. It's easy to guess but hard to prove.

For Silver problem "loan", does anyone have a proof for the correctness of binary search solution?

I had to do a lot of math to prove it. Did I miss anything?

I'm interested in this project.

I'm interested in promoting competitive programming, but I think we should know the novices well at first. This project can be a good experiment — to know what the new comers are actually seeking, and how they behave when they find competitive programming is actually different from their original imagination. Also, we can try to find what they need when they learn, practice, compete, fail and grow. We can share our experience to them, at the same time we can get to know them — so that we can build the community more friendly to those who are less experienced.

It's risky — yes, because I don't know them well yet. I'm not technically strong enough, but I hope I can give some help to this.

I've seen many good ideas in the comments. I'm looking forward to this training camp.

Did the contest end earlier than expected?

I was still in my window but I was kicked out when submitting problems. I think the contest should not end so early.

$$$O(n)$$$ solution for C: I didn't put the board greedily. I tried to break the gaps between the boards evenly.

My Submission: 64221433

Another same idea lol

Mine: 62694197

I had realized it after the contest XD

In contest I wanted to implement monotonic queue at first, so the pair existed, but later I changed my mind to use STL set. I wrote another simpler version after contest.

EDIT: If anyone interested with the simplified version, here it is: 62751793

You may want to try the result of following code:

cout << ceil(-0.5);

According to the definition, it should have minimum sum of depths. BST with minimum sum of depths should have all leaves on the last level or the last but one level. Now we can deduce that a perfect BST of height $$$h$$$ has two perfectly balanced subtrees of height $$$h-1$$$.

Then apply the parity condition to inductively find all striped perfect BST.

For Problem D, we can find the monotonicity of the position to stop. That is, let $$$s_i$$$ be the position to stop if song $$$i$$$ is the first played song. Then for $$$i = 2, ..., n$$$, it holds $$$s_i \geq s_{i-1}$$$. Here we assume the list is cyclic.

So we can use two pointers to loop over the stopping songs for each starting song. To determine if a song can be added into the current playlist, we need to keep the maximum element of the sliding window. Using STL set can achieve $$$O(nlogn)$$$ time and we can further apply monotonic queue to achieve $$$O(n)$$$ time.

My submission: 62706780. I used STL set in contest, for simplicity of code.

Well, I think "minimum cycle" should be a classic problem, so I did some search. The optimal way I could find is to do some modification on all pairs shortest path algorithms, like the classic cycle-detection Floyd-Warshall algorithm. I think the problem should have the same complexity as APSP algorithms. Since all edges have side length 1 here, the best we can achieve is $$$O(N(N+M))$$$.

However, I tried another way to solve this problem, to find the "minimal cycle". The following solution is inspired by Tarjan's algorithm to detect strong connected components, and I think it solves this problem in $$$O(N+M)$$$. In simple words, I try to find a vertex with back edge (if multiple back edges, choose the one with maximum depth of head) in the DFS tree, that means we find a strongly connected component with only one back edge. Since the SCC must be a DAG plus a back edge, we can find the minimum cycle which is a subgraph of this SCC in one pass.

This algorithm does not give the minimum cycle in the graph, but it does give a minimal cycle.

My Submission

For Problem F, we just claim that any smallest cycle in the graph is a possible answer.

First of all, if there is no cycle in the graph, the answer is obviously -1. Otherwise, assume we find a smallest cycle in the graph. We can show that if it isn't a simple cycle, then any extra edge in the subgraph will make there exists a smaller cycle.

Then we simply find the smallest cycle in the graph. My solution runs BFS from each vertex to find the smallest cycle containing it, and among all the possible cycles output the smallest one.

My Submission

It's also right, because router $$$i$$$ can only affect rooms $$$[i-k, i]$$$.

But writing $$$j \gt =0$$$ can already achieve linear time complexity.

For problem F, my solution achieved $$$O(n)$$$ through simple approaches.

Let $$$f_i$$$ denote the minimum cost to make rooms from $$$1$$$ to $$$i$$$ to be connected. In this case, $$$f_i$$$ should be non-decreasing. So for each $$$i$$$, the optimal result of $$$f_i$$$ is: 1. install a router in the first room in $$$[i-k, i)$$$ which can be equipped with a router; 2. link directly; 3. wait for the first router after $$$i$$$ to cover this room.

So we can use $$$dp_i$$$ to compute $$$f_i$$$ for the first 2 choices. When dealing with a router, we use current $$$dp$$$ value to update backwards all $$$dp_i$$$ in the segment between last router and current router, to apply the choice 3.

My Submission: 61007600

The sample code of problem F in official editorial returns 404.

For problem F, I first came up with the solution to keep $$$minY$$$ and $$$maxY$$$ for each $$$X$$$, but I thought it is too slow so I gave up it. After some thought I did it with sorting by angles then two pointers to achieve $$$O(NlogN)$$$ time complexity.

I think it is easy to construct such test cases to break the former solution: we can set the $$$x$$$s as $$$1, 2, 4, 8, \dots$$$ and $$$-1, -2, -4, -8, \dots$$$.

I've never thought of this, but maybe it can pass the test, since it only needs to run one sieve across all test cases.

I wrote a $$$O(p^2)$$$ solution for arbitrary $$$a_i$$$, based on elimination.

if we compute the $$$i$$$-th order differential of these equations, for all $$$j \lt i$$$, $$$b_jx^j$$$ term will not exist. So we can first compute the $$$(p-1)$$$-th order differential to only leave the $$$b_{p-1}x^{p-1}$$$ term, then we can get $$$b_{p-1}$$$. Then we subtract all $$$b_{p-1}x^{p-1}$$$ terms and compute the $$$(p-2)$$$-th order differential to get $$$b_{p-2}$$$, and so on.

We can compute the $$$i$$$-th order differential by $$$\sum_{j=0}^{i} (-1)^jC_i^jf_{t_j}(x)$$$ for any contiguous $$$i+1$$$ equations $$$f_{t_0}, f_{t_1}, \dots, f_{t_i}$$$. This differential should only contain the $$$b_ix^i$$$ term and the constant term, if we have already subtracted $$$b_jx^j$$$ for all $$$j \gt i$$$.

Actually we can prove $$$\sum_{j=0}^{i} (-1)^jC_i^j(i-j)^i=i!$$$. Since $$$(i!, p)=1$$$, we will always have exact 1 solution.

My submission

In most rounds (no matter Div2 or Div3) the last problem is not intended to be solved by most contestants, so it is reasonable that only about ten solve it.

I agree with you that problem difficulty is highly influenced by the rating of participants, so it is not so objective to match its actual difficulty.

The point is, I think Div3 is introduced to layer low-rated participants, and statistically produce a smooth solve rate distribution. Although some rounds seems to be good (like Codeforces Round 531 (Div. 3)), others are still somehow unfriendly (like Codeforces Round 560 (Div. 3), Codeforces Round 552 (Div. 3), Codeforces Round 547 (Div. 3), Codeforces Round 527 (Div. 3)).

I hasn't collected so much data as Nickir. I checked the result of recent rounds and it's my conclusion.

I agree.

I think in any division contestants should be distinguished mainly by the number of solved problems rather than the speed of coding. That could encourage contestants solve more and also learn more.

An extra division is provided for blue (or lower rated) users because Div2 problems are not enough to tell their difference. They are expected to do 2 or 3 problems fast and then do nothing but watch the round in Div2. Div3 should be intended to let them complete more problems in different difficulties so they can enjoy the round.

It should be a contest for targeted contestants, not a practice round of out-of-competition users.

Hello, I think the editorial PDF for the fourth solution of D puts a wrong link of source code.