Блог пользователя Gol_D

Автор Gol_D, 2 года назад, перевод, По-русски

Привет! В 25.11.2021 17:35 (Московское время) начнётся Codeforces Round 756 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Vladosiya, Aris, senjougaharin и мной Gol_D.

Также большое спасибо God_Of_Code, oversolver, FlakeLCR, Igorjan94, Jester, KHiMAeRA, KerakTelor, Loolo, MatheusMonteiro, Resende, teraqqq, dedlocc, doreshnikov, kbats183, kocko, vsinitsynav и pashka за тестирование раунда и весьма полезные замечания.

Всем удачи!

UPD: Разбор вышел!

  • Проголосовать: нравится
  • +267
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Just one contest in the weekend tbh :/

  • »
    »
    2 года назад, # ^ |
    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!

»
2 года назад, # |
  Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As we all know, div3 is more difficult than div2

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I love div 3 very very very much♥♥

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hope everyone will have good contest.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Good luck to everyone!

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hope I will get +100 in this contest.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thaks for this great contest!!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

problem F should be before D, maybe even C

»
2 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится +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.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you explain it, please?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
              Проголосовать: нравится 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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Thank you for the help !

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    try this: 3 5

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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})

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +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)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      so how "at most" is always achievable ?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 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?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    It was just to reverse the given array.

  • »
    »
    2 года назад, # ^ |
    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!

»
2 года назад, # |
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

»
2 года назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

C is trash.

»
2 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My statue on problem A and B today :

»
2 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

E2 approach?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -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).

  • »
    »
    2 года назад, # ^ |
    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)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
      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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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

»
2 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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?

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do F without using segment trees?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used prefix sums and 2 pointers.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I did sliding window

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    dp, i think

  • »
    »
    2 года назад, # ^ |
    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)$$$

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 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?

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
            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.

            • »
              »
              »
              »
              »
              »
              »
              2 года назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
          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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same question from me...

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      got it, thanks!

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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 )

»
2 года назад, # |
  Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

This was a nice div 3 contest. Loved it.

»
2 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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...?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
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 )

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Spoiler
»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Problem C have ruined my contest ! :(

»
2 года назад, # |
  Проголосовать: нравится 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 ?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
      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]<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 года назад, # ^ |
        Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone explain how to solve problem D?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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 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 года назад, # |
  Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    about Problem F

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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).

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 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.)

»
2 года назад, # |
  Проголосовать: нравится +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.

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It was one of the best divs 3!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

Hack #772495

Hack #772489

Hack #772484

Hack #772482

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Why the ratings have not been updated yet?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

у меня рейтинг 876, почему этот контест не рейтинговый у меня ? У меня всё ещё не вышел рейтинг

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Where are the ratings?

»
2 года назад, # |
  Проголосовать: нравится 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!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Check distance of each node from root.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      still not able to figure it out.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Ratings must have been updated till now

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

А почему раунд отображается как нерейтинговый в профиле? Стоит всё же ждать рейтинг или что-то пошло не по плану?

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Tired of waiting for the rating...

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Hey!

When we will get Editorials?

»
2 года назад, # |
  Проголосовать: нравится 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?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

finally I got expert for the first time!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Editorial ?? :)

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится