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

wow !! Vladosiya is back :)

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.

As a tester,

I tasted some apples I tested some cool problems.

first unrate div3,GL&&HF for everyone:)

and one more thing,how can i become a tester

As a Tester,

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.

Div 2?????!

As a tester, blablabla...

ahmet23 orz!..

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

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

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.

Can I become expert today?

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

contest of trees

E and F are really good problems.

Long Long anyone ?

Почему неправильный ответ 2 в задаче F1 считается как неверная посылка и влияет на штраф, если второй тест — семпл?

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)

diction[num]= ans
return ans

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

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)

`

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.

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?

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

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

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

Can F2 be solved with persistent segment tree?

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.

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://mirror.codeforces.com/contest/1843/submission/210448804

treeforces

I loved question F1!

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

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

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

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

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://mirror.codeforces.com/contest/1843/submission/210454284

Feels more like atcoder ABC__

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)

any approach for E please explain??

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://mirror.codeforces.com/contest/1843/submission/210465690

E can be solved using parallel binary search

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

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?