added, thank you

Why do I get the strange idea that some people just copy what I say?

Obviously Codeforces Contest .

7:35 pm*

Do you really think any of the players were going to participate?

CF round at 20:05(UTC+6). Is it possible to reschedule the El Clasico?

So I can't participate in contest

It is clearly mentioned in the bold letters in the post that "**It is rated for the participant with rating lower than 2100**

Me, but I am not proud of it

Even Edu Rounds are rated for those users.

Vladik

after the contest

me too

How about make another Rated Round with 10 munutes delay together? It seems very good idea to make great round!

I am not sure but I think it is taken care of bcoz for problem B some people who have submitted after me have gotten more points thus compensating for the 10 min delay.

I've read the logs — the issue with the unexpected error during code submit was fixed in less than 5 minutes.

Queues also were fixed quickly. Plus the longest time to judge was only 459 seconds (most submissions which faced a queue were judged much faster).

Are you sure that less than 5 minutes of such a breakdown plus some queues at the start are worth sacrificing a month of work of problem writers?

Instead of conducting many contests under Div2 and setting easy problems. Better Codeforces should conduct more contests as they are doing now, but the contests must be distinguished between Div 2 and Div 3 perfectly.

Because it is sometimes disgusting to wait for Div 2 contest and the finding Div3 or Div4 level problems in the contest :(

See the thing is A is cakewalk, B is easy constructive, C is cool and enjoyable and D seems tricky...perfect for a Div2 contest.

I don't understand your point at all. You solved only 2 problems this contest, and took 30 minutes to do so. Didn't you need to think? What's bad about you solving 2 problems out of 6? Are you lacking challenging problems?

Bro see the difficulty level this was a perfect div2 contest. A require some brain as always it involves.

B trick of just using 2 and 3 as prime numbers.

C good problem gives you deep intuitions of Binary search . The way the binary search used was brilliant.

D. DFS problem with a lot of insights and mathematics of finding averages and numbers.

E Another cool problem involving a lot of thinking.

F No idea.

Also see the balance between the number of submissions. '

A perfect Div2 contest must look like this only!

The blog under which you are commenting itself has a upvote/downvote button. Why don't you use that

Agreed, perhaps a rating for problems as well since a contest may be made of problems written by different writers. This will give feedback to the writers on what people find interesting (and what they dislike), and also help people prioritize better problems during practice.

Traverse the array from 1 to r and maintain a segment tree of the last position of X. For each ar[i], find min(lpos(1),lpos(2),...,lpos(ar[i]-1)). If this is > lpos(ar[i]), then ar[i] will occur in the final array.

Corner case : For 1 to occur in the final array, there must be a non-1 element in the array.

Didn't solve it during contest, but if you could find subarray mex queries in time $$$F(n)$$$ then to find if mex $$$x$$$ is possible for any subarray, consider all pairs of consecutive positions where $$$x$$$ lies, say $$$i_1, i_2$$$ for one, then you need to check if $$$mex(a[i_1 + 1, i_1 + 2..., i_2 - 1]) == x$$$. Since there are atmost $$$O(n)$$$ such pairs you can solve the problem in $$$O(n F(N))$$$.

One way to solve subarray queries is using Mo's algorithm and keep elements not in current segment in a set, giving $$$F(N) = \sqrt{n} \log n$$$

I think you can just keep track of the recursion and calculate how many numbers you can pick for position middle.

Put x in position pos, and assume the array is decreasing before x and increasing after x (so it's in sorted order, with x in its spot). Now run the binary search and see how many numbers of this array it accesses. Say there are "l" numbers that it accesses that are less than x, and "r" numbers that it accesses that are greater than x.

Then it suffices to find l numbers < x and r numbers > x to place in their correct positions. Then can rearrange the other numbers however. It follows the answer is $$$\dbinom{n-x}{r}\cdot r! \cdot \dbinom{x-1}{l}\cdot l! \cdot (n-r-l-1)! $$$

hint for n = 6

1 1 1 1 1 0
0 1 1 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1

I got runtime error on test 5?

Yeah! Have u figured it out?

I did for a while, then got stuck on pretest 4 on later submissions >:(

Some things I fixed to get AC (no clue which caused the WA):

• Only add single direction edge from $$$p$$$ to $$$i$$$ instead of adding it in both directions and storing parents of nodes (this shouldn't have made a difference but it did)
• Depending on how you calculate the answer, intermediate calculations can overflow long long, so I switched to __int128.

Pretest 7 was when there is only one child of 1. After correcting my mistake in this case my solution passed pretests

Yes

The answer is the maximum of ceil(sum/sz) for each node. Sum denotes the sum of all a[x] in the node's subtree, and sz denotes the number of leaves inside node's subtree.

I don't have a rigorous way to show this but this informal explanation is sort of intuitive if you think about it.

https://codeforces.me/contest/1436/submission/96577050

Try it before system tests =))

i think test case of C is designed to attack O(nlogn) solution

Wouldnt it give WA when sum will exceed int bounds?

I just gave up and wrote the $$$O(n)$$$ solution after my $$$O(n \times log(U))$$$ solution got TLE twice.

Only the last one.

i dont think so.

Yeah happened with me for C, got a resubmission penalty and last submission was considered so overall a good negative in total score.

Man… I did B in 13 minutes and I resubmitted after two hours a better solution, just to make sure it will pass the official tests. I didn't know that only the last submission counts. Now instead of +25 I get -60.

Try including a value for fac(0) as well.

Think about the order of the binary search. Every position in the array has a distinct binary search order. By tracing the direction of the B.S., you can reconstruct possible values for each "middle" position.

Just stimulate a binary search and check the path that binary search follows in there and count smaller and bigger for x during that simulation. After that its simple PnC .

in binary seach we make jumps from mid to val that we need..., so when ever we come to some point. we just need to check weather to jump forward or backward.

to jump foreward we need to put some value at that cell that is less than x. choices that we have is n-x for this cell in array. to jump backward we need to put some value at that cell that is greater than x. choices we have is x-1.

now if you make two jumps forewards, choices to put values in those cells are n-x for first cell and n-x-1 for next cell. total choices are (n-x)*(c-x-1)

after you fill and calculate all cells where you jumped. the permutation of remaining cells doesn't matter. you can permute all the rest of cells.

eg 4 1 2

we jump to 2 (4+0/2).

val[2] == 1(x) [it is given value at 2 is 1]

choices that we have to fill jumping indexes is 1 (only 1 was filled no other choice).

ans = 1 * fac(3), [3 is number of cells whose value doesn't matter]

ans = 6

its strange because as i checked it doesn't ouput correct on the test below

16 927

59 72 10 90 73 72 75 47 30 59 90 16 76 82 48 28

it outputs NO while the correct answer is YES|:

No, it won't pass because you can probably do 2*10^8 low level operations per second in cpp.

Hmm. So 10 minutes of queue affected your chances at trying ABC, and therefore you couldn't solve them? Don't talk bs man.

I tried using binary search. But got various results except AC.

My idea : Binary search on the minimum no. of citizens bandit can catch

So, basically i fix the answer and check if its valid or not.

https://codeforces.me/contest/1436/submission/96583528

UPDATE : I understand that its failing because of overflow.

Each leaf can take atmost 2e14 citizens. So, we carry forward 2e14 to 1e5 nodes. So, the value goes to 2e19 which leads to overflow.

Yes, you can. 96579469

We will go like this 61 30 15 23 27 25 24

First, if you use the pseudo code provided, the positions are 61, 30, 15, 23, 27, 25, 24.

Second, if a position is to the right of pos, you should use numbers that are greater than x, since you want to go to the left. Similarly, if a position is to the left of pos, you should use numbers that are less than x, since you want to go to the right.

So the answer is actually 116! * 81 * 80 * 79 * 78 * 41 * 40 Check.