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:
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.
OMG!!!
Pakistani round
*Graph/TreeBastic contest. It was fun to give this contest.
As a tester,
I tasted some applesI 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
As a Tester,
Hope you will enjoy the nice problem-set as i did.
As a tester, you must participate! Problems are interesting!
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 blue tester, I may say that I am a blue tester.
hope the problems are well balanced
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!
As a participant, I hope to become blue one day.
update:I have solved A~F1, so I can become a blue name.
Can I become expert today?
It's a good one, nothing like 880 :)
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 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.
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
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:
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:
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
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
anddfs_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.
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.net/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?
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.
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.net/contest/1843/submission/210448804
The result shows "Accepted"
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.net/contest/1843/submission/210454284
Because on each iteration on DFS you pass the graph to the function. It will be like 10^10 memory which gives MLE
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.net/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 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
Feels more like atcoder ABC__
Atcoderised codeforces
Someone has to say it...
Atforces.
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.net/contest/1843/submission/210465690
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.
E can be solved using parallel binary search
Can someone help me understand why I am getting TLE https://codeforces.net/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.
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.
https://codeforces.net/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.
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?
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.net/contest/1843/submission/210402068
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 :(
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.
how to find out the turtorial of these exercise
https://codeforces.net/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.net/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.net/contest/1843/submission/210448804
Try this input:
Your code gives 0 as output. The answer should never be 0.
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?
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.net/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.
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.net/contest/1843/submission/210366483
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.
Its one year since the contest started.
Happy 1st anniversary!