Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By ZeyadKhattab, history, 11 days ago, ,

A Segment Tree query works by breaking down a segment that is queried into several pre-computed segment tree segments and merge them together to find the answer for the queried segment.

What is a tight upper bound for the number of segment tree segments that are merged together?

I believe it's $2*log(n)$ because the following scenario is possible:

4 nodes are visited in the majority of the segment tree levels, 2 of them make recursive calls, (visiting 4 more in the next level), and 2 segments are returned.

Is this analysis correct?

Is there a tighter upper bound?

• +36

By ZeyadKhattab, history, 5 months ago, ,

I would appreciate it if someone explains the solution for 102055K - Mr. Panda and Kakin

I tried reading AC solutions, but I could not understand them.

• +4

By ZeyadKhattab, history, 5 months ago, ,

Can anyone explain the solution for this problem 102014F - Directional Resemblance ?

The problem basically says:

We are given N vectors in 3D and we want to find 2 vectors such that the angle between them is minimum.

• +12

By ZeyadKhattab, history, 13 months ago, ,

It is commonly known that we can use Fenwick Tree to perform 2 tasks :

1) calculate the prefix sum (a[1]+a[2]+...+a[idx-1]+a[idx]) up to some index

2) increment a certain index by a certain value

but, my question is how can we modify the fenwick tree implementation so that instead of calculating prefix sums, we are calculating suffix sums so the sum we are now querying is (a[idx]+a[idx+1]+...+a[n-1]+a[n]), so I tried to change the implementation by basically swapping the indices that are accessed in the update and the query functions and I tried submitting in different problems and the submissions are accepted and I wanted to know if someone had a proof of why does it work ?

• +1

By ZeyadKhattab, history, 14 months ago, ,

How can we solve the following problem efficiently (I am mainly looking for a Segment Tree solution) ? Given an array of integers A of size N , and Q queries of the form L,R,X we need to find the minimum index i such that L<=i<=R and A[i]>=X 1<=L<=R<=N and |X|<=10^9 1<=N<=10^5 1<=Q<=10^5 |A[i]|<=10^9 for 1<=i<=N

• +7

By ZeyadKhattab, history, 17 months ago, ,

Can someone help me solve this problem ? 101755D - Transfer Window My approach was to build a graph with the players as the nodes and there is an edge between player a and player b if I can exchange a with b then I created 2 nodes; Source and Sink. Then I added edges from from the Source to players I have and edges from players I want to the Sink, and applied max flow on this graph. All edges have capacity one. But then, I cannot construct the solution. My code (which gets WA at test 8) https://ideone.com/U4EjyO