That's so cool, good luck to them!

But I miss vovuh's Contests, Why did he stop preparing for the Div3 Contests?

I really liked this division 3 (I did it virtually, since I couldn't attend the real thing). Right mix of implementation and observation AND a reasonable solve count for each problem. Some non-trivial data structures, like sparse table/segment tree, and some really satisfying problems! I hope to see more rounds like this in the future :D

Can someone help me,please https://codeforces.net/contest/1611/submission/137113575

Really?

26th Nov: Codeforces Div 2 && Codechef FizzBuzz (Rated for Div 2 & Div 3)

27th Nov: Codechef Nov Lunchtime && ATcoder Beginner Contest

28th Nov: Codeforces Deltix Round && AtCoder Regular Contest

29th Nov: Codechef C.O.D.E.R.S (Rated for Div 2 & Div 3)

:) It's raining contests! Yay!

This aged well

I'll ask you about that after the contest :))

hope i able to solve more than four question

Hope your hope turns true

C shouldn't had been there at all ;)

I don't think so, problem D was very simple in my view

You could actually do D without trees too! For ex., I created a map m1 with the keys as vertices and the values as their parents. I then created another map m2 with the given permutation, with the keys as the vertices given in the permutation and the values as the summation of edge weights going from the root to that vertex, started from 0, and incremented the value by 1 for each subsequent vertex. I then just used m2[i] — m2[m1[i]] to get the weight of the edge connecting the ith vertex to its parent, m1[i]. If this was negative at any point, I returned -1, otherwise I printed out these weights. My only peeve with the contest was the placing of D, I feel that F should've come before it as it was easier.

I solved E2 using a modification from my E1 solution, which used 2 BFS. The first BFS would find the minimum distance of each node from one of Vlad's friends and store the value in an array. The second BFS would be from room 1. This BFS finds a room with only one corridor. For every node that the BFS visits, it checks whether there is vlad's friend that could arrive at the node faster than vlad. If vlad's friend can't get to the node quicker than vlad, then continue the BFS, else stop the BFS (this is the E1 solution).

For the E2 solution, modify the final BFS. If there is an instance where there is a node where the BFS stops (vlad's friend can get there quicker than vlad), then we can observe that one of vlad's friends has to stop him, so we can observe that one of vlad's friends has to stop him at that node. So, add 1 to the result (the minimum amount of friends required to stop vlad) by 1 (you can also use the answer to the first problem to check whether it is impossible to stop vlad).

I did E1, E2 with Euler tour.it was the first that come to my mind. I can explain that solution if someone is interested in it.

This round was a little harder than usual Div 3s, don't get disheartened, keep persisting, if you enjoy CP

can you explain your approach to problem D as I'm very confused as to how to set the distance of the edges...!

[UPD: Solved} the biggest hint for me was to use the permutation p itself. And No dfs is not required as you can just iterate through the permutation and assign the weights in increasing order and check while assigning if the sum of weights from parent to that node(say total_weight of that node) is equal to the total_weight of the previous element. if equal then just assign the weight accordingly for the condition given in the question to be true.

You can see the failing test case when you scroll to the bottom of the submission page and click on see test details.

No, the problems were not so hard as in div2 contests. Anyway problem B was much easier than in div2 contests

I can solve 7 problems during the contest and G just after the contest (so disappointed to miss it in the contest). For Div.2, usually 4 or 5.

try this: 3 5

A team needs at least one programmer. Hence the number of teams can be at most a. A team needs at least one mathematician. Hence the number of teams can be at most b. A team needs at least four members. Hence the number of team can be at most = total people / 4 = (a + b)/4.

So finally the number of teams = min of above three = min({a, b, (a + b)/4})

Good day to die

It was just to reverse the given array.

Because element with max value will always be either on first or last position(if ans is not -1), so comparing any other element with it will lead to insertion of that element. Try writing few test cases, u will get it!

exactly same with my solution. just check for implementation details.

you are

C is observation, and like allways very disapointing if not found.

yeah I did E1 before D

In my defense Bustinza was just trynna hug me dude

I solved E2 using a modification from my E1 solution, which used 2 BFS. The first BFS would find the minimum distance of each node from one of Vlad's friends and store the value in an array. The second BFS would be from room 1. This BFS finds a room with only one corridor. For every node that the BFS visits, it checks whether there is vlad's friend that could arrive at the node faster than vlad. If vlad's friend can't get to the node quicker than vlad, then continue the BFS, else stop the BFS (this is the E1 solution).

For the E2 solution, modify the final BFS. If there is an instance where there is a node where the BFS stops (vlad's friend can get there quicker than vlad), then we can observe that one of vlad's friends has to stop him, so we can observe that one of vlad's friends has to stop him at that node. So, add 1 to the result (the minimum amount of friends required to stop vlad) by 1 (you can also use the answer to the first problem to check whether it is impossible to stop vlad).

for each node, keep track of the minimum distance among all friends in the current subtree to reach this node in minFriendDist[node].

then do DFS from the root. as soon as distFromRoot >= minFriendDist[node], increment ans by 1 and return (stop exploring)

Lets make some observations:

1. Clearly if a friend exists at some node $$$x$$$, any leaf in the subtree of $$$x$$$ is unreachable.

2. If there exists no friend in the subtree of $$$x$$$, if Ivan can reach $$$x$$$ without getting caught, he has effectively escaped.

3. Ivan always moves down the tree and so the time he takes to reach a node is its depth in the tree.

4. His friends always stay in place or move up the tree to intercept him (if he's below them he has escaped from them).

So with these, we just need to check for each node $$$x$$$, can some friend in the subtree of $$$x$$$ reach $$$x$$$ before Ivan can. If so he can protect this subtree alone and the answer for this subtree is $$$1$$$. Otherwise the subtrees of each of the children of $$$x$$$ with need to be protected separately and the answer is the sum of the answers for the child nodes.

To check if any friend can protect this node $$$x$$$ we just need to store the closest friend in the subtree and check if it is at most the depth of the node.

Code — 136900309

How to solve B?

My solution was using BFS

You only need 2 BFS runs: From a) Vlad and b) from your friends. Then just check all leaves (inDegree==1 && not root) if at any leave there is distanceVlad < distanceFriends -> Vlad wins.

O(2*(V+E)) = O(2*(V+V)) = O(V)

multi source BFS for finding out minimum distance of friends from each node. And then one DFS.

136904073

LMAO

I used prefix sums and 2 pointers.

I did sliding window

dp, i think

While I got AC on the problem using sparse table, I suspect we can instead do this:

• Process the subarrays in reverse order of their starting points ($$$n$$$ to $$$1$$$) and maintain a strictly decreasing deque(*) (or reversed vector since we only insert at the front) of the values in this range.

• Now we can just binary search on this deque to find the first bad position rather than using some RMQ structure.

(*) — By this I mean we will store a strictly decreasing deque along with index which decreases at the first possible index. Like suppose for the array $$$[1, 3, -1, 0, 6, 4, -1, 3, -7]$$$, where (x, y) represents a tuple of (value, index):

• At $$$i = 9$$$, we will have $$$[(-7, 9)]$$$

• At $$$i = 8$$$, we will have $$$[(3, 8), (-7, 9)]$$$

• At $$$i = 7$$$, we will have $$$[(-1, 7), (-7, 9)]$$$

• At $$$i = 6$$$, we will have $$$[(4, 6), (-1, 7) (-7, 9)]$$$

• At $$$i = 5$$$, we will have $$$[(6, 5), (4, 6), (-1, 7) (-7, 9)]$$$

• At $$$i = 4$$$, we will have $$$[(0, 4), (-1, 7) (-7, 9)]$$$

• At $$$i = 3$$$, we will have $$$[(-1, 3), (-7, 9)]$$$

• At $$$i = 2$$$, we will have $$$[(3, 2), (-1, 3) (-7, 9)]$$$

• At $$$i = 1$$$, we will have $$$[(1, 1), (-1, 3) (-7, 9)]$$$

So clearly in each stage it suffices to just binary search on this deque. As to how we actually maintain this, at position $$$i$$$ we simply pop all elements $$$\geq a_i$$$ from the front of the deque and push $$$(a_i, i)$$$

same question from me...

Observe that the edges must be sorted so that we can build the tree starting at root, then add each vertex by add a child to some vertex in the tree.

Because else there will be a parent with bigger weight than a child, what is not possible.

So just add each vertex to the tree, and give the edge some weight so that the weight of the vertex is max so far.

I didn't pay attention to it until the last 5 minutes, so I coudln't solve it.

But this is what I thought: the permutation has to start with the root or it is impossible. That is because dist(root, root) = 0, so, when sorting, it will always come out first.

Second, for a given vertex v, it has to appear in the permutation in the same order as the simple path from root to v, otherwise it is impossible. Why? since we are adding edge weights, an ancestor will have less edge weight than it, so, when the permutation is sorted, the ancestor must appear first.

If both these conditions are true, then it is sort of easy to assign weights.

Hey, Is there any hack penalty in Div.3 contests for those who are in rated range (< 1600)?

O(n log n) probably, i'm guessing the check function is O(n)?

looks like O(n^2 logn) if all A is positive.

Can you explain your idea?

Hacked. Your check function is $$$O(n^2)$$$

https://codeforces.net/contest/1611/hacks/772016

Thank you OleschY

Depends on personal preference, obviously. For me C was quite easy as well, as long as you get the observation for C you can probably solve it in less than 2 minutes. It's just an array reversal.

anyway, tree is a data structure and needs knowledge to do DFS.

Can you write the implementation for F and E1 in short if possible ?

You failed on 19 11 ->7，you returned 6

The error code refers to the third test case which is

19 programmers and 11 mathematicians .

The answer for this case will be 7

6 teams of 3 programmers and 1 mathematician and 1 team of 1 programmer and 3 mathematicians

You can see less participants solved C than B. That’s best proval.

Both there and there are easy ideas, but in my opinion there was a very simple idea for C, but it was difficult to notice it. You can see for how much I decided and for how much C

Subtract 10 points))) It's always

Carrot is better. +25

Python dislikes deep recursion beyond ~1000 calls deep which is probably happening with your recursive dfs. There are some workarounds documented here and there on this site, but I've tended to just do things iteratively (as long as it's not too entirely gnarly to do so).

Can you please briefly explain the (segment tree + binary search) solution for F about which you talked in the video? TIA

I thought of an ad-hoc solution. Try to find a solution such that the first element on the permutation has dist 0 from the root, the second dist 1 from the root, the third dist 2, and so on.

Giving an example (same from the problem text)

5 3 1 3 3 1 3 1 2 5 4

You want the dist array to be [ 0, 1, 2, 3, 4 ] so dist(root, 3) = 0, dist(root, 1) == 1, dist(root, 2) == 2, dist(root, 5) == 3, dist(root, 4) == 4.

So, you have to notice one thing: it's impossible to have a node a such that dist(root, a) <= dist(root, father_of_a) since all the edges must have positive value. You need to check this before by seeing if the position of 'a' in the permutation is before the position of 'father_of_a' in the permutation, but there's also another way of doing it that I'm going to talk about below.

So now you know that dist(root, a) > dist(root, father_of_a)

This way you can build a constructive algorithm to find an answer

for the root, you know that dist(root, root) == 0 for the other nodes: dist(root, a) = w(edge from father_of_a to a) + dist(root, father_of_a) so w(edge from father_of_a to a) = dist(root, a) — dist(root, father_of_a)

Since you know the values for the distances (following that method in the beginning), you now know how to calculate w.

This value must be positive, since dist(root, a) > dist(root, father_of_a). If at some point you have a negative value, that's also an indication that finding an answer is impossible.

My solution, for reference: https://codeforces.net/contest/1611/submission/136944858

about Problem F

Let's see your checker. It's up to O(n^2),your time complexity may be wrong.

Yeah Nice and interesting problems :).

Looks like an intentional hack. Although I don't understand why would someone do so

Another intentional one 136921479