I have created my first youtube video. In this video I have discussed 1220E - Туризм. The video is made in Bangla language. Those who speak in Bangla or understand Bangla are invited to watch the video.

Video link: https://youtu.be/RntOXigIsSk

I have plan to make more and more videos on different good problems from online judges; different interview problems; various data structures, algorithm and problem solving techniques that I have learnt and then related a good number of problem discussion on each of them. I also may discuss a whose contest's problems after the contest ends or from a past contest(the problems that I have solved).

I believe that the channel may be helpful for some people who understand Bangla.

So, I would also like to invite you to subscribe my channel to get the next videos — if you understand Bangla.

For any codeforces regular round other than Div.3 and Educational round, on standing page, after a single click or tap on any score of any user for any problem from mobile browser(I am using chrome on android phone), the submission history for that problem of that user is popped up. Then by clicking on submission id the source code is shown.

But on the standing page of Div.3 or Educational rounds, nothing is popped up after clicking on the score(here + icon and submission time actually) from a mobile browser.

So, I am drawing kind attention of MikeMirzayanov and codeforces authority on this issue.

We hope we can see submissions on Div.3 and Educational rounds standing page similarly like other regular rounds.

Problem:

1092F - Tree with Maximum Cost

Problem description:

Given a tree with n vertices, where each vertex has a number a_i written on it. Distance between two vertices is defined as the number of edges on the path between them. You have to choose a vertex v such that d₁ × a₁ + d₂ × a₂ + d₃ × a₃ + ... ... + d_n × a_n is maximized, where d_i denotes the distance between vertex i and vertex v. You have to print this maximum value.

Solution:

Lets tot be the sum of all a_i for all vertices i and sum_i be the sum of all a_j of the vertices j in the subtree of vertex i.

Now, lets subtot_u stores the sum of all d_i × a_i for all vertices i in the subtree of vertex u, where d_i is the distance of vertex i from the vertex u. But how to calculate the array subtot?

Lets root the tree at vertex 1. If u is a leaf vertex, then it is obvious that subtot[u] = 0 × a[u] = 0, since distance from u tot u is 0.

Now what about the non leaf nodes?

For a vertex v, subtot[v] stores all a[i] × d[i] for all vertex i in the subtree of v. Since for its parent u, it is 1 distance upper than it's child v, we need to add sum[v] with subtot[v] to get subtot[u], for all child v of u.

So, for any non leaf vertex u, subtot[u] = subtot[v] + sum[v], for all direct child v of vertex u. Addition of sum[v] is for 1 distance away from child v to parent u.

So, run a dfs to calculate the array sum[] and subtot[].

vector<int> g[maxn];
ll subtot[maxn], sum[maxn];
void dfs(int u, int p){
    subtot[u] = 0LL;
    sum[u] = a[u];
    for(int v:g[u]) if(v!=p){
        dfs(v,u);
        sum[u]+=sum[v];
        subtot[u] += subtot[v] + sum[v];
    }
}

Ok, now if we choose vertex u as the fixed vertex, how to calculate the answer for this vertex?

Notice that, the calculation for any vertex which is in the subtree of vertex u will not change. What will be changed? Other vertices which is not in the subtree of vertex u. Lets the sum of all subtot[] values of other vertices which are not in the subtree of vertex u be up. Every time you go one step down, distance from vertex u to all other vertices which are not in the subtree of vertex u will increase by 1. So, wee need to increase up by tot - sum[u](we are ignoring the sum[u], since distance to other nodes is increased, which is, sum of all a[i], for all vertex i which are not in the subtree of vertex u.)

Then the current answer for vertex u is cur = subtot[u] + up + tot - sum[u]. Here, subtot[u] is for for vertices in the subtree of u, up for vertices which are not in the subtree, tot-sum[u] is for increasing ditance by 1 for non subtree vertices.

When you will go to vertex v from vertex u, then update up by up = cur - subtot[v] - sum[v]. Here since we are going down, that's why we subtract subtot[v] and sum[v], instead of adding.

Thus, you have to run another dfs to try to choose each vertex as the fixed vertex and keep track of the maximum value cur ans our required answer in ans.

ll ans = 0LL;
void dfs2(int u, int p, ll up){
    ll cur = subtot[u] + up + tot-sum[u];
    ans = max(ans, cur);
    for(int v:g[u]) if(v!=p){
        dfs2(v, u, cur - subtot[v] - sum[v]);
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200002;
int n;
ll a[maxn], tot, ans;
vector<int> g[maxn];
ll subtot[maxn], sum[maxn];
void dfs(int u, int p){
    subtot[u] = 0LL;
    sum[u] = a[u];
    for(int v:g[u]) if(v!=p){
        dfs(v,u);
        sum[u]+=sum[v];
        subtot[u] += subtot[v] + sum[v];
    }
}
void dfs2(int u, int p, ll up){
    ll cur = subtot[u] + up + tot-sum[u];
    ans = max(ans, cur);
    for(int v:g[u]) if(v!=p){
        dfs2(v, u, cur - subtot[v] - sum[v]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        tot+=a[i];
    }
    for(int i=1;i<n;i++){
        int u,v; 
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    dfs2(1,0,0LL);
    cout << ans;
    return 0;
}

Here is my submission link: 47272565

If you have any further query regarding any part of the solution, feel free to ask in the comment.

December 2017 long challenge just finished. I used square root decomposition technique to solve the problem CHEFEXQ.

Here is the problem link

I just wrote the tutorial explaining how I have solved this problem. Hope it will be helpful to someone.

Here the editorial link

You are welcome to comment below the post or here, if you find anything wrong or you have any further suggestion.

The following problem is from the preliminary contest of ACM-ICPC Dhaka Site 2016.

[Time Limit: 1s and Memory Limit: 1200MB]

Problem Statement:

Given a tree with N( <  = 10⁵) nodes, where value of each node can be either 0 or 1. How many number ways to choose two node where value of these two nodes is 0 and there are exactly two nodes with value equal to 1 on the path from a chosen node to another.

Sample Input:

5 // value of N

0 1 1 0 0 // value of each node, then the below are the edges

1 2

2 3

3 4

4 5

Output:

4

Explanation of Sample Test Case:

You can choose two nodes as (1, 4), (1, 5), (4, 1), (5, 1).

My question is:

1. How to solve this problem using centroid decomposition?
2. How to solve this problem using DP?

Problem:

Given an array of n integers and q queries of the form: Q(L, R, x). For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".

There is no update operation.

Constraints:

• 1 ≤ n ≤ 1900000
• 1 ≤ q ≤ 10⁵

I know two ways:

1. Using SQRT decompostion: Partition the array in SQRT(n) blocks and Sort each block. Then for each query binary search(lower bound or upper bound) x in each block. If I use Square Root Decomposition, complexity will be O(q * sqrt(n) * logn), which is not so good for this constraints, I think.

2. Using segment tree: Store the sorted list of numbers in each node in the segment tree. Then for each query, binary search x at each required node.

Can you please suggest any better solution for this problem ?

Thanks in advance.

In the qualification round of Codechef Snackdown 2017, I was able to solve all the problems and I had a great fun to solve the problem SNAKEEAT.

I was so much excited that I had given a post to express my feeling after solving this problem.

After that some people asked me on codeforces or facebook, how I had solved the problem. So, I had decided to write a post regarding my solution idea of this problem.

Before staring the post, I want to say you that I am not so great programmer, so I may make mistake in my post. And, this is my first tutorial post on codeforces, so forgive me if you find anything wrong. Also, English is not my native language, so I may make some grammatical mistake in my post. So, I beg your forgiveness in advance.

Abridged problem description:

Given the length of n snakes, a₀, a₁, a₂, .........a_n - 1. A snake i can eat another snake j, if a_j ≤ a_i and after eating a snake, it's length is increased by 1.

Given q queries. Each query contains an integer x, you have to tell what is the maximum number of snakes you can get which are of length at least x.

Soultion:

Prerequisites:

1. binary search
2. STL lower_bound
3. Cumulative sum or prefix sum or range sum

In my post, I won't discuss about these. I assume that you already know these, if not please learn them first.

Let store the lengths in an array and sort the array in increasing order. Since now the array is sorted we can use binary search or lower bound to search any value in this array.

Before processing the queries, let first observe something which will be helpful in processing the queries.

Observe that the number of snakes whose length  ≥ x can be added to the answer immediately. For any the other snake of length a_i, it needs to eat (x - a_i) snakes to make it's length x.

So, how many snakes are there whose length is  ≥ x ? We can use lower bound to find this. Let this index be k

But what should we do to find the rest ?

We might iterate from the index k - 1 and check whether we can increase it's length to x or not. From index k - 1, for each length a_i it need to eat (x - a_i) snakes to make it's length x. Of course snakes should be eaten from the left side(staring from index 0). We stop when there is not enough snakes on the left side.

But this process will get TLE. Because complexity of a single such process can be O(q * (n + logn)) in worst case.

So what to do ?

Their may be lot of ideas to optimize it. Here I am sharing my solution idea.

I would like to discuss the solution with an example. Let n=13 and the given lengths(after sorting) are-

Observe that for each index i, there are i snakes on it's left side. Let we are querying for x = 15. If we use lower_bound for 15, we get the index k = 10. So there are n - k = 13 - 10 = 3 snakes whose length is at least x, so this value can be added to our answer immediately. So, our current answer is, ans = 3.

Now, we have to find how many snakes can be made of size 15 by eating other snakes.

We have to find how many snakes from index k - 1 = 9, we can make of length 15 by eating other snakes. Index = 9, length = 14, need to eat = 15-14 = 1. total need till now = 1 (possible, 9 snakes left) Index = 8, length = 13, need to eat = 15-13 = 2. total need till now = 3 (possible, 8 snakes left) Index = 7, length = 12, need to eat = 15-12 = 3. total need till now = 6 (possible, 7 snakes left) Index = 6, length = 8, need to eat = 15-8 = 7. total need till now = 13, it is not possible, because there are 6 snakes on the left side of index 6. So, 3 snakes can make their length 15. So, final ans = 3 + 3 = 6.

We stopped at that index where sum of needed snakes to eat is less than the amount of snakes on the left side of that index. For each query we are finding this index by iterating linearly. So, in worst case it takes O(n) time. So, for each query it takes O(logn + n) time. Total query processing time O(q * (logn + n)). Sorting takes O(nlogn) time. So, total time complexity for each test case is O(nlogn + q * (logn + n)). Since 1 ≤ n, q ≤ 10⁵, it must get TLE.

So, the question is: how can we improve it anyway?

Observe that from the index k - 1, up to index i, sum of needed snakes is calculated as (x - a_k - 1) + (x - a_k - 2) + (x - a_k - 3) + ......(x - a_i). If we could know, somehow, for any index i, sum needed snakes to make all the snakes from index k - 1 to i of length x in O(1), then we could use binary search(or lower_bound) the index up to which we can make their length equals to x.

How can we do it ? It may seems difficult, since for each query the value of x is changed. But we still can do it by following the below technique.

We can store the cumulative sum of the difference between each length and and length a_n - 1, i.e. the largest length.

According to our example, we will store the sum of difference between each length and a_n - 1 = 20. The cumulative sum array will be:

We can now calculate the sum from any index i to any index j (i ≤ j), in O(1), by sum[j] — sum[i-1].

But how to handle, if we query for x = 15, or any other value of x?

We calculated the cumulative sum with respect to 20. Difference, d between a_n - 1 = 20 and x = 15 is 5. So, for each index we added extra d = 5. From i to j (i ≤ j) there are total j - i + 1 elements. So for this range we added extra sum = 5 * (j - i + 1) So, for any query x, the difference d = a_n - 1 - x So, the needed sum of snakes, with respect to x, from any index i to any index j (i ≤ j) is (sum[j] - sum[i - 1]) - d * (i - j + 1).

That's great !! We can now calculate the needed range sum from index k - 1 up to any index i in O(1) by sum[k-1] — sum[i-1].

Now, we have to use binary search(or lower_bound) to find the index up to which the needed sum is greater than or equal to the number of elements at it's left side. If that index is i and our first lower_bound index is k, then our answer to the query will be n - k (from lower_bound)  + k - i (from the 2nd binary search (or lower_bound).

That's all !!

Now the complexity of each query is O(logn + logn) So, total complexity for each test case is O(nlogn + q * (logn + logn)) = O(nlogn + 2 * q * logn)

Finally, here is the code(in c++):

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int MX = 100005;
int a[MX], n;
ll sum[MX];

int cal(int x, int last)
{
    if(last==0)
        return 0;
    int diff = a[n-1] - x;
    int l = 0, r = last;
    int ans = 0;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(mid==0)
        {
            l = mid+1;
            continue;
        }
        
        ll need = (sum[last] - sum[mid-1]) - 1LL*diff*(last - mid + 1);
        if(mid>=need)
        {
            ans = last-mid+1;
            r = mid-1;
        }
        else l = mid+1;
    }
    return ans;
}
int main()
{
    //ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t, q, x;
    cin>>t;
    while(t--)
    {
        cin>>n>>q;
        for(int i = 0; i< n; i++)
        {
            cin>>a[i];
        }
        sort(a, a+n);
        sum[0] = 0LL;
        for(int i = 1; i< n; i++)
            sum[i] = 1LL*sum[i-1] + 1LL*(a[n-1] - a[i]);
        
        while(q--)
        {
            cin>>x;
            int cnt = 0;
            int idx = lower_bound(a, a+n, x) - a;
            cnt=(n-idx);
            cnt+=cal(x, idx-1);
            cout << cnt << "\n";
        }
    }
    return 0;
}

You also can read this post on my blog

If you find anything wrong in my post, please let me know. If you face any difficulty to understand any part of my post, feel free to ask me in the comment below. Also, if you have another idea to solve this problem, you can share that in the comment.

Thanks to all.

It is one of the most happiest and excited moment in my coding life !!

Solved all the problems of Codechef SnackDown 2017 Contest (Qualification Round) !!

Now our team rank is 1 (combined).

I am unable to express my excitement and how much fun I have got by solving the last problem !!

Today I had an mid term exam. But till yesterday, we solved 2 problems out of 4, still there was two unsolved problems. Azad Abul Kalam sir told us to solve the rest. Sakib vai also inspired me.

Then I try to solve the third one. In my first attempt I solved that problem.

Since I had a mid term exam today, I thought to skip the last one. So I just read that problem and came out from the contest.

But from the time of reading the last problem, only this thinking was running in my head, "How to solve this?". I just couldn't give attention to anything else. Whatever I was trying to do, just this thinking was making me mad. I couldn't do a single math for today's exam. In the mean time the exam was cancelled !

Even when I was sleeping, I was trying to solve the problem in my dream !!

After wake up in the morning, I was just singing a song of Nachiketa Chokraborty. Suddenly an idea came to my mind !! I was attempting to brush my teeth. I said to my dearest one that I got an idea. She said me to solve the problem first then to brush teeth.

I sit in front of my laptop to solve the problem, then implement my idea and submit my code. But got 'wrong answer' verdict. Then started to debug my code and found two big mistakes in my code. Then I correct my code and submit it.

Then the moment came !! Yeeeesssss, this time my code is ACCEPTED !!!

After solving this problem, I just can't express my feelings on 'how much fun I have got' ! I just shouted in my highest loud and jumped over my bed !!!

The most important part was that when I first read the problem, I thought that it is out of my level and can't solve it. But finally I solved the problem ! I just made it true that if anyone tries his best, doesn't give up, works with full confidence, then he can do it.

In many geometry problems, setting a value for EPSILON leads WA, while setting another value for EPSILON leads the solution to get ACCEPTED. It happens that for which value of EPSILON I got ACCEPTED on a problem, with the same value of EPSILON, I got WA on another problem.

For example, on problem 140A - New Year Table, I used 1e-6 as the value of EPSILON and got WA then changing the value of EPSILON to 1e-10 got ACCEPTED.

So, I am very confused to set the value of EPSILON.

Can you please help me in such issue?

I know that Z algorithm can be used for string matching. Which is: If we want to find P is S, then we calculate value of Z[] array using the string P + $(or any unused sign) + S. Then for any i, if Z[i] == |P|, then we state that P is found in S.

Now, I want to know other applications of Z algorithm. Please tell me what other kinds of problems we can solve using Z algorithm and how ?

Thanks in advance.

problem link: 61E - Противник слаб

Reading the editorial and seeing other's code I have come to know that the problem is solvable by using binary indexed tree — BIT (aka fenwick tree). But I didn't understand how binary indexed tree is applicable for this problem.

Though I know BIT, I don't understand how to solve this problem using BIT. In contest hour, how should I determine that I should use BIT for this problem?

I have also read some code of others, but I didn't understand any full code. Specially, what is the use of lower_bound here? What it is doing?

Can anybody help me to solve and understand fully the problem, tricks behind this problem, solution — how BIT is working here and how did you understand that this is solvable by BIT ?

Thanks in advance.

I noticed that almost all of the programming blog shared O(n*(log n)^2) implementation for suffix array construction.

I saw O(n * log n) implementation in the book "Competitive Programming 3" — by Steven & Felix Halim. But it seems hard to understand and needs more time to code, since the code is longer compared to the O(n * log^2 n) implementation.

Besides, O(n*(log n)^2) implementation is easy to code and easy to understand.

So, my question is: Is it good enough to learn only n(log n)^2 suffix array implementation for solving problems related to suffix array in any contests? Have you seen any problem where O(n*(log n)^2) fails but O(n*(log n)) passes?

If you think that one must know O(n*(log n)) implementation, can you please share any easy to understand and comparably short code for O(n*(log n)) implementation?

Another question: any problem which is solvable by suffix tree, can be solved suffix array? If so, can we skip suffix tree and always use suffix array?

Thanks in advance.

Problem statement: Problem link "One day Jibon started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1st string and generated subsequent strings from it by replacing all the b's with ab and all the a's with b. For example, if he ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the N'th string has length X and M'th string has length Y. He wondered what will be length of the K'th string."

I observed that the i'th string length, L[i] = L[i-1] + L[i-2]. So, summery is, Given L[n] = x, and L[m] = y, find L[k] = ?, where L[i] = L[i-1] + L[i-2]. If it is impossible, then print "Impossible".

Since, n and m is not always consecutive, how to find L[k]?

Topcoder Single Round Match 699 will be held on 26th September 15:00 PM UTC

Lets discuss the problems after the contest finished.

UPDATE: Editorial of the SRM

Codeforces provides a nice facility of seeing friend's standing during contest.

There is also another option in the rating page that is filtering users according to "country", "Organization" and "City"

But in the standing page it can be filtered only by "Friends". If the standing page and rating changes page of any contest would have those option to filter the 'standing and rating change' according to "Country", "Organization" and "City", one could easily see and compare the performance of all contestants from his organization or city or country in that contest.

I request to add this feature in the standing page.

Thanks in advance,