Codeforces Round #881 (Div. 3)

Hello, Codeforces!

On Tuesday, June 20, 2023 at 14:35UTC Codeforces Round 881 (Div. 3) will start.

You will be offered 7 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 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 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round 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.

Problems have been created and written by: zwezdinv, EJIC_B_KEDAX, molney, Sokol080808, meowcneil, Vladosiya.

We would like to thank:

Good luck!

• 34 hours ago, # ^ | ← Rev. 2 →   +9 thanks. I wish all participants get + rating and enjoy

• 33 hours ago, # ^ | As a tester, this is my first contest. Thanks to the authors and coordinators.

• 11 hours ago, # ^ | Matching profile pictures with molney when? :wink:

• 9 hours ago, # ^ | Thanks.. I wish everyone will participate..

• 3 hours ago, # ^ | Question E supremacy

• 33 hours ago, # ^ | really?

• 21 hour(s) ago, # ^ | how to become tester?

• 16 hours ago, # ^ | Pakistani round

• 6 hours ago, # ^ | *Graph/TreeBastic contest. It was fun to give this contest.

• 34 hours ago, # ^ | I wish you another rated dib3.

• 30 hours ago, # ^ | same , lol we are on same rating xD

  • 20 hours ago, # ^ | same lol i want to become pupil

• 33 hours ago, # ^ | Wait for Xmas magic:)

33 hours ago, # | Div 2?????!

• 6 hours ago, # ^ | ← Rev. 2 →   0 I thought I was misremembering/misreading things! Sat down to write the Div. 2 -> It's a Div. 3 -> Wrote it anyway -> NO REGRETS, GREAT ROUND.

• 28 hours ago, # ^ | How you did it? The tag is showing lgm but he us expert..

• 30 hours ago, # ^ | Thank you, fixed.

• 14 hours ago, # ^ | This round is unrated for you unfortunately :(

  • 14 hours ago, # ^ | ← Rev. 2 →   +16 I don't believe in you.

• 7 hours ago, # ^ | update：I have solved A~F1, so I can become a blue name.

  • 6 hours ago, # ^ | please explain f1

• 7 hours ago, # ^ | How to solve E?

  • 7 hours ago, # ^ | binary search on the answer once one of the arrays is beautiful it will remain beautiful, so we can use binary search. to check the condition after some number of changes, build the array and check the segments with prefix sums.

  • 7 hours ago, # ^ | I used binary search to search whether I can get a beautiful array using the first m queries. Inside the binary search you can just maintain a prefix sum with the first m queries each time to calculate the number of 1's in a segment quickly, so you can know if there is a beautiful array if pre[r] — pre[l — 1] > (r — l + 1) / 2.

  • 6 hours ago, # ^ | E can be solved by binary search.Initialize lower and upper bound of binary search as 1 and q and find whether for a given 'id' is there any beautiful segment.Since each query element is between [1-n],store value of queries [1-q] in some data structure and check for each segment whether there are more than half the length of values present. Here's my submission- 210424751

• 7 hours ago, # ^ | How to do E?

  • 7 hours ago, # ^ | ← Rev. 3 →   0 I solved it with binary search. For each iteration, maintain an ordered set of all the queries already processed. Then iterate over each segment and check how many numbers are processed using order_of_key. You can now check whether any of the segments contain more ones than zeroes. You don't have to use ordered set, but it was the first implementation that came to my mind.

• 7 hours ago, # ^ | yes you are correct, I was able to solve F1 but couldn't solve E

• 7 hours ago, # ^ | take the sum of array and number of series of consecutive negative numbers

• 6 hours ago, # ^ | and store sum in long long int

diction[num]= ans
return ans

n= int(input())
# a, b, c, k= map(int, input().split())
# arr= list(map(int, input().split()))
# arr2= list(map(int, input().split()))
# a, b, c, k= arr[0], arr[1], arr[2], arr[3]
graph = [[] for i in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[min(a, b)].append(max(a, b))
    # graph[b].append(a)

diction = {}
# ans= solve(1, graph, diction)
# print(graph, diction)
q= int(input())
for i in range(q):
    a, b = map(int, input().split())
    ansa= solve(a, graph, diction)
    ansb= solve(b, graph, diction)
    print(ansa*ansb)
# print(diction)

• 6 hours ago, # ^ | 1 4 1 3 3 2 4 3 3 1 1 3 3 2 2 Check this test case

  • 6 hours ago, # ^ | ← Rev. 2 →   0 Did you mean this? Result:

    • 5 hours ago, # ^ | Same problem for me, wrong ans for test case 4. And I'm getting the same result at you (1 4 1 1) for the above test case. Did you find a solution for it yet?

      • 5 hours ago, # ^ | Yes i got the solution. I thought of this but for some reason i did not implement it during contest. I initially used the same logic as yours but it wont work. In the question is states If a vertex u has a child, the apple moves to it (if there are several such vertices, the apple can move to any of them). It wont follow the linear order. For example: In this example there are three leaf nodes, 4, 5 and 7 if an assumption is at (4, 2), the pairs can be: (4, 4), (4, 5), (4, 7) From 2, it can go to any node, so it went 1 -> 6 -> 7. and also 3 -> 4 and 3 -> 5 This is what i wrote the code for. I had to use c++ because with python i got stack overflow and runtime error. Hope I am right on this one

    • 5 hours ago, # ^ | No, the problem is that you are assuming that for every edge, the parent is the one whose value is the lowest, but it isn't. So when you try to traverse the graph, it doesn't work as planned, because it's disconnected.

  • 5 hours ago, # ^ | ← Rev. 3 →   0 Sorry for the bad test case, check this: The output must be: 4 4 If we change the position of the node 4 with the node 2, it will give us the right answer:

    • 5 hours ago, # ^ | I kinda improvised from your previous testcase, and found the solution. THANKS! Feeling terrible for not implementing an easy logic

• 3 hours ago, # ^ | can you explain this solution? Thanks

• 6 hours ago, # ^ | You are right! That's how I tackled this problem, at least. You just need to come up with ways to merge the binary lifting answers. Calculating the total sum, best (max/min) sum, best prefix sum and suffix sum on the path will certainly be useful.

  • 6 hours ago, # ^ | Ah, I see. I keep forgetting that binary lifting can be used to store information other than the 2^k-th ancestor.

• 6 hours ago, # ^ | please explain your solution for problem F.

  • 6 hours ago, # ^ | F2 (and F1): First of all, we pre-build the tree and answer all the "?" queries later. Let's note that, if we know the min and max values between all the subsegments on the path, then all other in-between values are reachable. For example, if there are subsegments with cost -5 and 7, then there always is at least one subsegment with cost 3. Why? Because when we add a new node to the path, the cost always changes by 1, there are no jumps. We can't get from 0 to 3 without going through 1 and 2 first, for instance. All we need to do is to calculate these min and max values quickly, and then it's a simple check that minn <= k <= maxx. Now, when faced with a "?" query, let's find the LCA (Least Common Ancestor) of u and v. Where can the min be? Well, it can just be somewhere on the first path (u -> LCA), or on the right one (LCA -> v). But perhaps it touches both, meaning it's the best suffix of (u -> LCA) + x[LCA] + the best prefix of (LCA -> v) (OR the suffix of (v -> LCA), since it's the same thing, just reversed). All we need to find these values is some binary lifting. For each up[v][power], you'll need to precalc the total sum on the segment, the best subsegment sum, best prefix and suffix sum. I hope this makes sense. :')

    • 6 hours ago, # ^ | Oh my God! I wrote HLD on it...

      • 6 hours ago, # ^ | That's one of the first things that came to my mind, too! Gladly, I didn't think about it too hard and came up with a different idea, instead. ...mainly because I'm inexperienced with HLD.

        • 6 hours ago, # ^ | ← Rev. 2 →   0 Usually, if I find a solution, I implement it, even if it is a treap in Div.2 C

          • 5 hours ago, # ^ | Oh, absolutely. But just thinking "HLD, maaaaybe?" wasn't exactly enough for me to start writing the solution. :)

            • 5 hours ago, # ^ | I think it is a good problem to implement HLD. And you can also speed up it using Disjoint Sparse Table instead of Segment tree

    • 6 hours ago, # ^ | I have exactly the same idea, but i was unable to implement the solution..very sad

    • 5 hours ago, # ^ | Can you guys please provide me some practice problems where one has to keep multiple factors as attributes of a node and has to figure out ways to merge them in binary lifting and HLD ? I have solved such problems in segment tree but somehow I could not figure it out for this problem, or for example in another problem where you had to find the longest arithmetic progression in a weighted tree.

• 4 hours ago, # ^ | Really? F2 is just 2 standard well known techniques mashuped together. What part was nice?

• 7 hours ago, # ^ | this is a mult-testcase problem, you need to clear the memory for your graph, you keep adding without deleting. graph[a].push_back(b); graph[b].push_back(a);

  • 6 hours ago, # ^ | Also need to use links to vectors instead of whole vectors in dfs

    • 6 hours ago, # ^ | dont know how to do that but i guess i should have used global vector and resized it later.

      • 6 hours ago, # ^ | ← Rev. 2 →   +9 Yes, or static array. Or you can do this using & before vector's name: vector<bool> &used And do this for all vectors in dfs. You have already use link in one of vectors.

        • 6 hours ago, # ^ | ← Rev. 2 →   0 yeah but i dont know how to pass vector int graph[] as a reference

          • 6 hours ago, # ^ | ← Rev. 3 →   0 Possible way is to make graph vector<vector<int>>

            • 6 hours ago, # ^ | Yeah that makes sense.

• 6 hours ago, # ^ | It is not necessary to pass large objects to the function, they are copied in each function call. Your function is called O(n) times and we get O(n *n) memory, which is not good.

• 6 hours ago, # ^ | Why do you need BFS for D? Either way, both will work in O(n + m), so it doesn't really matter.

  • 6 hours ago, # ^ | For test case 6, it was getting maximum recursion depth exceeded in dfs.

    • 6 hours ago, # ^ | Huh. Uh, something-something, blame Python?

      • 6 hours ago, # ^ | Blaming no one, just learn the other way after checking the solution of others. Thankfully that i got error.

        • 6 hours ago, # ^ | Great mindset!

          • 4 hours ago, # ^ | But not of use, i am stuck at the rating. Any advice or guidance to improve my rating?

            • 3 hours ago, # ^ | did you implement bfs ?

• 6 hours ago, # ^ | I only know that E can: 210400778

  • 6 hours ago, # ^ | Didn't solve E but I suspect segment tree on it is an overkill.

    • 6 hours ago, # ^ | It is an overkill, but overkilling is often better than overthinking during contests. :)

      • 6 hours ago, # ^ | But that undermines the whole point of mathematicians coming up with efficient and (not always) beautiful solutions for problems =)

        • 6 hours ago, # ^ | Bu-u-uut that undermines having to write more bad code! :)

    • 6 hours ago, # ^ | Oh I didn't know binary lifting and merging range like segment tree was a thing, I guess that totally overkilled the problem lol

    • 6 hours ago, # ^ | If a person has written an algo many times, its implementation becomes simpler for him than thinking about easier solutions.

• 7 hours ago, # ^ | Even if there are multiple sample tests only the first one counts.

  • 6 hours ago, # ^ | It seems strange that there are several separate samples in a task with multitest.

• 6 hours ago, # ^ | Unfortunately, as far as I know, this has always been the case.

• 6 hours ago, # ^ | ← Rev. 2 →   0 The result shows "Accepted"

  • 6 hours ago, # ^ | edited , my original implementation and logic gave wa on tc 4

    • 6 hours ago, # ^ | how do you solutoin tc 4

• 6 hours ago, # ^ | what was the problem? I am also getting wrong answer on test4.

• 6 hours ago, # ^ | same with me. I am unable to understand why i am getting was on 4 You can check my code above

• 5 hours ago, # ^ | To those who are failing on test case 4 on problem D, it's probably because you assumed that we only traverse from low to high. But, this is not correct. ONLY THE ROOT NODE IS 1. Every other node number can be arbitrary up to n.

• 6 hours ago, # ^ | treeforces! <3

• 6 hours ago, # ^ | Binary search.

• 5 hours ago, # ^ | Besides F, D was the only graph problem...

• 6 hours ago, # ^ | In F2, what if u and v are in the same subtree?

  • 6 hours ago, # ^ | We need to lift u to LCA(u, v), and lift v to the child of LCA(u, v).

• 6 hours ago, # ^ | kth minimum can be solved by wavelet tree instead of Mo's, the complexity is O(m * logq)

• 6 hours ago, # ^ | ← Rev. 2 →   0 Here is a very elegant solution for E that I used: Maintain a fenwick tree of values. It need not be persistent, we will take care of that later. Of course we will binary search on queries (because of course, monotonicity). Let us define these three functions. : apply queries in the range . : cancel queries in the range . : on the current state, check if the array is beautiful. Trivially, can be implemented in . Also, and can be implemented in similarly. Maybe with a PST it will be faster. but without it, we don't seem to find a better time complexity for these three functions. But this time complexity seems to be enough. Why? Let us look at the time complexity deeply. There will clearly be calls to . So that part is . Now the issue is whether the other two functions will be fine. Look further. What will we find? Write down the recurrence formula. You will find this — . This recurrence seems very familiar, doesn't it? We can easily see that this recurrence is equivalent to . Now, everything seems so trivial. Time complexity at last — .

• 6 hours ago, # ^ | i used BFS and got RTE on test 7 too, i feel like it's probably a key error or something but i can't find it https://codeforces.com/contest/1843/submission/210442051

• 6 hours ago, # ^ | Because on each iteration on DFS you pass the graph to the function. It will be like 10^10 memory which gives MLE

  • 6 hours ago, # ^ | any clue what causes RTE on mine?

• 6 hours ago, # ^ | ← Rev. 2 →   0 The MLE is because pypy handles function calls differently, which means it handles setrecursion depth differently: so not only will pypy happily allocate enough RAM for the call depth you requested, the amount per level of depth might be surprisingly heavy. tl;dr setrecursiondepth on pypy gets you your MLE result before hitting any of your other bugs

  • 6 hours ago, # ^ | https://codeforces.com/contest/1843/submission/210468007 i stopped passing the graph to function and i use python 3 instead of pypy how can I conquer the runtime error?

    • 4 hours ago, # ^ | ← Rev. 2 →   0 interpolation's comment above is an incorrect extrapolation of low-level concepts like pass-by-value vs. pass-by-reference... python's already skating on top of its own system of internal objects, so VERY LOOSELY SPEAKING, since you're already interacting via levels of indirection, everything you're passing in python code is already a reference (except when it's not, but for a mutable object/collection, this story fits here better than the low-level fear of a massive copy). If you only used setrecursionlevel to undo python's safety limit, you're probably running out of stack space (stack overflow, undefined behavior, etc.). In cpython, you can essentially set the limit to whatever you want (since there's no matching pre-allocation like in pypy), but that doesn't change how much stack space there is. That's why the bits with threading and setting a custom (large, multiple of target system page size) stack size happen. Other languages also need to do this too, just that it's conveniently handled in cpp compiler parameters and commonly pre-applied due to its popularity in competitive programming (and a source of angst for other contests where people go back to running code on their own systems). Personally, my habit is to simulate bfs/dfs iteratively rather than confronting python's recursion warts or dropping into lower-level (ie closer-to-hardware/system, less abstracted-away) concepts (otherwise might as well go back to cpp). You can also look up 'bootstrap recursion' but like the thread-parameters backflips, test it out before trying to use it in contest... I'd at least rank bootstrap above the thread-parameters idea as you can keep pypy's faster-worst-case speed. But before any of that, you should probably internalize python-y ideas of mutable/immutable so you feel more comfortable predicting behavior of things like a name passed as a function parameter. Try to avoid slapping 'global' onto things in reaction to errors without understanding the underlying causes etc... happy hunting! edit: A follow-up...! The biggest weakness of the thread-parameter approach is finding the right value for the thread's stack size. See 210486427 and how it consumes 450,528 KB by requesting 268,431,360 for its thread's stack. Weirdly, that seems to be a maximum on codeforces. I tried a smaller value ~160mb and reproduced the test 7 stack overflow. Maybe there are values in between that'll work, but it's not something I'd mess with mid-contest. Other approaches mentioned (sorry for sloppiness, was poking at this whenever I got a moment this afternoon): bootstrap recursion: note the use of yield 210485286 iterative simulation: 210483619

• 6 hours ago, # ^ | Atcoderised codeforces

  • 6 hours ago, # ^ | Someone has to say it... Spoiler

• 6 hours ago, # ^ | If there is a sequence like 1 1 1 1 -1 1 1 1, we can get sum 6.

• 6 hours ago, # ^ | ← Rev. 2 →   -12 Binary search + any data structure for queries sums on segments and updates(Segment tree, Fenwick, Something like Mo heuristics)

  • 6 hours ago, # ^ | you can just use cumulative sum instead of O(log n) query data structure for range sum.

    • 6 hours ago, # ^ | Exactly! A cumulative sum would suffice for each search space from 0 to q-1 within the binary search to find the minimal change number so that at least there is one beautiful segment. 210467548

• 6 hours ago, # ^ | Still don't understand why tle... Thanks if you can help me with F1

  • 4 hours ago, # ^ | Ok I know why

• 4 hours ago, # ^ | You count space using sizeof(int) in memset() but your ans array is actually boolean type. If the required size is greater than the size of ans array, according to c++ standard of memset(), it's a undefined behaviour.

  • 4 hours ago, # ^ | 210441297 why is this giving mle and why i have to decrease no of ways of node 1 by 1

    • 4 hours ago, # ^ | Watch out your adjacency list, it's N^2.

  • 3 hours ago, # ^ | Thank you very much.

• 6 hours ago, # ^ | Passing the whole graph as an argument each time is costly. Try making it a global variable or passing the pointer to the vector, instead.

  • 6 hours ago, # ^ | (╥_╥) Works now thanks

• 6 hours ago, # ^ | In most contests of CF you don't need to worry about stack overflow when n<=2e5

  • 6 hours ago, # ^ | Is that's the case for python?

  • 5 hours ago, # ^ | ← Rev. 2 →   0 That sounds a bit vague. Moreover, there exists correct data which would cause stack overflow for almost any solution. E.g. this code should generate such data, which would hack such solutions, isn't it? I tried to hack some solution but got "incorrect test". Could you please explain why it is incorrect? #include <iostream> using namespace std; int main() { int t = 1; int n = 200000; cout << t << '\n'; cout << n << '\n'; for (int i = 1; i <= n - 1; ++i) cout << i << ' ' << i + 1 << '\n'; int q = n; cout << q << '\n'; for (int i = 1; i <= q; ++i) cout << i << '\n'; }

    • 5 hours ago, # ^ | You only output one number per query instead of two.

      • 5 hours ago, # ^ | Oh, indeed. Thank you! I tried, and it seems that the test machine has bigger stack size than mine. Is that stack size known? Because it seems like another limit in addition to the time and memory limits.

        • 4 hours ago, # ^ | I believe the stack size depends on the selected programming language. For example, I've seen many comments stating that it's low enough on Python that you basically have to use BFS. The best way to know the limit here for sure is just plain testing.

          • 4 hours ago, # ^ | Yeah, sure. But if we consider a programming language that compiled to native code (C++), then a stack size could be a part of OS environment variables (e.g. I think it might be the case for Linux). What bothers me is that even if the program passed the pretests it still can fail on some tests. So trial and error during the contest is no guarantee of correctness. So we return to the leap of faith concept :(

        • 4 hours ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/blog/entry/57646 So, there are 256 MB for stack (on C++17). By default, you have probably something like 8MB.

          • 4 hours ago, # ^ | 210441297 can you tell why mle and why i have to decrease no of ways for 1 by 1 szaranczuk

            • 45 minutes ago, # ^ | ← Rev. 2 →   0 vector<vector<int>> adj(n+1,vector<int>(n+1)); You are allocating (n+1)*(n+1) memory at the beginning, thats why you got mle. I didn't test it, but im not convinced whether you actually need to decrease this value.

          • 4 hours ago, # ^ | Cool! Thanks a lot!

• 5 hours ago, # ^ | ← Rev. 2 →   0 recursive stack limit exceeded you cannot use recursive dfs for this question in python, you should convert to iterative or use other languages where recursion isnt so heavy

  • 5 hours ago, # ^ | how about resetting max recursion depth limit?

    • 4 hours ago, # ^ | Ya, I tried it too but it gives the still says STATUS_STACK_OVERFLOW.

• 5 hours ago, # ^ | ← Rev. 2 →   0 same. the first thing I did was use BFS so that every vertex’s value in the graph only contained its children, not all neighbors. then I found the number of leaves each vertex has as descendants. but i get an RTE on test 7 and I’m not sure why. https://codeforces.com/contest/1843/submission/210442051

• 5 hours ago, # ^ | 210472002. I corrected your latest C++ submission which was getting WA. All you missed was typecasting your ans to long long.(I did it using 1LL).

• 29 minutes ago, # ^ | If you get a clean exit (error code 1) at later test case (7), you probably hit python's safety limit against deep recursion. If you get a weird result with garbage values, perhaps you used setrecursionlimit to alter that limit (python, not pypy) and overflowed the stack (thereby finding out why the limit exists in the first place). While it's possible to alter the stack size sufficiently for straightforward deep recursion to work (again, regular cpython, not pypy), that approach has some more system-specific pitfalls than other approaches, see my responses to olezhkavayn above.