### Gol_D's blog

By Gol_D, 13 days ago,

Hello! Codeforces Round #756 (Div. 3) will start at Nov/25/2021 17:35 (Moscow time). You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Vladosiya, Aris_244_, dim3x38on and me Gol_D.

Also many thanks to A_Killer, Bugman, FlakeLCR, Igorjan94, Jester, KHiMAeRA, KerakTelor, Loolo, Matheus.Monteiro, Resende, cat998__, dedlocc, doreshnikov, kbats183, kocko, meow__353 and pashka for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

• +267

 » 13 days ago, # |   +339 I really want the round to go well. I have gathered a team of ITMO students so that they can quickly prepare such rounds. For example, for this round we had to get together twice for several hours: to approve a set of problems, and I also showed and told all the details of preparation. The guys put in a lot of effort. Thanks to them!I am sometimes asked why the circle of Div3 contributors is so narrow. The fact is, for such rounds we do not have coordinators: the skills of preparing problems are very important. You need to take into account a large number of little things and accustom yourself to be careful when preparing them. The easiest way for me to do this is with a permanent team. I supervise the preparation several times, the writers themselves encounter difficulties and as a result, they already know how and what to do. In such easy problems, quality and uniformity of preparation are more important. Then you can count on a regular schedule of such rounds.
•  » » 13 days ago, # ^ |   -9 Respect++
•  » » 13 days ago, # ^ |   +2 That's so cool, good luck to them!But I miss vovuh's Contests, Why did he stop preparing for the Div3 Contests?
•  » » 12 days ago, # ^ |   +22 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
•  » » 11 days ago, # ^ | ← Rev. 4 →   0 Edit: Thank you for updating my rating. Nice contest.
•  » » 11 days ago, # ^ |   0 Thank you for all the hard-work, and thank you to all your team members as well. A lot of people has benefitted from this platform and a lot more will in the future too!
•  » » 10 days ago, # ^ |   0 Can someone help me,please https://codeforces.com/contest/1611/submission/137113575
 » 13 days ago, # |   -11 I hope this round is better than the previous div 3 round.
 » 13 days ago, # |   0 Div 3 is my favorite because I can at least solve a problem!
 » 13 days ago, # |   0 My first time seeing Unrated setters and testers (even though they have far more knowledge than me). Hoping for a good round
 » 13 days ago, # |   -42 Just one contest in the weekend tbh :/
•  » » 13 days ago, # ^ | ← Rev. 2 →   +26 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!
•  » » » 12 days ago, # ^ |   0 I guess he is talking personally.
•  » » » 12 days ago, # ^ |   0 Yes, but many times it's happen like drought
•  » » » 12 days ago, # ^ |   -26 Friday isn't weekend and i only like codeforces so I'm still waiting
•  » » » 11 days ago, # ^ |   +1 Add leetcode contest also
 » 13 days ago, # |   -7 finally, a contest i can join!
 » 13 days ago, # |   0 Is there any way to see the number of trusted/nontrusted participants registered in the contest?
•  » » 11 days ago, # ^ |   0 uncheck the unofficial checkbox in the right top corner during contest
 » 13 days ago, # |   0 Can't wait to participate! This is the first contest that I'll be able to participate in since these are usually at 9:30 AM for me. Good luck everyone.
 » 13 days ago, # |   0 As we all know, div3 is more difficult than div2
•  » » 12 days ago, # ^ |   +8 This aged well
•  » » » 12 days ago, # ^ |   0 Why does div2 have the same number of questions as div3? Doesn't it mean div3 is simpler than div2 ？
 » 13 days ago, # |   -6 I am very excited for this round Good luck to every one.
 » 12 days ago, # |   0 My first round! Good luck to everyone!
•  » » 12 days ago, # ^ |   0 Thanks
 » 12 days ago, # |   0 Man, this is gonna be fun! Good luck to other participants :)
 » 12 days ago, # |   0 I have one word to this contest, please let us go up with our rate alittle
 » 12 days ago, # |   0 I love div 3 very very very much♥♥
•  » » 12 days ago, # ^ |   +4 I'll ask you about that after the contest :))
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 So buddy how you doing? :))
•  » » » 12 days ago, # ^ |   0 This, was my first contest, I thought that I registered but it shows that I am unofficial? Do you know why>
•  » » » » 12 days ago, # ^ |   0 It's caused by the "being a trusted participant" thing that you have to be in 5 contests with at least 1 accept so that you become an official participant.
•  » » » » » 12 days ago, # ^ |   0 Oh, now I see it in the description. I guess that doesnt include the div 2 and 1 contests?
•  » » » 12 days ago, # ^ |   0 I'm sad I'm solved one problem
•  » » » 12 days ago, # ^ |   0 -80 coming:(
 » 12 days ago, # |   +1 Hope everyone will have good contest.
 » 12 days ago, # |   +1 Good luck to everyone!
 » 12 days ago, # |   0 take part in at least five rated rounds (and solve at least one problem in each of them)Great change requiring five rounds instead of two!
 » 12 days ago, # |   +1 Hope I will get +100 in this contest.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +1 hope i able to solve more than four question
•  » » 12 days ago, # ^ |   0 Hope your hope turns true
 » 12 days ago, # |   0 Hopeforces
 » 12 days ago, # |   0 thaks for this great contest!!
 » 12 days ago, # | ← Rev. 2 →   +9 problem F should be before D, maybe even C
•  » » 12 days ago, # ^ |   0 true
•  » » 12 days ago, # ^ |   -13 C shouldn't had been there at all ;)
•  » » 11 days ago, # ^ |   0 I don't think so, problem D was very simple in my view
 » 12 days ago, # |   -9 Problem D and E It's all about trees. I don't have any ideas ，It's sad
•  » » 11 days ago, # ^ |   0 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.
•  » » » 11 days ago, # ^ |   0 Hmm I personally thought that D was much easier than F. This kind of thing is quite subjective, though.
 » 12 days ago, # |   0 Nice problemset. Although, not a good idea to put 3 Tree problems in a Div3 imo. Also, can we solve E2 without binary lifting?
•  » » 12 days ago, # ^ |   +5 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).
•  » » » 12 days ago, # ^ |   0 But how does this find the min number of friends? I mean, it is not so difficult to find which friends can stop vlad at any given vertex. But still how can we know what is the minimum set of friends covering all leafs?
•  » » » » 12 days ago, # ^ |   +2 Since this is a BFS, the BFS will stop at the closest node to node 1 where his friend can stop him. Since this is a tree, stopping at a smaller distance to the root will minimize the different nodes where vlad's friends need to stop him at.Through this observation, we can try to find the closest node to the room. We can find this using the aforementioned BFS from the root.
•  » » » » » 12 days ago, # ^ |   +1 Ah, i see. At each vertex where vlad would be catched, there is exactly one friend able to catch him. And that friend cannot catch him anywhere else. Clever.
•  » » » » 12 days ago, # ^ |   0 Exactly same with my solution. you don't need to return which friend should stay, just the number.
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 11 days ago, # ^ |   0 Could you explain it, please?
•  » » » » 11 days ago, # ^ |   +1 E1:lets do an Euler tour and some structure for asking minimum in the segment. Let's do a dfs. if we will reach leaf(and it's not bad) then we will print YES otherwise NO. if we are currently at some node v and it's bad then we don't go deeper. How to check if the node vis bad or not? let's look at the depth of vertex v, it's equal to the length of the path from the root to v. then we are interested in the shortest path to all of his friends that are in the subtree of v.We can find that by asking for a minimum depth in our structure. However, there can be some vertex that is higher than v and has a shorter path than any friend from subtree of v. However, it's turn out that if we have such vertex then we will never go to v. E2 it's really easy to modify E1.just when we are at bad vertex do ans++. That's all. Have you understood it? I can also tell u about an Euler tour if u don't know what is it.
•  » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 А, кстати, ты ведь с Украины... Под какой-нибудь структурой для поиска минимума на отрезке ты имеешь в виду ДО? И каким всё же образом ты применяешь Эйлеровы пути?(Я знаю, что это, но как тут применить, до меня не доходит...)
•  » » » » » » 11 days ago, # ^ |   0 yes, I used a segment tree as such structure. with the Euler tour we can get minimum on a subtree because if we will write down all the vertices in the order of Euler traversal then each subtree will form an uninterrupted segment. E1 code 136893182 E2 code 136893182
•  » » » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 Ok, I got it.Thanks!
 » 12 days ago, # |   +3 During this round i realised that cp is not for me ;)
•  » » 12 days ago, # ^ |   +12 This round was a little harder than usual Div 3s, don't get disheartened, keep persisting, if you enjoy CP
•  » » » 12 days ago, # ^ |   0 that was needed :(
 » 12 days ago, # |   +3 Really enjoyed problem D, I like problems of this kind. thanks
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 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.
 » 12 days ago, # |   0 Can anyone tell me why my Solution of D is getting WA 1 ?? My Solution for DThank you for the help !
•  » » 12 days ago, # ^ |   +1 You can see the failing test case when you scroll to the bottom of the submission page and click on see test details.
 » 12 days ago, # |   -12 I think that the authors of this contest need to be reminded that this is a Div 3 round, not a Div 2 round. Div 3 should be ideal for beginners/newbies, this round certainly wasn't.
•  » » 12 days ago, # ^ |   0 No, the problems were not so hard as in div2 contests. Anyway problem B was much easier than in div2 contests
•  » » 12 days ago, # ^ |   0 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.
 » 12 days ago, # |   0 Im. shocked. Why I got WA in B? I can't totally find out fault in my codes
•  » » 12 days ago, # ^ |   0 try this:  3 5
•  » » 12 days ago, # ^ |   0 int solve2(int a, int b) { return min(min(a,b), (a+b)/4); }This was my solution.
•  » » 12 days ago, # ^ |   +4 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})
•  » » » 12 days ago, # ^ |   0 How to train math problems like B?I'm disgusted with the codeforces recently. My performance continues to increase in atcoder, but codeforces ruins the round depending on the problem.
•  » » » » 12 days ago, # ^ |   +1 Usually you can use binary search instead of formula in this type of tasks. Problem B of this contest is not an exception.Universal method xD (binary search: 136850518)
•  » » » » » 11 days ago, # ^ |   0 Can you please explain the check function in your code?
•  » » » » » » 11 days ago, # ^ | ← Rev. 4 →   0 Sure. X — suppositional number of teams.If we cannot have a team consisting only of programmers / mathematicians, then to get the greatest answer, each team must have at least one programmer and mathematician.Other members doesn't matter for us, so we can choose anyone from the remaining (aa + bb — 2 * x). We chose 2 members of our team previously, so aa + bb — 2*x must be greater than (4 — 2) * x — 1.That's it!
•  » » » » » » » 10 days ago, # ^ |   0 Thank you for replying and sorry for disturbing you again but I want to ask a question(4 — 2) * x — 1. why are you deducting -1? we have already taken 2 members for each team we have to take two more so the expression should be (4-2)x. why are you including the -1 term?
•  » » » » » » » » 10 days ago, # ^ |   0 Oh, sorry, my fault.The key word is "greater".aa+bb-2*x >= (4-2)*x -> aa+bb-2*x > (4-2)*x — 1
•  » » » 12 days ago, # ^ |   0 so how "at most" is always achievable ?
•  » » » » 11 days ago, # ^ |   0 a, and b is easy to achieve, you can prove (a + b) / 4 by contradiction. if (a + b) / 4 >= a, and t = a + b — k * (a + b) / 4, t can't greater than 3.
•  » » 12 days ago, # ^ |   0 Good day to die
 » 12 days ago, # |   0 For C, I just simulated the described process on the reverse of the input array and printed that as the answer. Can someone explain why this works?
•  » » 12 days ago, # ^ |   +6 It was just to reverse the given array.
•  » » » 11 days ago, # ^ |   -12 Sir, the ratings haven't been updated yet.
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 Edit : Thank you for updating my rating. Nice contest.
•  » » 12 days ago, # ^ | ← Rev. 3 →   0 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!
 » 12 days ago, # | ← Rev. 2 →   +1 Is this on the right track for G? If so any hints for what I'm missing? Split points into two grids by parity, i.e, (i + j) % 2 and solve them independently. Now in each grid, depending on the row and parity we can either go down / left or down / right (some of these moves may be invalid at the boundary col). While there are candies remaining in the grid, in each pass our priority is to remove points from the left most columns possible. So, we take the first remaining candy for each non-empty row and sort them by column. Now we process these values in sorted order and try to see can we insert them into the current path, if so we do. Checking if they can be inserted can be checked in O(log n) time by storing a set of {row, col} of the points we have taken, binary searching for the points in the currently taken path before and after the insert point (if they exist) and check if this newly added point is reachable from them. Reachability can be calculated in O(1) time by calculating the max columns left / right we can move in this row range (number of rows / 2 + 0 / 1 depending on starting row parity). This passes samples but gets WA2 so I suspect I'm still missing something.Submission in case that helps — 136926073
•  » » 12 days ago, # ^ |   +8 exactly same with my solution. just check for implementation details.
•  » » » 12 days ago, # ^ |   0 Thanks, probably an implementation mistake somewhere since I finished right at the end.
 » 12 days ago, # |   -21 C is trash.
•  » » 12 days ago, # ^ |   +19 you are
•  » » 12 days ago, # ^ |   +15 C is observation, and like allways very disapointing if not found.
 » 12 days ago, # |   -9 The difference between the difficulty level of C and D made it another speedforces round
•  » » 12 days ago, # ^ |   +1 yeah I did E1 before D
 » 12 days ago, # |   +1 Enjoyed! I dunno if it was just this contest, but every problem kept me on my toes.
 » 12 days ago, # |   0 My statue on problem A and B today :
•  » » 11 days ago, # ^ |   +1 In my defense Bustinza was just trynna hug me dude
 » 12 days ago, # |   -10 E2 approach?
•  » » 12 days ago, # ^ |   -7 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).
•  » » 12 days ago, # ^ | ← Rev. 3 →   +1 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)
•  » » 12 days ago, # ^ |   +3 Lets make some observations: Clearly if a friend exists at some node $x$, any leaf in the subtree of $x$ is unreachable. If there exists no friend in the subtree of $x$, if Ivan can reach $x$ without getting caught, he has effectively escaped. Ivan always moves down the tree and so the time he takes to reach a node is its depth in the tree. 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
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 Do you know how to solve E2, if the given graph was not a tree (i.e., it is allowed to contain cycles)?I thought of this because for my solution of E1 proof of correctness, most of the time you can just view the graph as a graph, so when trying to solve E2, I didn't think hard enough about using the tree property.
 » 12 days ago, # |   0 Noooo. I was 10 seconds away from submitting F :(:(:(
 » 12 days ago, # |   0 I think the risk/reward of all-problems-same-score rounds is taking a turn for the worse...Today's B was 1538G - Gift Set in a past life... at least I'm consistent in my failure :P
•  » » 12 days ago, # ^ |   0 How to solve B?
•  » » » 12 days ago, # ^ |   0 Answer will be minimum of { A, B, (A+B)/4 }You can refer to my solution :)
•  » » » 12 days ago, # ^ |   0 a) don't overcomplicate (by thinking of other problems...?) b) if bricking, finish a brute forcer instead of prematurely trying to avoid TLE c) similarly: don't force the brute forcer away from the answer, looking at its overall output would've shown that the answer/max is at either boundary... but for some reason during the contest, I insisted it shouldn't count the easiest a==b case's result, so... lolwoops. d) algebra works too...
•  » » » 12 days ago, # ^ |   +1 I did binary search for answer, but looks like it was an overkill.
 » 12 days ago, # |   +28 Cool problems! Excited to see more contests from these new writers!
 » 12 days ago, # |   +13 Enjoyed very much, Every Problem from B was a challenge in itself. Perfect Div.3 Round. Really loved C and D.
 » 12 days ago, # |   0 How do we do E1?My approach was to 1. make a tree with 'par' and 'lev' vectors to store the immediate parent of each vertex and the level it is in — 1 is root note/vertex. 2. now, for each of the leaf nodes, calc their distance from the root node 1 (D), and from each node that friends are on (d1, d2, ... dk — for k friends). 3. if D < d1, d2, d3 ... dk — then I should be able to reach a leaf node from node 1 before a friend can intercept me. 4. to calculate d1, d2, ... dk, I tried to use LCA But i kept getting a TLE? Is this the right idea/algo to use?
•  » » 12 days ago, # ^ |   +1 My solution was using BFS
•  » » 12 days ago, # ^ |   +1 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)
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 multi source BFS for finding out minimum distance of friends from each node. And then one DFS.136904073
•  » » » 12 days ago, # ^ |   0 No, actually 2 bfs is enough - one for min dis from all friends - one for min dis from root node 1
•  » » » » 12 days ago, # ^ |   +4 what you did is called multi-source bfs
•  » » » 11 days ago, # ^ |   0 I did the same approach but I got a Memory limit can you tell me what the wrong with my code ? https://ideone.com/CBAxuP
 » 12 days ago, # |   +3 i want you to hack my b and c as i dont feel confident enough that they are correct.thanks
 » 12 days ago, # | ← Rev. 2 →   0 .
 » 12 days ago, # |   0 RIP Arheo
•  » » 12 days ago, # ^ |   0 LMAO
 » 12 days ago, # |   0 How to do F without using segment trees?
•  » » 12 days ago, # ^ |   0 I used prefix sums and 2 pointers.
•  » » 12 days ago, # ^ |   +10 I did sliding window
•  » » » 12 days ago, # ^ |   0 why does sliding window works here?
•  » » 12 days ago, # ^ |   0 dp, i think
•  » » 12 days ago, # ^ | ← Rev. 3 →   +1 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)$
•  » » » 12 days ago, # ^ |   +1 We can use two pointer, increase right until the subarray becomes bad, increse left until it becomes good again.
•  » » » » 12 days ago, # ^ |   0 Aren't there cases where moving the left part forward will require us to move the right part back? How do we handle this with two pointer?
•  » » » » » 12 days ago, # ^ |   0 Well, if there is such a case...then I will get hacked :/
•  » » » » » » 12 days ago, # ^ | ← Rev. 2 →   +2 I doubt it would have passed pretests if it didn't work.I suspect that it doesn't affect the answer since we only want the max, even if for some $[l, r]$ we don't actually count some $[l + 1, r - x]$ as good (for some arbitrary x), it won't affect the maximum. If we wanted to count the number of good subarrays this would have failed.
•  » » » » » » » 12 days ago, # ^ |   0 But sliding window is not supposed to work with negative array values, right ?
•  » » » » » » » 12 days ago, # ^ |   +8 When L increases, R is not monotonic, but when R increases, L is monotonic, so we can use two pointers.
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   0 Let's say the current sliding window is $[L, R]$, we need to move $L$ immediately when $sum(L, R) < -s$, so when we need to move $L$, $(L, R-1)$ will be a feasible answer.If somehow when moving $L$ we need to move $R$ backward, the corresponding subarray won't be better than $(L, R-1)$, so I think the cases you mentioned don't exist.That's my thought, I am not quite sure though. Please correct me if I was wrong.
•  » » » 12 days ago, # ^ |   0 I implemented the exact idea you mentioned: my submissionI used a prefix sum + monotonic (decreasing) array + binary searchand after reading this thread I found simple sliding window works...
•  » » 12 days ago, # ^ |   0 same question from me...
 » 12 days ago, # |   +1 not a good idea to put 3 problems on tree for a div3! also problems are not sorted by difficulty ,, why is that ?
 » 12 days ago, # |   0 approach to solve D? I was able to solve E1 but got stuck on D.
•  » » 12 days ago, # ^ |   0 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.
•  » » » 12 days ago, # ^ |   0 got it, thanks!
•  » » » 12 days ago, # ^ |   0 On the topic of edge weights, here is an easy one — since we know that a child's position in a permutation is greater than its parent's we can just make the edge weight the difference in positions.
•  » » 12 days ago, # ^ |   0 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.
•  » » » 12 days ago, # ^ |   0 This should be the correct observation, as I used similar observations for my solution
•  » » » 10 days ago, # ^ |   0 can you please explain how to assign weights?
 » 12 days ago, # |   0 When editorial will out ??
•  » » 12 days ago, # ^ |   0 After completion of hacking phase and system testing, usually they post editorials.
 » 12 days ago, # |   0 I solve F using binary search without calculate the exactly time complexity. Can anyone hack me or tell me the exactly worst time complexity? :) (here is my submission 136915199 )
•  » » 12 days ago, # ^ |   0 Hey, Is there any hack penalty in Div.3 contests for those who are in rated range (< 1600)?
•  » » » 12 days ago, # ^ |   0 no
•  » » » 12 days ago, # ^ |   0 But if you hack some guy before you in the standing table, you migth raise one position.
•  » » » » 12 days ago, # ^ |   -9 Well, Thank you captain not obvious :p
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 O(n log n) probably, i'm guessing the check function is O(n)?
•  » » 12 days ago, # ^ |   0 looks like O(n^2 logn) if all A is positive.
•  » » 12 days ago, # ^ |   0 Can you explain your idea?
•  » » » 12 days ago, # ^ |   0 Just using binary search to find the biggest date which can satisfied.And brute force in checking.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +20 Hacked. Your check function is $O(n^2)$https://codeforces.com/contest/1611/hacks/772016
•  » » » 12 days ago, # ^ |   0 Can you hack my Sol too. I know it's wrong just don't know how to hack.136908596
•  » » 12 days ago, # ^ |   +8 Thank you OleschY
•  » » » 12 days ago, # ^ | ← Rev. 2 →   +10 and physics0523 :)
 » 12 days ago, # |   0 Was the criteria to put D after C just "D is tree related, C is array"? D is much easier than C in my opinion.
•  » » 12 days ago, # ^ |   0 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.
•  » » 12 days ago, # ^ |   0 anyway, tree is a data structure and needs knowledge to do DFS.
•  » » » 12 days ago, # ^ | ← Rev. 4 →   +2 Funny thing is, you don't need DFS for D. Knowing the permutation and the ancestor is enough. You can just iterate all your nodes.
 » 12 days ago, # |   +4 This was a nice div 3 contest. Loved it.
 » 12 days ago, # |   +25 Thanks for this round. My best ranking ever...
•  » » 12 days ago, # ^ |   0 Can you write the implementation for F and E1 in short if possible ?
 » 12 days ago, # |   0 Hello, It's my first time participating. I'm Korean and I use a translator to write it down. I have a question. My code number B (wrong answer on test 2) : https://codeforces.com/contest/1611/submission/136932156 I don't understand. testcase 33 29 -> 14? Isn't this answer 15? 2 programmers, 2 mathematicians, 14 teams. 3 programmers, 1 mathematician, 1 team. The remaining number is programmer 2, mathematician 0. Total team 15...?
•  » » 12 days ago, # ^ |   0 You failed on 19 11 ->7，you returned 6
•  » » 12 days ago, # ^ |   0 The error code refers to the third test case which is 19 programmers and 11 mathematicians .The answer for this case will be 76 teams of 3 programmers and 1 mathematician and 1 team of 1 programmer and 3 mathematicians
•  » » » 12 days ago, # ^ |   0 I understood. Thank you!
•  » » 12 days ago, # ^ |   0 yeah 15 is the correct answer according to me.
 » 12 days ago, # | ← Rev. 2 →   0 how problem's difficulties get determined? because even though problem B was way harder than C , difficulty of B is 800 and C is 1000. I mean the difficulties should be based on how hard the idea of the problem is. (it's just my opinion problem B may has been easier for you than problem C :") . but generally problem's difficulties doesn't make scene T_T )
•  » » 12 days ago, # ^ |   +21 You can see less participants solved C than B. That’s best proval.
•  » » 12 days ago, # ^ |   0 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
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 I think Problem B is more mathematical and logic-based. Since there have to be exactly 4 members in each team, you can easily determine the number of teams = (mathmatics+programmers) / 4. All you have to do now is make sure if there is at least 1 math or 1 programmer in each team.
 » 12 days ago, # |   +2 E1 was almost similar to cses problemset graph problem : Monsters. https://cses.fi/problemset/task/1194
 » 12 days ago, # |   0 If the CF predictor is right then this was my last Rated Div 3 ;) SpoilerAssuming I don't fall again
•  » » 12 days ago, # ^ |   0 Subtract 10 points))) It's always
•  » » 12 days ago, # ^ |   +1 Carrot is better. +25
•  » » » 12 days ago, # ^ |   0 Can you share the link to this predictor?
•  » » » » 12 days ago, # ^ |   +1
•  » » » 11 days ago, # ^ |   0 Can Carrot or CF calculate based on trusted/nontrusted participants?
•  » » 11 days ago, # ^ |   0 assume predictor-10
 » 12 days ago, # |   +2 Problem C have ruined my contest ! :(
 » 12 days ago, # |   0 Problem E2 (using python): I get runtime error on testcase with n=20000 k=10000 136941508 Anyone has any idea what the problem might be ?
•  » » 12 days ago, # ^ |   +1 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).
•  » » » 12 days ago, # ^ |   +1 I used a stack instead and it worked. Thank you!
 » 12 days ago, # |   0 Here are the video Solutions to problem A-F in case you are interested.
•  » » 12 days ago, # ^ |   0 Can you please briefly explain the (segment tree + binary search) solution for F about which you talked in the video? TIA
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 Let me give you my version.Firstly we define sum[i] as the prefix sum of a.If a[l]+……+a[r]+s<0,sum[r]-sum[l-1]+s<0.sum[r]
•  » » » 11 days ago, # ^ |   0 Two pointer may be a better solution than data structure.For L=1,we move for the farthest R.Then we just move L and minus it,if we can't get to a further R,we can't get a better solution than L=L-1,just skip it.If we can,move R check if it is a better solution.
 » 12 days ago, # |   0 someone please explain the solution of problem B.
•  » » 12 days ago, # ^ |   0 first you need to check how many teams of 4 members u can form ,from the total of participants which is max_possible =(a+b)/4 , this satisfies the first constraint , now for the second constraint we need 1 programmer and 1 mathematician in each of these teams so IF both a (number of mathematicians) and b (number of programmers) are larger or equal than max_possible we just return the max_possible ELSE we just need to return the minimum of a and b since once we exhaust one of these two numbers we can't form anymore teams according to the second constraint hence the solution return min(min(a,b),(a+b)/4)
•  » » » 11 days ago, # ^ |   0 thanks buddy!
 » 12 days ago, # |   0 camy solution can anyone tell me why this solution doesn't work?
 » 12 days ago, # |   0 can anyone explain how to solve problem D?
•  » » 12 days ago, # ^ |   0 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 4You 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 answerfor 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.com/contest/1611/submission/136944858
•  » » » 11 days ago, # ^ |   0 thank you ^^
 » 12 days ago, # |   +42 I know this will be pretty controversial, and though it is uncommon to say things like this about R1000 problems, but C was quite an interesting problem. It had probably been a very long time since I found a sub-1500 problem with an observation that can qualify as an "aha" moment, and this definitely meet the criteria. I guess I just want to say kudos to the problemsetters for coming up with such a nice easy problem.
 » 11 days ago, # |   0 https://codeforces.com/contest/1611/submission/136953503I'm TLE(12). Can someone help me see how to optimize it？
•  » » 11 days ago, # ^ |   0 about Problem F
•  » » » 11 days ago, # ^ |   0 I think using “Prefix Sum” ans “Sparse Table” in your check can lead to O(nlogn).And you can use “Binary search on Segment Tree”,the Binary Search and check is O(nlogn).But I suggest you to use Two Pointers,it's O(n).
•  » » » » 11 days ago, # ^ |   0 Use dichotomous answers ， How to O(n) check ?
•  » » » » » 11 days ago, # ^ |   0 By using Prefix Sum and Sparse Table.It's O(n)
•  » » » » » » 11 days ago, # ^ |   0 I found that using the double pointer algorithm is very clear to solve this problem. It took me only 5 minutes to finish it.https://codeforces.com/contest/1611/submission/136959303
•  » » » » » » » 11 days ago, # ^ |   0 Yes.I also used double pointers during the contest.It's convinient.
•  » » » » » 11 days ago, # ^ |   0 Above all,get the prefix sum of ai.if a[l]+a[l+1]+……a[r]+s<0 it is sum[r]-sum[l-1]+s<0=> sum[r]
•  » » 11 days ago, # ^ |   0 Let's see your checker. It's up to O(n^2),your time complexity may be wrong.
 » 11 days ago, # |   0 A good round!All of the problems are good,but I think I may see the F somewhere else.(And the difficulty gap between E1 and E2 may be too low.)
 » 11 days ago, # |   +15 Hello MikeMirzayanov,Some contestant hacked problem A . But inside hacked solution code I found out that they intentionally kept a test case written inside the solution so that the solution can be hacked. It seems unethical.
 » 11 days ago, # |   0 It was one of the best divs 3!
•  » » 11 days ago, # ^ |   0 Yeah Nice and interesting problems :).
 » 11 days ago, # |   0 did somebody notice that the solution of problem B has been out by someone and due to which the submission on that problem increases.
 » 11 days ago, # |   0 in problem E1 I used the following approach1.Apply BFS from node 1 and calculate distance of each leaf node form node 1.2.Apply multisource BFS from all the friend nodes, and calculate distance of leaf nodes find a leaf node(other than 1) whose distance from node 1 is smaller than its distance from friend node Please tell if there is anything wrong with the above approach.Thanks in advance ^-^
•  » » 11 days ago, # ^ |   0 You're on track.
 » 11 days ago, # |   +8 Can someone tell me what on earth was these hacks???Hack #772495Hack #772489Hack #772484Hack #772482
•  » » 11 days ago, # ^ |   0 Looks like an intentional hack. Although I don't understand why would someone do so
•  » » » 11 days ago, # ^ |   +3 It might be possible that it his fake accounts and he/she is submitting just so that he can get hack points
•  » » 11 days ago, # ^ |   0 Another intentional one 136921479
 » 11 days ago, # |   0 Tutorial pls :(
 » 11 days ago, # |   0 what is meant by timelimit per test case is 2 ?
 » 11 days ago, # |   0 Can someone talk about how to solve F using binary search on Segment Trees? It'll be a big help thank you!
•  » » 11 days ago, # ^ |   +1 Take prefix sum array(lets name it dp) and build a segment tree for range minimum queries. Suppose you need to check if the segment from L to R is good, then all you need is to check if (s+the minimum inside that subsegment) — dp[L-1] is >= 0. Binary search from each index for max length good subsegment to maximize the answer.Here's my submission : https://codeforces.com/contest/1611/submission/136905894
•  » » » 11 days ago, # ^ |   0 Thank you so much!
 » 11 days ago, # |   +2 Why the ratings have not been updated yet?
 » 11 days ago, # |   0 Problemset was great. But I did feel that there were harder concepts (not problems) for a div.3 round.
 » 11 days ago, # | ← Rev. 2 →   0 I tried a DP implementation for Problem F which passed the first pretest, but gave WA verdict on the subsequent ones. Can anyone please help me out in finding what is wrong in the logic?My submission: 136929173
 » 11 days ago, # |   +17 Where are the ratings?
•  » » 11 days ago, # ^ |   -10 this round was unrated due to that ratings are not updated
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 Check description , its written over there that : "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."
•  » » » » 11 days ago, # ^ | ← Rev. 3 →   0 yes bro now it is updated!
 » 11 days ago, # |   0 Help! why am getting WA for D. https://codeforces.com/contest/1611/submission/136977033 saying that expected d[p[i]] < d[p[i+1]] when i output d[p[i]] for all i it is sorted means condition is fullfilled!
•  » » 11 days ago, # ^ |   0 Check distance of each node from root.
•  » » » 11 days ago, # ^ |   0 still not able to figure it out.
•  » » » » 11 days ago, # ^ |   0 In test case 1, both nodes 4 and 5 are at distance 4 from root 3. Your dist vector maintains weights of edges, not distance from the root. You cannot use that directly. You can try using a vector that maintains distance of each node from root.
•  » » » » » 11 days ago, # ^ |   0 ah i see! thanks i'll try that
 » 11 days ago, # |   +13 Ratings must have been updated till now
 » 11 days ago, # |   +3 Tired of waiting for the rating...
•  » » 11 days ago, # ^ |   +3 I'm in full solidarity with you
•  » » 11 days ago, # ^ |   +5 As a stonk investor, I cannot secure my profit...
 » 11 days ago, # |   +11 Hey!When we will get Editorials?
•  » » 11 days ago, # ^ |   0 Also ratings are not changed yet.
•  » » » 11 days ago, # ^ |   0 Its updated now
•  » » » 11 days ago, # ^ |   +5 You just have 0 delta.
 » 11 days ago, # |   0 Can anyone help me? I actually submitted my code twice from two accounts which has led to a violation of rules.Can someone tell me what proof can I give for that and where?
•  » » 11 days ago, # ^ |   0 Well, you used two accounts. What do you want to proofe now?
 » 11 days ago, # |   0 finally I got expert for the first time!
•  » » 11 days ago, # ^ |   +3 Congrats :)
 » 11 days ago, # |   0 Was able to solve 5 problems in this div 3 contest but the most painful part is that I fell short of expert by just 10 points..... Hoping to reach it soon!
 » 11 days ago, # |   0 I solved 7 problems, and I became Specialist. Thank you!
 » 11 days ago, # |   0 Hello All! For a few hours, the rating got updated but now it vanished. Is it happening the same with others as well?
•  » » 11 days ago, # ^ |   0 Yes!! I had the same confusion.
•  » » 11 days ago, # ^ |   0 Does anyone have an idea why this happened?
•  » » » 11 days ago, # ^ |   0 Now this contest is unrated;
•  » » » » 11 days ago, # ^ |   0 Ratings are updated
 » 11 days ago, # |   0 Editorial ?? :)
•  » » 11 days ago, # ^ |   0 We'll provide it tonight
 » 11 days ago, # | ← Rev. 4 →   0 Unable to access problem statements. Spoiler
 » 10 days ago, # | ← Rev. 2 →   0 Can someone help me,please https://codeforces.com/contest/1611/submission/137113575