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://mirror.codeforces.com/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...