Weak pretest of F even do not have cases of disconnected :(

+1

bruh its icpc style, every problem carries the same score.

Never thought u to be a saint, I believe that u r a slut , haha

Same here bro!T_T

In fact,Educational Rounds is good for our rating :)

Tbh, Atcoder ABC's are more educational nowadays.

In my experience with educational rounds, the only 'educational thing' with them is that they are not educational :/

What is freedom?

what is the lie, what is the truth, what to believe

I too am crying due to the 3rd question... :_)

1st problem : combinatorics

2nd problem : modulo

But you also need to be careful with other special situation!

The answer will only depend on the largest number, second largest number, and their respective frequencies. I'll denote largest number as $$$max$$$ and second largest number as $$$secmax$$$. If the count of $$$max$$$ is greater than $$$1$$$, then the answer will $$$factorial(n)$$$ (all possible permutations), because all permutations will be nice in this case. If the difference between $$$max$$$ and $$$secmax$$$ is greater than $$$1$$$, then the answer will be $$$0$$$ (since no permutation can be nice in this case).Now the only case remaining is when $$$max=secmax+1$$$ and count of $$$max$$$ equals $$$1$$$. Here, a permutation will not be nice only if $$$max$$$ is behind all the $$$secmax$$$ in the permutation. So the number of not nice permutations will be $$$nCr(n,(countmax+countsecmax))*factorial(n-countmax-countsecmax)*factorial(countsecmax)$$$. The final answer will be $$$factorial(n)$$$ — ($$$no.$$$ $$$of$$$ $$$not$$$ $$$nice$$$ $$$permutations$$$), which we calculated above.

I missed the registration, but my guess is

Just separate the points into two parts one where the x of the point matches with any of the x of vertical roads and other part where the y of the point matches with the y of any horizontal road. these two parts may or may not be disjoint as it is also possible that point's x as well as y matches with any vertical and horizontal road then this point will be the part of both parts.

Now solve the answers for both the parts separately ->

for 1st part Sort it using a comparater which sorts first according to y and then according to x. Now just iterate one by one on the points since the points are sorted using the above comparater so the points will be divided into groups which lie on the same horizontal line(same y) and this group is also sorted according to x also. Now we can see that the vertical roads divides the x axis into some segments. (x0,x1) (x1,x2) (x2,x3) ........

for calculating the answer we will maintain one array f of size (n-1) where ith element represents the number of points that lie in the ith segment and whose y is also less than the current y(on which we are currently at in the iteration).

f[i]=number of points which lie in the segment (x[i],x[i+1]) end points not included.

for finding the segment-number of a point (a,b) we can easily find it using binary search(using lower_bound in c++)

now let us assume we are at a point (a,b) so to find out the pairs that this point will make with other points that are already visited in the iteration we can make use of the array f.

first we find the segment to which the point (a,b) lies and then the bad pairs which it makes is equal to f[segment-number]. because f[segment-number] stores the number of points that lie in that segment in the previous horizontal line (y<b). This can be easily observed that bad pairs are the points which strictly lie inside same segment(end points not included) and which do not lie on the same line.

Now when we move to the next horizontal line (y>b) then we need to add the point (a,b) to its respective segment(increment value of f[segment-number]) so that it can contribute the points which lie on the horizontal line above it.

what we can do is we can maintain a cnt variable which stores the number of points which lie on the same horizontal line and in the same segment of x axis.When we move to next segment then we can just update the value of f[prev-segment-number]+=cnt.

for 2nd part-

Sort it using a comparater which sorts first according to x and then according to y. It's exactly same the difference is just the change of axis now we will iterate vertical line by line and in increasing order of x.Now the y axis is divided into segments.

Link to my code- https://codeforces.me/contest/1569/submission/128325617

These guys now even seem to be crowd-sourcing solutions.

If it makes you feel better I forgot take mod of the final answer.

Just try for individual competitions... using brute force suppose there are two players i and j, if any of them is aiming for 1, you can simply draw the match '=', if both are aiming for 2, think... if A has won in any of the previous matches... declare B and the winner and A as the looser, else B as the winner....

In the end just check if all of the players were able to achieve their goals or not... the problem is solved...

This is my submission... ignore everything above //MARK :- SOLUTION=====...

I hope this will help... ;)

128236197

First of all separate all the players who are satisfied with not losing a single match from those who need to win at least one as games need to be won or lost only in the case of the latter.
Now, a valid solution can only exist if the number of unique pairs that can be formed between the players of the second type is greater than the number of players of the second type.
Why?

in the last case, basically its the number of ways to put the maximum element in any spot while there exists atleast one or more nextMax on it's right side

you can see my submission here https://codeforces.me/contest/1569/submission/128280479

For k=5 you just can solve for k=4 (2^15) and get the solution with meet-in-the-middle (2^8).

I tried to reduce the possibilities of backtracking by fixing the sum of eliminated people for every stages. I believe that will be enough to pass the tests in 4 seconds.

It's pretty hard for C, lots of combinatorics

No fast IO?

? Couldn't it be solved in $$$\mathcal O(n)$$$?

Here's the approach:

First, obviously, if all the characters in the string are 'a' or 'b', there must be no solution. Otherwise, there must be a position $$$x$$$ that makes $$$a_x\neq a_{x+1}$$$, scan this string directly to find the position $$$x$$$. The answer is $$$x,x+1$$$.

UPD: AC Submission 128343804

I guess codeforces has a good system to detect cheaters

Woah bro, chill, there are way worse people who are still alive than those who cheat in online contests.

This fails: 1 5 22222