Hello, Codeforces!

On Jun/20/2023 17:35 (Moscow time) 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:

Vladosiya for coordinating the round.

MikeMirzayanov for Polygon and Codeforces platforms and testing.

tute7627 for red-black testing.

ace5, sevlll777, oursaco, lightseba, gmusya, pavlekn, vrintle, tolbi for yellow testing.

diskoteka, moonpie24, SashaT9, shell_wataru, MGod, Phantom_Performer, tarattata1, alex.kudryashov, Restricted, sdyakonov for purple testing.

Alex239, MrEssiorx, olyazyryanova, marzipan, Pa_sha, Rudro25, azureglow, IHateGeometry, ivan.alexeev, krigare for blue testing.

sahal, exhausted, viteli, prohamer80 for green testing.

Good luck!

**UPD:** Editorial.

As an author, I recommend you to participate in it.

thanks. I wish all participants get + rating and enjoy

As a tester, this is my first contest. Thanks to the authors and coordinators.

Matching profile pictures with molney when? :wink:

Thanks.. I wish everyone will participate..

Hey , I have been flagged by system even though I wrote the entire code .Please look into this . Sol ing till d gave me negative rating i don't get it :(

wow !! Vladosiya is back :)

Question E supremacy

Hope so it would not be like the CF round 880

Wish this contest is not bad like Round 880.

As a tester, this round is bombastic.

really?

OMG!!!

.

Pakistani round

*Graph/TreeBastic contest. It was fun to give this contest.

As a tester,

~~I tasted some apples~~I tested some cool problems.first unrate div3,GL&&HF for everyone:)

I wish you another rated dib3.

and one more thing,how can i become a tester

If you have time you should write this round! Because it give you a lot of rate if you are good in programming. Please like it!

As a Tester,

SpoilerHope you will enjoy the nice problem-set as i did.

As a tester, you must participate! Problems are interesting!

hope to became pupil

same , lol we are on same rating xD

same lol i want to become pupil

Waiting for this round. Best of luck everyone

As a participant, I hope to become yellow one day.

Wait for Xmas magic:)

Div 2?????!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.

As a tester, blablabla...

ahmet23 orz!..

How you did it? The tag is showing lgm but he us expert..

I think there is a mistake in the typo, it should be Codeforces, not Codefoces, missing a "r" letter

Thank you, fixed.

As a friend of the tester, I don't know good this round, or not

As a tester, I recommend you to take the contest :)

Wish this isn't bad as 880 ;-;

As a Participant looking forward for a good round.

As a blue tester, I may say that I am a blue tester.

hope the problems are well balanced

Best of luck to everyone .

I hope can solve four or five problems

hope to get CM today! :D

This round is unrated for you unfortunately :(

I don't believe in you.

As a non-tester I will test this round during contest.

I'll test this round at 20:05 :-)

Grey Tester missing !!

omg a div 3, I'm so glad!

i need to esceb from newbi rank

As a participant, I hope to become blue one day.

update：I have solved A~F1, so I can become a blue name.

please explain f1

Can I become expert today?

Unfortunately, no gray testing!

It's a good one, nothing like 880 :)

is this a div4 round?

contest of trees

E and F are really good problems.

How to solve E?

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.

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.

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

How to do E?

I solved it with binary search. For each iteration, maintain an

ordered setof all the queries already processed. Then iterate over each segment and check how many numbers are processed usingorder_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.yes you are correct, I was able to solve F1 but couldn't solve E

Long Long anyone ?

take the sum of array and number of series of consecutive negative numbers

GLA++

and store sum in long long int

friendly contest (●'◡'●)

friendly contest！！！！！！

Can someone tell me why my solution for D gave wrong answer for testcase 4

`

def solve(num, graph, diction): if len(graph[num])==0: diction[num]= 1 return 1 if num in diction: return diction[num] ans=0 for item in graph[num]: ans+= solve(item, graph, diction)

for _ in range(int(input())):

`

1 4 1 3 3 2 4 3 3 1 1 3 3 2 2 Check this test case

Did you mean this?

Result:

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?

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

anynode, so it went 1 -> 6 -> 7. and also 3 -> 4 and 3 -> 5This 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

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.

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:

I kinda improvised from your previous testcase, and found the solution. THANKS! Feeling terrible for not implementing an easy logic

Finally a nice and easy contest after a string of hard ones

Although E is binary search, technically an easy sqrt solution exists in n^1.5 by processing queries n^0.5 at a time.

can you explain this solution? Thanks

Just like binary search, the solution is based on using prefix sums to check if any segment has been satisfied.But we use up n^0.5 queries at a time instead of checking prefix sums every query like brute force. If we see any segment satisifes after the current bacth of n^0.5 queries we can just check all those individually. Otherwise we skip and start with the next batch.

Is this a specific algorithm? If yes, can you provide me with a reference article or a similar problem?

its just sqrt optimization, google

Sure, Thanks.

How would F2 be solved? Initially I thought it was continuing the idea of max/min subarray sum but on arbitrary paths, and that we could use binary lifting to find the LCA, then to find max subarray sum on path from u to v, take best of the three cases: u to LCA, v to LCA and some path that crosses the LCA. But didn't find a good way of doing it. Am I on the right track or is it something completely different?

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.

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

As a participant, I enjoyed this contest a lot, especially the F2 problem! :D

please explain your solution for problem F.

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

Oh my God! I wrote HLD on it...

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.

Usually, if I find a solution, I implement it, even if it is a treap in Div.2 C

Oh, absolutely. But just thinking "HLD, maaaaybe?" wasn't exactly enough for me to start writing the solution. :)

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

For me, the HLD solution gave TLE's despite my best attempts to optimize it. I later switched to the sparse tables approach.

I tried to find mistake for a while. You should use links to vector arr in

`init_tree`

and`dfs_labels`

. But even after adding links, the solution gets TLE.May be you have a problem on multiple test cases — I don`t know.

My solution passed without any problems: 210446339

May be, you should remove vectors and structs to improve the constant of solution.

I was using galen colins template, havent written my own template ever .. perhaps I should try doing it.

I have exactly the same idea, but i was unable to implement the solution..very sad

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.

Really? F2 is just 2 standard well known techniques mashuped together. What part was nice?

I liked the implementation. Also it's a great introduction for binary lifting in my opinion.

belongs as a cses task not a codeforces problem (and max subarray sum exists as cses problem too just not on tree)

0 thinking (i took ~2mins to come up with the solution) and then lots of implementation (if you are doing from scratch like me, ~20mins), when the problem itself is standard. [i have 2nd solve on the problem btw]

International master for a reason

i'm sorry, i didn't mean for it to be a flex, i just do not like putting standard problems in cf rounds

Can anyone tell me why memory limit exceeded on this submission https://codeforces.com/contest/1843/submission/210459020

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);`

Also need to use links to vectors instead of whole vectors in dfs

dont know how to do that but i guess i should have used global vector and resized it later.

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.

yeah but i dont know how to pass vector int graph[] as a reference

Possible way is to make graph

`vector<vector<int>>`

Yeah that makes sense.

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.

Can you solve D by only using BFS? or would get TLE and have to use DFS?

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

For test case 6, it was getting maximum recursion depth exceeded in dfs.

Huh. Uh, something-something, blame Python?

Blaming no one, just learn the other way after checking the solution of others. Thankfully that i got error.

Great mindset!

But not of use, i am stuck at the rating. Any advice or guidance to improve my rating?

did you implement bfs ?

Learning good themes is always great, but lots of practice is at least as important, even more so for the first few rating groups, provided you know the basics. Just keep going and don't give up. Practicing keeping composure during contests is useful, too. Don't rush too much, don't worry about your rating, don't give up, even if the problem seems too tough, etc.

Thanks a lot !!

Can F2 be solved with persistent segment tree?

I only know that E can: 210400778

Didn't solve E but I suspect segment tree on it is an overkill.

It is an overkill, but overkilling is often better than overthinking during contests. :)

But that undermines the whole point of mathematicians coming up with efficient and (not always) beautiful solutions for problems =)

Bu-u-uut that undermines having to write more bad code! :)

Oh I didn't know binary lifting and merging range like segment tree was a thing, I guess that totally overkilled the problem lol

If a person has written an algo many times, its implementation becomes simpler for him than thinking about easier solutions.

As far as I know , all of the sample tests don't cost any penalties when getting WA or RE and so forth , but why problem F has cost me a penalty when I got WA in test 2 although it's included in the sample test . IS it a problem with the system testing or anything else ? thanks in advance.

Even if there are multiple sample tests only the first one counts.

It seems strange that there are several separate samples in a task with multitest.

Unfortunately, as far as I know, this has always been the case.

Tasks E and F1 are very interesting, and the condition is very incomprehensibly written in task D. It also seems to me that there is too big a gap between D and E. It was too difficult to guess the key idea in E for its place in div3.

Nice contest, problems were from various topics, and their difficulty and overall time to solve were adequate

I read A statement wrong. Then, 10 minutes later I read it wrong again. 40 more minutes later, I read it wrong yet again. Finally, 80 minutes after the beginning of the contest, I read it right.

in d i took the count of leaf nodes reachable from u and v . their product should have been the answer but what is wrong with this one which failed on test case 4

https://codeforces.com/contest/1843/submission/210448804

The result shows "Accepted"

edited , my original implementation and logic gave wa on tc 4

how do you solutoin tc 4

what was the problem? I am also getting wrong answer on test4.

same with me. I am unable to understand why i am getting was on 4 You can check my code above

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.

treeforces

treeforces! <3

I loved question F1!

Don't know if it was intended, but running Kadane's algo on a tree was very satisfying.

Yep , I did it the same way

nvm, got my mistake

...

for problem F1/F2

Any ideas on E , I was really stuck there for a long time but couldn't think anything

Binary search.

AH YES!!! THE OG div3 contest for newbie/beginner coders who are well versed with 'trees' right??? disappointed.

Besides F, D was the only graph problem...

E: We let t[x]=inf initially, and if we a[x]=1 on the i-th query, we let t[x]=i. Then if the segment [L, R] become beautiful at the i-th query, i will be contained in t[L, R], and there will be at least floor((R-L+1)/2) elements smaller than i. so after we sort t[L, R] increasingly, the (1+floor((R-L+1)/2))-th element will be i. So we can solve the problem by range query for k-th minimum element on t[1, n]. We can answer the queries by Mo's algorithm, in which we need to maintain a subset of [1, q]. Using sqrt decomposition we can add/remove an element in O(1) and query k-th minimum in O(sqrt(q)), so we can solve the problem in O(n*sqrt(m)+m*sqrt(q)).

F1: Assume the minimum sum of weight over all subsegments of path (u, v) is m, and the maximum sum is M. Then if sum(L1, R1)=m, sum(L2, R2)=M, when we change the subsegment (L, R) from (L1, R1) to (L2, R2) by extending or reducing the length by 1 each time, the sum of weight will be increased by -1 or +1 each time, so the sum of weight can be any integer between m and M. Therefore, we only need to find m and M for path (u, v). When u=1, we only need to check for path (1, v). Let p be the parent of p, define M(v)=the maximum sum of weight over all subsegments of path (1, v), suf(v)=the maximum sum of weight over all suffixs of path (1, v), we have suf(v)=weight(v)+max(0, suf(u)), M(v)=max(M(p), suf(v)). Similarly we can calculate the minimum sum m(v).

F2: When u can be any nodes on the tree, we need to look for what if we concatenate 2 paths. Let M=the maximum sum of weight over all subsegments, suf=the maximum sum of weight over all suffixs, pre=the maximum sum of weight over all prefixs, sum=the sum of weight over all nodes on the path. Then if we denote (L, R) be the concatenation of path L and R, we have:

(L, R).sum=L.sum+R.sum

(L, R).M=max(L.M, R.M, L.suf+R.pre)

(L, R).pre=max(L.pre, L.sum+R.pre)

(L, R).suf=max(R.suf, R.sum+L.suf)

So we can merge information of any 2 paths. Therefore, we can solve the problem by binary lifting: Let infos[r][u] be the information of the path from u to the (2^r-1)-th ancestor of u, and parent[r][u] be the (2^r)-th ancestor of u, we can find LCA(u, v) and merge path from u to LCA(u, v) and the reverse of the path from v to the child of LCA(u, v).

In F2, what if u and v are in the same subtree?

We need to lift u to LCA(u, v), and lift v to the child of LCA(u, v).

kth minimum can be solved by wavelet tree instead of Mo's, the complexity is O(m * logq)

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.

Trivially, $$$check()$$$ can be implemented in $$$O(M \log N)$$$. Also, $$$go(i,j)$$$ and $$$rollback(i,j)$$$ can be implemented in $$$O((j-i)\log N)$$$ 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 $$$O(\log Q)$$$ calls to $$$check()$$$. So that part is $$$O(M \log N \log Q)$$$. 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 — $$$T(Q)=T(Q/2)+O(Q \log N)$$$.

This recurrence seems very familiar, doesn't it? We can easily see that this recurrence is equivalent to $$$O(Q \log N)$$$. Now, everything seems so trivial.

Time complexity at last — $$$O(N+Q \log N + M \log N \log Q)$$$.

For D I was using DFS in python and it was having RTE on test 7, so I googled for decision and found the way to use threading, but for unknown reason now my code does not print anything help me please https://codeforces.com/contest/1843/submission/210454284

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

Because on each iteration on DFS you pass the graph to the function. It will be like 10^10 memory which gives MLE

any clue what causes RTE on mine?

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

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?

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 errorswithout 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

Feels more like atcoder ABC__

Atcoderised codeforces

Someone has to say it...

SpoilerAtforces.

why?

could some figure out what did i do wrong in f1

this is my submission : 210459296

for every x(1<=x<=n), i have stored the maximum continues ones and minus ones from 1 to x.

then while querying i just checked

if k==0 ans is always true

else ans is true if maximum length of ones or minus ones >= absolute(k)

If there is a sequence like 1 1 1 1 -1 1 1 1, we can get sum 6.

any approach for E please explain??

Binary search + any data structure for queries sums on segments and updates(Segment tree, Fenwick, Something like Mo heuristics)

you can just use cumulative sum instead of O(log n) query data structure for range sum.

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

Good round! The statements are very clear and I love it!

Tree forces !

I loved the round! I hope you all get your delta increases!

I don't understand why I got a TLE on F1. Here is my submission https://codeforces.com/contest/1843/submission/210465690

Still don't understand why tle... Thanks if you can help me with F1

Ok I know why

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.

210441297 why is this giving mle and why i have to decrease no of ways of node 1 by 1

Watch out your adjacency list, it's N^2.

Thank you very much.

E can be solved using parallel binary search

Can someone help me understand why I am getting TLE https://codeforces.com/contest/1843/submission/210409586?

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.

(╥_╥) Works now thanks

I have a question about problem D. It can be easily solved using recursive DFS, and (at least almost) participants used this solution. But how could you know in advance that it would be satisfactory? I mean, that we know that n <= 2*10^5. And the tree could be very long and thin. In this case a recursive solution would cause stack overflow. So whether almost anyone did a leap of faith that trees would not be so thin?

In most contests of CF you don't need to worry about stack overflow when n<=2e5

Is that's the case for python?

Hi there fellow seal, it seems like we coincidentally share the same avatar

Seals togetha are stronk ;)

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?

You only output one number per query instead of two.

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.

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.

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 :(

https://codeforces.com/blog/entry/57646 So, there are 256 MB for stack (on C++17). By default, you have probably something like 8MB.

210441297 can you tell why mle and why i have to decrease no of ways for 1 by 1 szaranczuk

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

Cool! Thanks a lot!

Div 3 A to D did not test binary search and since its a div3 binary search is usually tested => neuron activation => immediately starts coding binary search solution for E

I also had the same thought initially, then I reverted, and then came back and solved it. The binary search was subtle. If you have not implemented a similar algorithm before, it is definitely tough to inspire. The idea is to check a prefix, and from there it takes linear time to check. Initially, I thought it would take NM time to check. Good to see you got the insight instantly!

I tried to implement BS twice, deleted everything halfway through, tried to build a fenwick tree with an O(q * m * log(n)) time complexity instead, fuck me

Lol. I thought of Binary Search for a minute but never dived into it. SegTree had taken over all my ideas. After the contest, it was so easy to solve with BS+SegTree.

Very nice problemset (though more than expected tree problems) & perfectly balanced contest..Author should get ++.....+INF contribution.

goodjob

Can anyone tell me what is wrong in my python solution for problem D here? It gives Runtime error on 7th testcase. 210431759

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

how about resetting max recursion depth limit?

Ya, I tried it too but it gives the still says STATUS_STACK_OVERFLOW.

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

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

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.

Should I stop using python for competitive coding?

It would be a good idea to transition to C++. It has a larger userbase and better resources to improve in CP.

Not really. Maybe practically all problems <= 2000 can be solved using python, and of couse it is very good for problems like div 2 A-C.

some optimisations that i used to avoid TLE using recursive dfs (java) https://codeforces.com/contest/1843/submission/210402068

For problem B, the problem name is the main hints. (Long Long)

https://www.youtube.com/watch?v=U3xzNgUS0fk&feature=youtu.be My solution for F1

Great round! First time solving E feels great, sadly i got 5 WA's in D.

Is there any penalty for nonsuccesful hack on a div 3?

No

In problem D,I miscalculated subtree nodes of leaf. Life goes on!!

Nice contest! I like problem F

F2 is 2 hard for div3 :(

can i do grey testing?

Not a lot of people mentioning problem C. Albeit simple, very nice question. The observation that broke the problem was that the node u has children 2u and 2u+1 (obvious if you are grounded with binary trees).

F2: Commutative law, I miss you...

That's a good contest and I got + rating. Thank you to EJIC_B_KEDAX and his friends.

Please do some works on servers. This is really annoying that site was going down frequently while doing contest.

3 solve only >~<

how to find out the turtorial of these exercise

The editorial has not been published yet, as the hacking phase is still ongoing. When the editorial is published, you can find it in "Recent Actions" and in this blog too.

https://codeforces.com/blog/entry/117468

This is the best 3rd division of those that I have solved!

But TBH, A-D are just Div4

D is a Leetcode Medium standard, most likely has the difficulty of the 3rd problem in the contest

TBH, only E and F are interesting enough.

https://codeforces.com/contest/1843/submission/210504578

Please see the above solution for problem D and tell me where i am going wrong :( spent so many hours to figure it out. but couldn't able to resolve it :(

Tree is undirected, you should add adj[b].push_back(a) too in your solution. Since its not certain that node with a smaller value will lie above the node with higher value.

And to check if a node is a leaf , you can just check if adj[node].size() == 1 && node != 1

exactly what i did , can you point out what could be wrong

https://codeforces.com/contest/1843/submission/210448804

Try this input:

SpoilerYour code gives 0 as output. The answer should never be 0.

Here the tree would be formed

1 --> 3 --> 2 . I didn't consider higher node can come before :(

My solution to problem A is still in queue and when I submitted it was shown accepted and now its showing in queue.

That's because of system testing. Just wait for a bit. :)

My two questions are still in queue...why is it so?

System testing. It's almost over now.

why my rating has not been improved even after solving three questions?

give it some time, ratings should be updated soon

can anyone tell me how to create tree from given edges in Problem D (apple Tree) ? because edges are not given consistent like higher level to lower level of tree....some edges given higher to lower and some are given lower to higher....that's the only issue I have in my approach..

My approach:

Once I have tree, I will apply BFS on the given x and y separately. BFS on x will return total possibilities(integer value) that are exist for an apple on node x (same for node y). int value return by BFS on node x will be stored in variable ans1 and int value return by BFS on node y will be stored in variable ans2.

and finally we will print ans1 × ans2 for each assumption...

so, can anyone tell me how to store tree in C++?

I think the problem is way more natural with DFS instead of BFS. Also your approach will TLE, you are not supposed to run whatever traversal for each query here. You need to preprocess the input once and store the number of leaves reachable from each node. This can be achieved with a single traversal.

To be sure the adjacency list is correct you must put the second node in the neighbors of the first and also the first node in the neighibors of the second.

While doing dfs just be sure you are not visiting the parent again. You can do this both with a visited array or by keeping track of the father of the current node, in this way if the next node is not the father you keep going with the dfs, otherwise you dont.

While doing DFS you can compute on fly the number of leaves reachable from any root and store into an array, let say array "leaves". Ans for each query is leaves[i]*leaves[j]

It was last rated div3 for me :)

I too had thought this brother :)

gl next bro <3

Why hasn't the tutorial out? Crying ಥ_ಥ

https://codeforces.com/blog/entry/117468

Thanks! love you

Why did my rating fell from 852 -> 796??? It shows accepted. I am really unable to understand this platform.

Because you solve only 1 problem?

And how is that a reason for rank to decrease ? In previous rounds too I have solved a single problem and got increase in ranking.

Why do you think you rating must always go up? There are like more then 15k ppl solved A,B,C. So yours rating drops.

I saw the formula but it didn't go into my head. In one of the contests I solved 0 problems but had a leaderboard rank of 6275, which is the best amongst all(if you consider my other leaderboard ranks) but my rating decreased in that round.

The name of the problem B may indicate that you should use long long.

EJIC_B_KEDAX I'm surprised this passed pretests :/ :/ went from 200 to 1522 :/ https://codeforces.com/contest/1843/submission/210366483

Hi, I received a penalty for q4 in this contest. However my approach was directly derived from a prior reference that i had studied, finding all the leaf nodes in an n-ary tree using dfs. https://www.geeksforgeeks.org/print-all-leaf-nodes-of-an-n-ary-tree-using-dfs/ is the link that can be checked for reference, Kindly look into the problem and perhaps give a more appropriate solution for the same? Thanks, yxjat

even I received a similar message.I received the message of significant collision of submission with others today for 1843D. The problem was very easy and standard . the solution had a simple use of DFS which is a standard algorithm .I had format of standard answer with me while practicing and I used that. The format ( written much before the contest) was from YouTube tutorials and other online resources . Resources :1) https://www.geeksforgeeks.org/print-leaf-nodes-left-right-binary-tree/ 3)https://www.geeksforgeeks.org/number-of-leaf-nodes-in-the-subtree-of-every-node-of-an-n-ary-tree/

Im facing the same penalty , i had reused previously written code I think it was in a cses problem set not sure though Please look into this test setters.

I am not able to understand why I received mail from codeforces (Attention!

Your solution 210439915 for the problem 1843D significantly coincides with solutions .....) I think because I used online gdb(https://www.onlinegdb.com/)compiler, they found plagiarism in my code,You can cheak my code too. Please I request you to resolve my issue because I didn't copy code from anyone.Please anyone helpe regarding this issue.

Author I have been flagged for having similar solutions but this is a standard problem and I have reused previously written code . Please look into this :(

Hi, I got a notification of plagiarism in the last contest of Codeforces Round 881 div3. I have gone through both the submissions and both the codes seem to be different to me. It must be a coincidence that plagiarism was detected because if a question has a particular type of approach there is a good enough probability that it might match someone in a pool of about 30k participants, I think that same thing happened here. This was a normal dfs + dynamic programming question and I think the other person has done the question in the same way. There is no way I have cheated here. Please review it once.

Hello, even I got a notification of plagiarism for 1843B. I have gone through others' submissions and my code is way different than the others. Could have been a coincidence that I was marked for plagiarism because in a pool of about 30k participants its pretty possible to get similar codes because of the same correct approach. This was a simple and normal arrays question and I think the others have done the question in the same way. I did it myself and it is the truth so you cant just conclude I have cheated here. Kindly, review it once. Thanks

I am writing to express my concern regarding the solution matching issue I encountered while solving Problem D on Codeforces. I solved the problem using the standard DFS (Depth-First Search) approach, I am surprised to see my code matching with a large number of other participants.

I want to clarify that my implementation is based on a well-established algorithm commonly used for efficient problem-solving in graph and tree traversal. I assure you that there has been no plagiarism or intentional copying involved. I developed and implemented the solution independently, relying solely on my understanding of the problem statement and established programming techniques.

I kindly request your support in ensuring a fair evaluation of my solution. I ask for your consideration in not penalizing participants, including myself, who utilize standard algorithms like DFS when there is code similarity due to the widespread usage of such approaches.

`~~~~~`

`Your code here...`

`~~~~~`