Thanks Celeste for the contest! I appreciate it.

Congratulation to all participant.

Good luck to everyone.

Hello I am having problem with submission of Problem B.My Code runs fine on my local machine but its giving wrong answer when I tried to submit it here.. It seems to me the issue with compiler pls look into this..

We look forward to your interesting tasks!

omg Spring Festival Eve round

Get a life

A1: probably shipping issues A2: xd

Because their wish.

They are Indian setters. They can't send prizes to other countries because it costs too much.

I was part of organising similar events in previous years, generally sending prizes requires approval from college professors and they denied to approve the transactions for overseas participants since it was "costing too much". Too much pain to convince them for anything. Later on we did send amazon gift cards to overseas winners but couldn't get approval for some prizes :(

My current IQ is ZERO, Do something for me as well

My IQ did increase thanks to this contest. (Hopefully the same happens for rating too XD)

Why yall downvoting? It is clashing

And so shall you have me.

Appreciations.

omg Spring Festival Eve round

You should try it in custom test and check if you are having the same output as your local machine or not.

• Makes Codeforces account
• Solves all 6 problems in a little over an hour, getting 5th official place
• Calls it a trash indian round with standard problems
• Refuses to elaborate
• Leaves

i do not see issue with standard problems, earlier codeforces used to give standard problem variations only if you pickup few age old problems. It is just since recent 4-6 years that more constructive and math problems are coming and i do not see any issue in both standard/adhoc as they both enhance problem solving/approaching skill.

tree dp

Did you solve C? What was your approach?

Thank you for the appreciation, it means alot. 🧡

Problem C is just two pointers :)

I don't think D was that trivial as it was pretty hard for me to see the idea. Or maybe it's just a skill issue on my part.

same... C took me 1 hour and a half ( I didn't see that I WA'd B cuz I didn't check submissions) ☠️ but D took me like 3 minutes to think of the solution and 10 minutes to code (though this was after the contest already ended so I can't submit.)

n!*n*(n-1)

see below for my attempt to prove

Suppose $$$p_i,p_j$$$ such that $$$1\le i<j\le n$$$ are distinct elements of the permutation. Their reflections are $$$p_i',p_j'$$$, respectively. If $$$p_i<p_j$$$, then they contribute only $$$2$$$ inversions because $$$p_j>p_i'$$$ and $$$p_j'>p_i'$$$. If $$$p_i>p_j$$$, then they also contribute only $$$2$$$ inversions because $$$p_i>p_j$$$ and $$$p_i>p_j'$$$. Thus, for every pair of distinct indices $$$i,j$$$, they contribute $$$2$$$ inversions. There are $$$n\choose2$$$ ways to choose pairs of indexes. So, the answer is $$$n!\cdot{n\choose2}\cdot2$$$.

Consider a specific permutation of size $$$n$$$. For any two different indices $$$i$$$ and $$$j$$$, either they form an inversion in the original array OR they form an inversion in the reverse array. Each such pair will contribute exactly one such inversion (note that there are no duplicates in the original array, since it is a permutation). There are $$$\frac{n(n - 1)}{2}$$$ pairs of indices.

This will already count all inversions that are between indices that are either both in the original array or both in the reverse array. All that's left is to count inversions where one index is in the original array and the other index is in the reverse array. Because both the original and reverse arrays are permutations, it's easy to count them: the value $$$k + 1$$$ in the original array will have $$$k$$$ values smaller than it which are present in the reverse array. Thus, the total number of such indices is $$$\sum_{k = 1}^{n - 1} k = \frac{n(n - 1)}{2}$$$.

Add them up and we have exactly $$$n (n - 1)$$$ such inversions. This is for a single specific permutation, without actually depending on what the permutation is. Since there are $$$n!$$$ permutations, the required answer is $$$n! n (n - 1) \bmod (10^9 + 6)$$$

Consider any pair of numbers $$$i$$$ and $$$j$$$, such that $$$i$$$ is to the left of $$$j$$$.

In the final array you will have ... $$$i$$$ ... $$$j$$$ ... $$$j$$$ ... $$$i$$$ ...

You can see that no matter which value is higher, each pair will give 2 inversions.

There are $$$ \frac{n(n - 1)}{2} $$$ pairs, each will contribute $$$2$$$ inversions per permutation and there are $$$n!$$$ permutations

All permutations of a given n have the same number of inversions (write a couple down and you'll see why). The number of inversions for a single permutation of n is the Gaussian sum of n — 1. For concatenated permutations, it is double the Gaussian sum. So, final answer is just n! * n * (n — 1).

Sort the input array $$$v$$$. Keep track of 2 pointers $$$left$$$ and $$$right$$$, initially both at the 1st position of the array, and keep a map that stores the frequency of all the divisors from $$$v[left]$$$ to $$$v[right]$$$. If the size of the map is not equal to $$$m$$$, then increase $$$right$$$ and update the map, otherwise increase $$$left$$$ and update the map. Keep track of the minimum difference between max and min while iterating.

Consider three cases separately,

case 1: where the inversion is completely in the first half (i.e. the original permutation),

case 2: where the inversion is completely in the second half (i.e. the reversed permutation),

case 3: where one end of the inversion is in first half and the other in the second half.

The answers for these cases will be t+(nC2-t)+(1+2+3+...+(n-1)) where t will depend on the permutation. But as you can see, the sum is simply 2(nC2) which is same for each permutation of length n. There are a total n! such permutations. So the answer is n!*2*nC2 which is n!n(n-1).

Tagging MikeMirzayanov because I think this should be applied universally across Codeforces contests, if possible.

this issue happened to me too and It made my submission for problem A later about 1 minute:(

It's as simple as the original problem (both versions need to check strong components). The original is checking "whether there is only one component with 0 in-degree", and your version is checking "whether there is only one strong component".

But subtraction modulo M may give a negative number, so you also need to add M and take modulo again.

No, it's math. For each node to be equal to 1, calculate total no. of arrays for which it is possible. Also find its relation with its height.

Maybe there's larger test in system testing…

Also there's possibility that the problem setter forgot to disable O(n^2) solutions for Div2F.

I hacked it, the system tests are too weak

If you think about it, the first vertex after the topological sort is the one which will always belong to the first SCC (i.e. a SCC with 0 indegree). So, just checking whether all the other nodes are reachable from this vertex is enough for the problem.

Yeah, D was quite frankly hard to think about.

it could be that you took a break and you need a little bit of time to de-rust..

Essentially what you want to find first is a subarray of numbers such that the number of factors of all numbers in that subarray is exactly $$$m$$$. Once you have done that, all we want to do now is to minimize the difference between the maximum and the minimum numbers in that subarray. You can do this by having $$$2$$$ pointers, and incrementing the $$$1st$$$ pointer towards the right while making sure that the number of factors remain $$$m$$$

I had a different approach from many , I sorted the array and then used a map in this map when i am traversing i take the factors of a[i] and then updated the map of these factor values by the value a[i] so in map if we have all elements from 1 to m i will see which is the minimum map value of 1 to m to find the element which must be used and then taking the difference and check if it is minimum till now.code->

You forgot to set ans = 0 in solve function before dfs call.

Check out the editorial, we have provided hints as well!

Waiting for systests too, bit odd its so late. It annoys my I can't check all the pretests before system testing finishes...