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

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,

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

hope to became pupil

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

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.

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.

Long Long anyone ?

friendly contest (●'◡'●)

friendly contest！！！！！！

Почему неправильный ответ 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?

for E should we use MKTHNUM — K-th Number question from spoj.

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