Codeforces Round 914 (Div. 2) Editorial

Sorry for the weak pretests on A :(. We hope you enjoyed the round nonetheless.

1904A - Forked!

Idea: Apple_Method
Preparation: Apple_Method/oursaco
Analysis: lunchbox

1904B - Collecting Game

Idea: oursaco
Preparation: oursaco
Analysis: lunchbox

1904C - Array Game

Idea: lunchbox
Preparation: lunchbox
Analysis: lunchbox

1904D1 - Set To Max (Easy Version) / 1904D2 - Set To Max (Hard Version)

Idea: oursaco
Preparation: oursaco
Analysis: oursaco

1904E - Tree Queries

Idea: Apple_Method
Preparation: oursaco

Editorial 1:
Analysis: oursaco

Thanks to errorgorn for the solution!

Editorial 2:
Analysis: willy108

1904F - Beautiful Tree

Idea: Apple_Method
Preparation: oursaco
Analysis: Apple_Method

• 3 days ago, # ^ | Great Idea to express that in the username xd

• 4 days ago, # ^ | Lol, I could say the same about math tasks. My suggestion would be for you to go onto chess.com and practice in your free time :)

  • 4 days ago, # ^ | i don't think the problem is that you are not good at chess enough, this is really just a brain teaser, i might suggest instead to get familiar with those type of problems, a good book about this is "The art and craft of mathematical problem solving", an interesting one full of problems, although it barely talks about math, just skip the math ones since the book structure is designed for so :3

• 4 days ago, # ^ | and who can explain why this 236632847 doesn`t work ?

  • 3 days ago, # ^ | Try this sample: Correct answer would be 1 instead of 2 (from your solution) The reason is that when you use upper_bound, it give you the first element that is considered greater than your number. You should get the prev of that element for calculating difference. In the case above, 1006 - 1000 give you 6 and upper_bound give you 8, but you should look for 5

    • 3 days ago, # ^ | thanks you man !

• 2 days ago, # ^ | Downvotes shows hate or what?

• 4 days ago, # ^ | 236585544 is my solution with same approach

• 4 days ago, # ^ | Don't do that, if you check all cases by it makes your code so long and sometimes missing cases lead to WA. Instead of using you can make 2 vectors Move_x, Move_y then For from 0->7 (a knight can move 8 cases) from the Queen and King, If a cell can be moved by King and Queen your Ans++. You can refer to my code: 236529329

  • 4 days ago, # ^ | Yes, solved it like that later but thought casework would work as well. I missed a few cases in brute force case solution which I have to check

• 4 days ago, # ^ | You used set and map there. So on the worst case time complexity is O(N*N*log(N)*log(N))

• 4 days ago, # ^ | ← Rev. 2 →   0 Quite strange that commenting out the map gets it accepted because the map itself should run in O(N*logN)

  • 4 days ago, # ^ | thats why I'm asking. I really didnt understand the issue in that part of the code.

    • 4 days ago, # ^ | Your set h contains at most N ^ 2 elements. Then u lower_bound in that set for every i in array a, and run the pointer back to the beginning of the set, so the time complexity is O(N ^ 3 * logN)

      • 4 days ago, # ^ | Should the time complexity not be O(N^2 logN). As logN is required to find the upper/lower bound in the set for an element. Why there is an additional N factor in TC. Could you please explain?

        • 3 days ago, # ^ | oh my bad, i thought he runs the pointer back to the starting point after using lower_bound. Anyway, his code is correct, just need a few minor optimizations. Here the fixed code: 236638928

• 4 days ago, # ^ | ← Rev. 2 →   0 This test will TLE, courtesy of porker2008 print(1) print(200000) ans = [200000 - i for i in range(200000)] print(" ".join(map(str, ans))) ans = [min(200000, 300000 - i) for i in range(200000)] print(" ".join(map(str, ans)))

• 4 days ago, # ^ | Something like that happened to me as well. Not sure what happened there

• 4 days ago, # ^ | that is n^2

• 4 days ago, # ^ | If you reroot the tree to correctly, then each leaf in the segment tree will store the distance of a node to and this isn't limited to just 's subtree. Doing a max query on all the non blocked intervals will then find the maximum distance to all reachable nodes.

• 3 days ago, # ^ | Maybe to solve the memmory problem,you should use tree chain dissection.

• 3 days ago, # ^ | But the time complexity is O(log^2n) However

• 3 days ago, # ^ | The solution described in "Editorial 2" is online.

• 3 days ago, # ^ | Maybe you can try resubmit. I tested your solution and it is working fine (there is a bug in your solution though)

• 28 hours ago, # ^ | Imagine creating a binary lifting on the tree. You have , , etc. Here, is an auxiliary node that has edges to and . is an auxiliary node that has edges to and . Note that this is equivalent to having edges to , , and . Similar to how you always jump up the largest power of 2 that fits when you perform binary lifting, you will always add an edge to the auxiliary node with the largest power of 2 that fits. This will always require at most edge additions.

• 3 days ago, # ^ | Ive sorted the array and finding the sum which is closest to the ith element and then min of all their difference is the answer.. can anyone pointout the issue in my logic?

  • 2 days ago, # ^ | You can try this case. Spoiler

    • 40 hours ago, # ^ | Thanks!! i missed this case

• 2 days ago, # ^ | No there is no any condition on taking different (i,j) each time.

• 2 days ago, # ^ | Your two pointer approach is mostly correct except two bugs. Check out 236828774 for references.

• 37 hours ago, # ^ | You are correct. |a| means the length of the array a. Essentially, in each operation, you can pick two different elements (can be equal) from the array and compute the absolute differences and put the result back to the array. So the order of the elements in the array does not matter and you are free to reorder the array (including sorting it).