Gol_D's blog

By Gol_D, 2 years ago, In English

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, senjougaharin and me Gol_D.

Also many thanks to God_Of_Code, oversolver, FlakeLCR, Igorjan94, Jester, KHiMAeRA, KerakTelor, Loolo, MatheusMonteiro, Resende, teraqqq, dedlocc, doreshnikov, kbats183, kocko, vsinitsynav and pashka for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

  • Vote: I like it
  • +267
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +339 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    That's so cool, good luck to them!

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Just one contest in the weekend tbh :/

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    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!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As we all know, div3 is more difficult than div2

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I love div 3 very very very much♥♥

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope everyone will have good contest.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck to everyone!

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope I will get +100 in this contest.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thaks for this great contest!!

»
2 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

problem F should be before D, maybe even C

»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Problem D and E It's all about trees. I don't have any ideas ,It's sad

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm I personally thought that D was much easier than F. This kind of thing is quite subjective, though.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problemset. Although, not a good idea to put 3 Tree problems in a Div3 imo. Also, can we solve E2 without binary lifting?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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).

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exactly same with my solution. you don't need to return which friend should stay, just the number.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain it, please?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          А, кстати, ты ведь с Украины... Под какой-нибудь структурой для поиска минимума на отрезке ты имеешь в виду ДО? И каким всё же образом ты применяешь Эйлеровы пути?(Я знаю, что это, но как тут применить, до меня не доходит...)

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

During this round i realised that cp is not for me ;)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Really enjoyed problem D, I like problems of this kind. thanks

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my Solution of D is getting WA 1 ?? My Solution for D

Thank you for the help !

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Im. shocked. Why I got WA in B?

https://codeforces.com/contest/1611/submission/136901877
https://codeforces.com/contest/1611/submission/136919221

I can't totally find out fault in my codes

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try this: 3 5

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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})

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so how "at most" is always achievable ?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It was just to reverse the given array.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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!

»
2 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, probably an implementation mistake somewhere since I finished right at the end.

»
2 years ago, # |
  Vote: I like it -21 Vote: I do not like it

C is trash.

»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

The difference between the difficulty level of C and D made it another speedforces round

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Enjoyed! I dunno if it was just this contest, but every problem kept me on my toes.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My statue on problem A and B today :

»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

E2 approach?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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).

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Noooo. I was 10 seconds away from submitting F :(:(:(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Cool problems! Excited to see more contests from these new writers!

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Enjoyed very much, Every Problem from B was a challenge in itself. Perfect Div.3 Round. Really loved C and D.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My solution was using BFS

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    136904073

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, actually 2 bfs is enough - one for min dis from all friends - one for min dis from root node 1

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i want you to hack my b and c as i dont feel confident enough that they are correct.thanks

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F without using segment trees?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used prefix sums and 2 pointers.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I did sliding window

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp, i think

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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)$$$

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      We can use two pointer, increase right until the subarray becomes bad, increse left until it becomes good again.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, if there is such a case...then I will get hacked :/

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            Rev. 2   Vote: I like it +2 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              When L increases, R is not monotonic, but when R increases, L is monotonic, so we can use two pointers.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I implemented the exact idea you mentioned: my submission

      I used a prefix sum + monotonic (decreasing) array + binary search

      and after reading this thread I found simple sliding window works...

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same question from me...

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

not a good idea to put 3 problems on tree for a div3! also problems are not sorted by difficulty ,, why is that ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

approach to solve D? I was able to solve E1 but got stuck on D.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got it, thanks!

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This should be the correct observation, as I used similar observations for my solution

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 )

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This was a nice div 3 contest. Loved it.

»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Thanks for this round. My best ranking ever...

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 )

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

E1 was almost similar to cses problemset graph problem : Monsters. https://cses.fi/problemset/task/1194

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the CF predictor is right then this was my last Rated Div 3 ;)

Spoiler
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem C have ruined my contest ! :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here are the video Solutions to problem A-F in case you are interested.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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]<sum[l-1]-s.

      Then to every l,we can get the nearest r that min(sum[l] to sum[r])<sum[l-1]-s.

      r-1 is the last student l can service.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

camy solution can anyone tell me why this solution doesn't work?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain how to solve problem D?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.com/contest/1611/submission/136944858

»
2 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1611/submission/136953503

I'm TLE(12). Can someone help me see how to optimize it?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    about Problem F

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Use dichotomous answers , How to O(n) check ?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          By using Prefix Sum and Sparse Table.It's O(n)

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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]<sum[l-1]-s.

          You can use binary search if there is a array up to len

          for each l, just check the minimum of s[l~l+len-1] is lower than a[l-1]-s or not. If not ,a[l]~a[l+len-1] is ok.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.)

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

These are the solution https://codeforces.com/contest/1611/submission/136954440 https://codeforces.com/contest/1611/submission/136948337 https://codeforces.com/contest/1611/submission/136939066

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was one of the best divs 3!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem E1 I used the following approach

1.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

  1. 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 ^-^

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone tell me what on earth was these hacks???

Hack #772495

Hack #772489

Hack #772484

Hack #772482

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It might be possible that it his fake accounts and he/she is submitting just so that he can get hack points

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another intentional one 136921479

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone talk about how to solve F using binary search on Segment Trees? It'll be a big help thank you!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why the ratings have not been updated yet?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problemset was great. But I did feel that there were harder concepts (not problems) for a div.3 round.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Where are the ratings?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check distance of each node from root.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      still not able to figure it out.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Ratings must have been updated till now

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Tired of waiting for the rating...

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hey!

When we will get Editorials?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, you used two accounts. What do you want to proofe now?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

finally I got expert for the first time!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello All! For a few hours, the rating got updated but now it vanished. Is it happening the same with others as well?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial ?? :)

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it