I think problem B and C required relatively simple ideas but I found them hard to implement. Problem B was uncomfortable to write yet doable. However, I just lost too much time over problem C trying to figure out how to implement "properly".

good job!

here, have my downvote

I hate weak pretests.

Huge difficulty gap between C and D.

And I hate weak pts.

Pretests were so bad and huge gap between C and D, will definitely have to downvote on this one.

138767795

Input - 24 4 8
My output - 9 8 10 7 11 6 12 5 13 4 14 15 3 16 17 2 18 19 1 20 21 22 23 24

• Checker comment
• wrong answer expected a=4 and b=8, but found 7 8 (test case 4)

1. Doesn't my solution have 4 local maximums.

Problem B and C are quite easy but hard to code.

The contest was not so good but problem D and E are interesting but quite bad pretests!

everyone talking about downvote, and I am wondering how the "maroonrk" (rank 1) solved B using topological sort :p

Since the editorial for MEX counting isn't yet available, I'll share my solution.

Let $$$dp_{ijk}$$$ represent the number of ways to determine the first $$$i$$$ elements of the array such that the MEX of these elements is $$$k$$$, there are $$$j$$$ unique values higher than $$$k$$$ in the array, and values greater than $$$k$$$ are indistinguishable. For example, the arrays $$${0, 2, 3 }$$$ and $$${0, 3, 2 }$$$ would be equivalent under this scheme, in total contributing $$$1$$$ to the value of $$$dp_{3, 2, 1},$$$ because both include two distinct values higher than the MEX in the second and third positions, but $$${2, 0, 3 }$$$ would be distinct from these arrays because the fixed $$$0$$$ is in a different position, and $$${0, 2, 2 }$$$ is distinct from all three of these arrays and would contribute to $$$dp_{3, 1, 1 }.$$$ Note that there are $$$O(K)$$$ choices for $$$k$$$, so there are $$$O(NK^2)$$$ states in total.

There are three types of transitions.

1: Transitions to a higher MEX. The above DP formulation is useful because it makes these transitions feasible. First, determine the least MEX we can transition to ($$$k+1$$$, if doing so does not violate the given constraint, $$$b_i - K$$$ if $$$k+1 < B_i - K$$$; it is impossible to increase the MEX if $$$k \geq B_i + K$$$). If this MEX is $$$k+1$$$, then the only possible transition to this MEX is to make the next element of the array $$$k+1$$$. However, if this MEX is $$$k+1+x$$$ for some $$$x$$$, then we must choose $$$x$$$ of our unique values larger than $$$k$$$ that have appeared so far and assign them to the values $$$k+1, \cdots, k+x.$$$ There are $$$\frac{j!}{(j-x)!}$$$ ways to do so.

Afterwards, we can transition to a MEX of $$$m+1$$$ rather than a MEX of $$$m$$$ by taking another value larger than $$$k$$$, assigning it to $$$m-1$$$, and making the next value of our array $$$m$$$. Therefore, after performing the above step, we can iterate through our new DP table and transition from $$$(i, j, k)$$$ to $$$(i, j-1, k+1)$$$ while multiplying by $$$j$$$. This allows us to process these transitions in $$$O(N^2K)$$$ time in total.

2: Transitions in which the next element has appeared already. There are $$$j+k$$$ ways to choose this element, giving us $$$j+k$$$ ways to transition from $$$dp_{ijk}$$$ to $$$dp_{(i+1)jk}.$$$

3: Transitions in which the next element is higher than $$$k$$$ and has not appeared before. Because elements higher than $$$k$$$ are indistinguishable, there is only one such transition, taking us from $$$dp_{ijk}$$$ to $$$dp_{(i+1)(j+1)k}.$$$

Once we're finished, we can find our answer by iterating through the values of $$$dp_{Njk}.$$$ Note that we must assign the remaining $$$j$$$ larger values to numbers greater than $$$k$$$ before adding the result to our answer.

My code is available at https://codeforces.com/contest/1608/submission/138771063.

When I see C and D:

$$$\text{ }\text{ }$$$ Are you sure this is Div.1+Div.2?

Please can somebody say what's wrong with my approach? 138778827

A few nice problems ≠ A nice contest. I have to downvote. Hope they can write a nicer contest :(

the problems are great and challenging,but the samples and pretests are so weak.

It's a great contest, the problems are nice, and the pretests can judge your real skill in an efficiency way.

What is the purpose of the 1sec. time limit for problem C? Usually these O(nlogn) problems have 2sec...

Is it possible to use Discretization and 2-D Binary Indexed Tree to solve E by O(36(logn)^4)?

I want to describe an approach without graphs for $$$C$$$ which is a bit different from editorial and other submissions I have seen.

Sort the people by their first map strength. Let us name them $$$1,2,\dots, N$$$. Now obviously person $$$N$$$ can win the tournament as he has the largest first map strength.

Let us assume we have the answer for all people from person $$$i+1$$$ to person $$$N$$$. Now let's look at person $$$i$$$. He can beat all people from $$$1$$$ to $$$i-1$$$ as he has greater 1st map strength.

I claim that person $$$i$$$ can win if and only if there exists a person $$$j$$$ such that:

• $$$i \lt j$$$
• Person $$$j$$$ can win the tournament
• 2nd map strength of person $$$j$$$ $$$\lt$$$ than $$$max_{k = 1}^{i}$$$(2nd map strength of person $$$k$$$)

By moving right to left, we can keep track of the minimum so far of the 2nd map strength of a winnable person and compare with prefix max of 2nd map strengths. My submission 138786776

I really liked this problem. It's very nice!

I came here to plug my solutions video, but looking at the downvotes just made me sad and I would just like to say, the contest was nice guys, weak pretests sucks yea, but problem C was nice atleast and I even got +ve, so win for everyone.

Yes, I still plugged my video, I ain't no saint.

Can someone explain fivedemands's solution for problem C ? Thanks in advance.

I have an alternate solution to C.

Sort all players by $$$a_{i}$$$. Now iterate in reverse. Player $$$n - 1$$$ can always win so we start with $$$i = n-2$$$. If $$$max(b[0],b[1],...,b[i]) > min(b[i+1],b[i+2],...,b[n-1])$$$ then this player can win, otherwise break since no smaller players can win now. Note that the $$$b_i$$$ order is different than input since the array is now sorted by $$$a_{i}$$$.

https://codeforces.com/contest/1608/submission/138742092

Can someone please tell me why did we check a+b+2 < n condition in B question and how did we construct the order since the editorial is a little tough to understand.

Can anyone explain their approach for D ?

Problem B is definitely obnoxious problem, but I spent an hour and found quite elegant solution. I'm sure you are already noticed that if abs(a - b) > 1 there is no solution.

But how can we construct an example of needed permutation?

Firstly consider this example: $$$n = 10, a = 3, b = 3$$$ i.e. we have permutation:

$$$[1,2,3,4,5,6,7,8,9,10]$$$ and we need to make 3 maximums and minimums somehow

let's play a little with it, let's swap 2 and 3

$$$[1,3,2,4,5,6,7,8,9,10]$$$

And now by a single swap I made one maximum 3 and minimum 2. Now let's swap 4 and 5

$$$[1,3,2,5,4,6,7,8,9,10]$$$

So 5 is new maximum and 4 new minimum. So by swapping I can produce 1 maximum and 1 minimum. And for test case $$$a = 3, b = 3$$$ you just can do another swap and there you go, you have needed permutation $$$[1,3,2,5,4,7,6,8,9,10]$$$ with 3 maximums and 3 minimums.

So what to do if we have $$$a \neq b$$$? Let's see if $$$a > b$$$, and you will see how to do $$$a < b$$$ too:

Let's consider previous test case $$$n = 10, a = 3, b = 3$$$ but with $$$a = 4$$$.

We ended up with $$$[1,3,2,5,4,7,6,8,9,10]$$$ with 3 maximums and 3 minimums. Where 1 extra maximum can appear? Actually we didn't used the right-hand side of array. So in this test case to produce extra maximum we can swap 9 and 10. And now we have $$$[1,3,2,5,4,7,6,8,10,9]$$$ which is an answer to this test case. How to produce the minimum instead of maximum? If you store permutation in reverse order you can replace 2 last elements as well.

I hope my explanations were clear, also see my implementation: code

Is it just me or someone else solution as well TLE in system check but submitting the same code getting AC for Problem C? TLE:TLE CODE

SAME CODE AC:AC CODE

TadijaSebez Is it due to tight limit or load on server during system check????

UPD: verdict changed!! thankyou

Yeah...

In Problem C DFS solution was easy, can anyone give a link to someone's code who did with 2 pointer method? Or anyone here have a video editorial who did it with 2 pointer method?

Please share the link. Thanks for help :)

Hey guys, could you explain the approach to problem D? This is what I tried.

The 1st observation is number of WW & BB should be same. Then the remaining strings will be either WB or BW. Now we can split into 3 cases, Number of ??, Number of B? or ?B & number of ?W or W?. Somehow we need to make equal number of WW & BB using these cases. For B? or ?B, only BB is possible. Similarly for ?W or W?, only WW is possible. But for ??, anything is possible.

After finding the number of ways of making WW's equal to BB's, then for '??', there are 2^count ways. For ?B, only WB is possible similarly if there is ?W only BW. So the answer is Let c0 = count of ??, c1 = count of ?W or W? and c2 = count of ?B or B?. Then the answer is

C(c0, i) * C(c0 — i, j) * C(c1, k) * C(c2, l) * 2 ^ (c0 — i — j). where (i + k) — (j + l) = 0.

I was able to optimize the second part using vandermonde identity. i.e C(c1, k) * C(c2, l). i.e with the difference of d, where d = k — j, answer is C(c1, d) or C(c2, d) depending of sign of d, * C(c1 + c2 — d, c1 or c2) depending on sign. But cant optimize the 1st part of ??. i.e. Number of ways of getting the difference diff, where diff = number of WW — number of BB. and putting the rest to 2 ^ (c0 — i — j).

Any help in optimizing would be highly appreciated. Thanks.

B is cancer but C is so cool.

people downvoting should atleast appreciate the effort it takes to conduct a contest.

I think problem D is easier than C.

Problem C :

am trying to solve it by (Binary Search) :

https://codeforces.com/contest/1608/submission/138819932

can any one help me what is the testcase I get WR in it

I have never heard of any Div.2 or Div.1+Div.2 contests that C is a graph problem and D is a Maths problem like this.

The problems are very nice, but I think the contest is awful. I have had my donwvote.

C'mon at least include the sample codes in the editorials

Could someone please tell me whats wrong with my C solution?

I am essentially doing a reverse dfs.

can somebody tell simple countercase for my solution link

Got a WA on TC2 for Problem C, not sure why. https://codeforces.com/contest/1608/submission/138834566

Can somebody tell me what is going wrong in my code or provide any counter case. Thanks

For those who wonders, there exist simple dp solution for C, which requires 25 rows of code Here is it: https://codeforces.com/problemset/submission/1608/138843789

For problem C, I have a much more simple way to do (at least for me). It doesn't require any graph knowledge, just sort and greedy.

Observation : If $$$p$$$ can be a winner, and $$$q$$$ can beat $$$p$$$, then $$$q$$$ is also a winner.

First, we construct two array, sorted by their strength, and also store their index. I use pair<int,int> to store these data.

After that, we maintain $$$min_{1}, min_{2}$$$. They are the minimum required strength in map-1 or map-2 to become winner. And we travel from the top of these two array, since we also store their index, we can keep $$$min_{1}, min_{2}$$$ decreasing by check map1 and map2 in a rotation. Until it doesn't decrease anymore we stop our algorithm and output.

Actually, My strategy in this problem is really similar to this https://leetcode.com/problems/jump-game/. maintain the minimum winnable number on both map .

Since we sort, the time complexity will be $$$O(n\log(n))$$$.

Here's my code. 138742846

My approach to C:

Sort the array A and B which contains the value and their index in pair. Observe that the player having max A or having max B value will always win. Now for some other player to win, he would wish that either all the remaining players have lesser A value or lesser B value. For eliminating larger B values, we can use max A value to eliminate those players, and similarly, for larger A, we can use max B values. When we are eliminating any element from the B array, we would keep track of the min A value till that suffix of B array, which will denote that our A pointer can be decreased to that min A value and similar operation for B pointer. It will be continued until the current index of A and B corresponds to the same player in the original array.

My code : https://codeforces.com/contest/1608/submission/138845902

In editorial of C,

To find the set of such nodes, we can run DFS from the player with maximum ai.

Why only ai? Don't we have to take maximum bi also?

I don't understand about the weak pretest for problem D

好

for question C

https://codeforces.com/contest/1608/submission/139063539

logic -→

sorting the strengths take the highest strength index and insert it in set check the next strength , if lies in set then remove it else add it and make its flag as 1(included in answer). if set becomes empty then other players with smaller strength won't be able to win anyone which we have already counted

Why the hell, the tutorial for problem C is so confusing. According to the tutorial, we should use DFS but using graphs not only increases the size of code but it also makes it confusing. There is a really simple approach using maps and the tutorial could have been written in a simple manner keeping in mind that not everyone around here is a Candidate Master or Master.

Meanwhile,I think the editorial is hard to understand.

holy shit, F is one of the most beautiful problems I've ever seen, upsolved in a day! although my $$$O(n^2k)$$$ passes in 3900ms... xD