So one day, after getting so ashamed of reading other's solutions and copying them, instead of trying to find out what's wrong with my code, I decided it's time. There is a video by Errichto related to this topic that I balatantly copied, and suggest others to do too.

So I was trying to solve this problem : 1418D, and after 2 days of thinking, I really felt I knew what to do, and implemented it. It failed on the 3rd test case, as can be seen in this submission.

So I decided to write a basic random test case generator for this, and a brute force version of the program.

Generator:

This is a c++ program, written to generate test cases to be feeded into our solutions. In this problem we need a $$$n$$$ : number of elements in the array initially, $$$q$$$ : number of queries on this array, the $$$n$$$ sized array, and the description of each $$$q$$$ queries. The queries also are restricted in a way that if an operation of type "0" is to be done, then an already present element in the array is to be removed, and if it's of the type "1", then an element not in the array is added to it.

So to generate $$$n$$$ and $$$q$$$ I used (rand()%10)+1 (different in code, but it's okay), to specifically generate arrays of length 1 to 10.

For $$$q$$$ too, I used the same thing. You can choose any number, but choosing small values makes sure that in the case your solution and the brute force solution don't give the same answer, then you can debug easily.

Now for the array, just generate any numbers from 0 to 100. But we can't have repeated numbers here, so I used this while loop :

while((int)p.size()<n)
    {
        int g = rand()%100 ;
        if(st.count(g)==0) p.pb(g),st.insert(g) ;
    }

Where st is a set of integers.

Now we have to generate the queries. You can create a variable operation = rand()%2, and based on it's value, decide which operation is to be performed. Type "0" is easy, as you can simply calculate the index of the element to be removed, by index = rand()%((int)p.size()) ;. Also erase them from our set and the array.

In the type "1", we'll need to generate numbers, until we reach a number which isn't in the array already. Same methodology.

Note : If you don't want your generator to generate the same test case every time (which is obvious), srand(time(NULL)) ; is to be used. Setting random seed, initiated the random function differently, because of which it generates different series of numbers. Here's the full code of the generator :

#include<bits/stdc++.h>
using namespace std ;
#define f(i,s,n) for(int i=s;i<(int)n;i++) 
#define pb push_back 
#define fio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cout<<setprecision(10) ;
int main()
{
    fio ;
    /* ======================Start of code ================ */
    srand(time(NULL)) ;
    int n = (rand()%10)+1 ;
    int q = (rand()%11)+1 ;
    cout<<n<<" "<<q<<"\n" ;
    vi p;
    set<int> st ;
    while((int)p.size()<n)
    {
        int g = rand()%100 ;
        if(st.count(g)==0) p.pb(g),st.insert(g) ;
    }
    f(i,0,n) cout<<p[i]<<" ";
    cout<<"\n" ;
    f(i,0,q)
    {
        int operation = rand()%2 ;
        if(operation==0)//remove
        {
            int index = rand()%((int)p.size()) ;
            cout<<operation<<" "<<p[index]<<"\n" ;
            st.erase(p[index]) ;
            p.erase(p.begin()+index);
        }
        else 
        {
            int gen = rand()%100 ;
            while(st.count(gen)==1) gen = rand()%100 ;
            cout<<operation<<" "<<gen<<"\n" ;
            st.insert(gen) ;
            p.insert(lower_bound(all(p),gen),gen) ;
        }
    }
    /* ======================End of code ================== */
}

Now, the Brute Force isn't actually useful in this context. It's, as the name suggests, is a brute force solution of the same problem. So, just to show you, I made a submission where it TLE'd here.

Now the in the case of windows, you can create a .cmd file, to create a program that : generates a test case, saves in a text file, uses the same text file to run on the normal solution and the brute forces solution, captures their output in two different text files, and compares these text files.

Here's the code for this:

GeneratorTrashProblem.exe > generatorTrashProblem.txt 
(TrashProblemBrute.exe < generatorTrashProblem.txt) > BruteResult.txt
(TrashProblem.exe < generatorTrashProblem.txt) > NormalResult.txt
fc BruteResult.txt NormalResult.txt

Remember, that it can be improved by adding a loop, and testing until the outputs aren't same. I am lazy, so please help me by telling me how to do those.

By using this, I was able to generate a test case which caused issue in my solution. So I was able to fix that and get a AC.

This was the minor bug that was causing the issue:

I've recently solved this problem and have seen many people asking for an explanation. Well, here is what I did, I hope it helps someone.

The problem can be found here.

Consider the first example.

4
1 2
1 3
2 4

16

That is, we have this:

(I just realized I can't upload pics from local PC. Okay ._.)

Let's assume 1 to be the root node of this tree. So, what we want are different permutations of this. Now pick up 2. What can we do just in this sub tree? (That is, 2 and 4).

We can either have 4 on the left of 2, or in the right of 2. Nothing else is doable here.

What about 3? Well, it doesn't have any children so we can't do much here. So, nothing.

Now let's look at 1. What things are possible?

A lot of things eventually. If we go in a similar way as we did with 2 (that is, all children are taken to one side)

a. You can have 2 and 3 on the left of 1

b. 2 on the left 1 in the middle and 3 on the right

c. 2 and 3 on the right of 1

And 3 more, if we change the ordering of 2 and 3 for each a,b and c.

So basically 6 options.

This looks like we're just creating all the arrangements for the children of a node. Isn't that simply equal to $$$children!$$$ (factorial, not what a pedo would have screamed to his genie).

Well then the answer for 2 should have been $$$1!=1$$$ and not 2. So, we also have to count empty spaces for nodes.

So, we get an idea of $$$(children+1)!$$$. Remember we're not looking at the whole thing until now, node and it's children.

So for 1, we have 2 children, thus $$$(2+1)! = 3! = 6$$$ ways. Well yes, but actually no.

The point where we're taking all children to one side, is wrong actually.

Looking at some bad sketches:

Aren't they both representing the same structure? Yes. So, we remove ways 1 and 3 (and their 2 copies). So we get only two options for node 1:

1. 2 on the left of 1, and 3 on the right
2. 3 on the left of 1, and 3 on the right

So actually we're using $$$children!$$$ here. So, was our $$$(children + 1)!$$$ wrong? Well actually no.

An empty space matters when you have a parent. It gives some structural difference. But it doesn't matter if you don't have a parent. So for the root, we have $$$(children)!$$$, and for others we have $$$(children+1)!$$$.

So what now?

Since these options are mutually independent, they have to be multiplied with each other. Thus all you have to do is multiply all these and you've the answer.

One more thing to do. Now you've got the total number of different structures. But do notice that each structure is present $$$n$$$ times. The ordering is the same, but they've just rotated it. So, you have to multiply your answer by $$$n$$$ too in the end.

Do not forget to do the MOD though.

Here is my submission. I hope this helps.

Hello all,

I've been trying to solve this problem, and even after reading the editorial, I'm unable to get an AC.

My submission: https://mirror.codeforces.com/contest/505/submission/85055307

My approach:

So, if anyone has solved the problem, they know that there are only 491 total types of jumps possible, at any point. That is d-245,d-244,d-243,...,d,d+1,...,d+245. So I've created dp[i][j], where i is the current point, and j is the last modified jump size (mjs), where dp[i][j] would give the maximum number of gems collected, with being at point i with the last jump of size j.

Since d is in the range 0 to 30000, that'd mean that d-245,...,d+245, will be in the same order. So to deal with that, $$$mjs = jumsize-d+offset$$$. Here, $$$offset=250$$$.

Similarly I've create a boolean matrix visited[i][j], with the same system in place.

Now I go from 0 to MAXN (MAXN = 3e4+5). Initialising dp[d][offset] = gems[d], and visited[d][offset] = true.

Now for each point, we go forward.

So, if we reached point i with a jump mjs, then we can take jumps of mjs-1, mjs and mjs+1. So we simply update these values if possible.

Great! That's pretty much it. So, now my submission is failing on Test Case 4, which it misses by 1. I checked all the smaller test cases, which were shown completely, and my code worked fine on them.

So, I'd like to ask two things here: 1. How do you deal with such a situation? If you don't have any tests to test your code, and you know that there is some bug. 2. What's the catch here? I couldn't find anything obvious. I tried to play around the code a bit, but that didn't do anything.

Any kind of advice is highly appreciated. Please help me understand how you people deal with such situations. If you also find the bug, then that's a plus.

Hello all,

I am doing small 2 hour practise contests for a time now. I am thinking of switching to week long practise contests, with 6 DP 1900 — rated problems (because these are the ones I need to practise now). Only 6 problems because I don't practise all day long, and am free only in the evening.

Therefore, if you're interested, do join our discord channel: https://discord.gg/c6ZRsj

Here I am planning on keeping invite links to contests, discussion on problems after contests, and a separate blog for all the problems. So that we can be sure we understood the problems and can give alternative approaches to other people solving the same problems.

So we start the virtual contest on Sunday, and discuss solutions on the next Sunday. Others' submissions will be visible too.

Do let me know if something similar is already been going on. I'd be glad to join that.

I am trying to solve this question for two days now.

Gist of the problem:

2D plane is given. Only the first quadrant is to be used. Three type of queries:

1. add x y: Add a point (x,y) to the coordinate system
2. remove x y: Remove an already existing point (x,y) from the coordinate system.
3. find x y: Find the left-most, bottom-most strictly above and on the right of (x,y).

Constraints: $$$1 \leq x,y \leq 1e9$$$ $$$queries \leq 2e5$$$

Approach to solution:

Firstly we need to map the $$$x$$$ co-ordinates to the 2e5 range, so that we can use a segment tree on them. I have done this using the code:

int n;cin>>n ;
f(i,0,n)
{
    cin>>type[i]>>queries[i][0]>>queries[i][1] ;
    v.push_back(queries[i][0]) ;
}
sort(v.begin(),v.end()) ;
int u = unique(v.begin(),v.end())-v.begin() ;
f(i,0,u) mp[v[i]] = i+1 ;

where v is a vector<int>, which saves the x coordinates for each query. Then we sort it, and use unique to find the unique entries. u is the total number of unique x coordinates. Then I use a map<int,int> mp, which stores the 1e9->2e5 mapping.

Now, we can build a segment tree. The segment tree will simply store the maximum y value for a segment. This is useful, as when find x y is called, we can query for the range (map[x]+1,u) for a number having value more than y. So, we get the mapped x.

Now we can store all the y's for a single (mapped) x,by creating an array of sets. I've used set<int> xset[MAXN] for this purpose. We can find the first element greater than some element by using xset[x].upper_bound(y).

All being said, here is the insertion function:

void insert(int node,int l,int r,int x,int y)
{
    if(x<l || r<x) return ;
    if(l==r)
    {
        tree[node] = {x,y} ;
        return ;
    }
    int mid = (l+r)>>1 ;
    insert(2*node+1,l,mid,x,y) ;
    insert(2*node+2,mid+1,r,x,y) ;
    tree[node].Y = max(tree[2*node+1].Y,tree[2*node+2].Y) ;
}

This is used along with the add x y query. tree represents the segment tree, where tree[i].X represents the x value and tree[i].Y represents the y value.

This function is called as:

if(type[i]=="add")
{
    xset[mp[queries[i][0]]].insert(queries[i][1]) ;
    insert(0,0,u,mp[queries[i][0]],queries[i][1]) ;
}

Now the removal function which goes along with the remove x y:

void remove(int node,int l,int r,int x,int y)
{
    if(x<l || r<x) return ;
    if(l==r)
    {
        tree[node] = {0,0} ;
        return ;
    }
    int mid = (l+r)>>1 ;
    remove(2*node+1,l,mid,x,y) ;
    remove(2*node+2,mid+1,r,x,y) ;
    tree[node].Y = max(tree[2*node+1].Y,tree[2*node+2].Y) ;
}

Which is called by the following code:

else if(type[i]=="remove")
{
    xset[mp[queries[i][0]]].erase(queries[i][1]) ;
    remove(0,0,u,mp[queries[i][0]],queries[i][1]) ;
}

And now comes the MVP. The function that goes along with the find x y:

int find_next(int node,int l,int r,int start,int end,int val)
{
    if(tree[node].Y<=val) 
        return 0 ;
    if(end<l || r<start) 
        return 0 ;
    if(l>r) 
        return 0;
    if(l==r)
    {
        return tree[node].X ;
    }
    int mid = (l+r)>>1 ;
    int v1 =  find_next(2*node+1,l,mid,start,end,val) ;
    if(v1==0)
        return find_next(2*node+2,mid+1,r,start,end,val) ;
    return v1 ;
    
}

Here have the range (start,end), where we need to find some element which has a value strictly greater than val. This is done by checking the maximum element of the current range. If it is greater than val, then we're sure we have come to the right place. If not, then we ignore this range by returning a zero.

Now we'd like to go to the left child if possible, because remember, in the find query, we needed the first element strictly greater than y. So, if possible, let's find such element in the left child. If no such element is found in the left child, then we look for the element with the mentioned properties in the right child.

Here is the main code that calls this code:

        else //find
        {
            int next = find_next(0,0,u,mp[queries[i][0]]+1,u,queries[i][1]) ;
            // int next = find_next2(0,0,u,mp[queries[i][0]],queries[i][1]) ;//<-----
            if(next==0) cout<<"-1\n"; 
            else
            {
                auto it = xset[next].upper_bound(queries[i][1]) ;//<----
                if(it==xset[next].end()) cout<<"-1\n" ;
                else 
                {
                    cout<<v[next-1]<<" "<<*it<<"\n" ;
                }
            }
        }

Here we try to find the next x element by calling find_next(0,0,u,mp[queries[i][0]]+1,u,queries[i][1]). Look that we're querying for the range mp[queries[i][0]]+1 to u, for values greater than queries[i][1]. If we get a zero as a result, then we know that no such element exists. If it's not a zero, then we can search our y in x's set. If it is not found then set.upper_bound returns an iterator pointing set.end(). So, we can check whether an element strictly greater than y is present in xset[next] or not. If it is present then we output the answer.

Remember f(i,0,u) mp[v[i]] = i+1 ;? This means that v's ith element is mapped as i+1th element. So, we o/p v[next]-1, instead of v[next].

Here is my latest submission. I've submitted ~10 similar solutions in 2 days. I know that I have got the most part of the solution right, but am not able to find what exactly am I doing wrong here.

Any help is appreciated.

Hello,

I was trying to solve 339 A — Peter and Snow Blower, which basically involves a polygon, bound to some point, by a rope. The polygon moves around the point, in a circle. We have to find the area cleared by the polygon.

(It's working correctly here too)

Approach: Find the point that is at the maximum distance from the tethering point ($$$P$$$). This is amongst the vertices of the polygon. To find the point, that is closest to $$$P$$$, we consider each side, and find the point on this segment, that is closest to $$$P$$$. A line perpendicular to the segment, that goes through $$$P$$$ is found. The intersection of the segment and the perpendicular is the point closest to $$$P$$$. This point might not be on the segment, so we have to check that too.

Enough explanation. Here is my code. It fails on test 54, which when I run locally, gives out the correct answer.

Good problem.

So, let's think, why this should happen. The -g flag does change the memory. So, if I am accessing some memory that I should not have, then in the local case, that memory is fixed, but not in the case of the online compiler. So, what memory do I access in my code?

const int MAXN = 1e5+5 ;
pt pts[MAXN] ;

And where do I use it?

f(i,0,n)
{
    T a,b ;
    cin>>a>>b ;
    pts[i] = {a,b} ;
    maxd = max(maxd,dist(P,pts[i])) ;
    mind = min(mind,dist(P,pts[i])) ;
}

n is an input, $$$3 \leq n \leq 1e5$$$, so I don't think we have any problem here. Let's see:

f(i,0,n)
{ 
    int j = (i+1)%n ;
    line l ;
    l.v = getv(pts[i],pts[j]) ;
    l.c = cross(l.v,pts[i]) ;
    pt poii = poi(l,P) ;
    if(inseg(pts[i],pts[j],poii))
    {
        mind = min(mind,dist(poii,P)) ;
    }
}

i goes from 0 to n-1. That doesn't cross any barrier. j=(i+1)%n, so j's range is (0,n-1). That too shouldn't do anything bad.

Is there any other place, where I could do a bad memory access?

I think, but no.

Imported functions work different for different compilers?

Whenever I think it's not my fault, I'm 100% wrong. So no.

Where are you little bug. Where do you hide?

I am trying to find this little bug, please share more strategies to find this little pos.

EDIT: Got the problem. When inserting a string to the trie, the temp->endi is always changed. But when a duplicate string is inserted into the trie, the temp->endi value is changed for the node. This is bad, because the ancestors of this node would have a temp->index according to the index of the previous string. So, we'll DFS into it, but in the end, find that no endi value satisfies our constraints. That's why there was an infinite loop.

So all I had to do was temp->endi=min(i,temp->endi). Here is the AC'd solution.

Hello,

This is regarding codechef's question: Sheokand And String. I am facing a consistent TLE/WA for a test case, which I think, should not be the case.

Question description:

There are $$$N$$$ strings as input. Then there are $$$Q$$$ queries, which are of the form $$$R$$$,$$$S$$$,where $$$S$$$ is the string to search, and $$$R$$$ is the number of strings to consider. That is, if $$$R=3$$$ then the answer should be amongst strings 1,2 and 3.

Now, we have to find the string amongst $$$s_1,s_2,...,s_R$$$, which matches $$$S$$$ the most. If there are many strings that qualify this criterion, then we have to select the lexicographically smallest string.

Example:

4
abcd
abce
abcdex
abcde
3
3 abcy
3 abcde
4 abcde

OUTPUT:

abcd
abcdex
abcde

Now, for the first query, abc is matched with all the three strings, but y doesn't. So now the lexicographically smallest string amongst the starting $$$R$$$ strings is abcd.

For the second query, abcd is matched with 1st and 3rd strings, but e only matched abcdex.

For the third query, you have abcde too to select, which matches the query exactly.

Solution:

The solution uses Tries. One can read about the full theory of the solution here, which is the question's editorial.

Still, I'll give a small overview of the solution. We can create a Trie of all the $$$N$$$ strings in the input. We can save three (or two if you insist) variables: end, endi and index. Where end is the bool which saves whether any string is ending at the current node, endi is the index of the string, which ended at the current node, and index is the string index, for which this node was created. This is a secret weapon we'll use later.

Now, we get a query, and we traverse the trie. We only go to nodes which match (obviously) the current string character, and has index less than $$$R$$$. When this condition falls short, then all we have to do is find the lexicographically smallest string which has endi<=R. We can easily see that if a node has an index<=R, then it will have a node in it's subtree that will have endi<=R. This is so, because index is set, when the node was created by the indexth string. Either this string ended at this node, or later in the subtree. So, yeah, proof.

Now all we have to do is find the first string in the sub-trie which has endi<=R, which would be the answer.

For that we can create a while loop like:

while (!(temp->end) || temp->endi > l)//This might take some time = 26 x 10 (max depth of trie)
{
	f(i, 0, 26)
	{
		if (temp->a[i] && temp->a[i]->index <= l)
		{
			ans += (i + 'a');
			temp = temp->a[i];
			break;
		}
	}
}

Using this will give you a TLE. You'll have to change it to:

while (!(temp->end) || temp->endi > l)//This might take some time = 26 x 10 (max depth of trie)
{
	bool found = false ;
	f(i, 0, 26)
	{
		if (temp->a[i] && temp->a[i]->index <= l)
		{
			ans += (i + 'a');
			temp = temp->a[i];
			found = true;
			break;
		}
	}
	if(!found) break ;
}

Which changes my answer to a WA. Now, I got really confused by this. A TLE means that the while loop is executed infinitely. Thus, the inner loop's if condition is never satisfied, in some case.

But this doesn't make sense. Let's see why:

The code before this code is:

Node* temp = root;
for(int j=0; j<(int)se.size();j++)
{
	int c = se[j] - 'a';
	if (!(temp->a[c]) || temp->a[c]->index > l) break;
	ans += se[j];
	temp = temp->a[c];
}

This means that matching is done only till the either the next letter doesn't exist, or the it does exist, but it's index value is greater than l. Which means that the current node, at which this loop breaks has it's index<=l. (Here l is $$$R$$$).

So, we come back to the while loop. So temp is a node which has it's index<=l. Good. If temp is an end point for a string, and has endi<=l then the loop ends here, and the answer is output. But if that is not the case, then we go in the while loop. From the earlier proof, we know that there is a node in temp's subtree that has endi<=l. So, there should never be the case when the whole for loop is executed and the if condition is not satisfied, atleast one time.

Therefore, I do not understand when is the case applicable.

Here is my solution.

Many AC'd solutions use this loop exit flag (like found, in this case). I hope that there's something I am missing here.

Any help is appreciated!

Thank you.

Hello all,

I was trying to learn about binary lifting, and came across this codechef question.

Gist of the question:

You're given a weighted tree. You are given $$$q$$$ operations, which are of the format $$$u,v,x$$$, where $$$u,v$$$ are the nodes of the tree, for which we have to find the maximum weight path which joins them. $$$u,v$$$ are never each other's ancestors. An edge of weight $$$x$$$ can be used to connect the subtrees of $$$u$$$ and $$$v$$$.

Gist of my solution

Case 1: Do not use $$$x$$$ :

If we do not connect $$$u$$$ and $$$v$$$'s subtrees, then we'll have to find their LCA, and the answer would be $$$dist(u,lca)+dist(v,lca)$$$. LCA can be found using binary lifting. The recurrence for binary lifting is:

And the distance recurrence is:

These can be built in the same for loop as done by me in the code.

Case 2: Use $$$x$$$ :

If we use $$$x$$$ and connect the subtrees of $$$u$$$ and $$$v$$$, then we'll do that by connecting the nodes (in the respective subtrees) which are at the maximum distance from $$$u$$$ (in it's subtree) and $$$v$$$(in it's subtree). That is, let's say $$$u_{alpha}$$$ is the node in $$$u$$$'s subtree that is farthest from $$$u$$$, and $$$v_{\alpha}$$$ is the node in $$$v$$$'s subtree that is farthest from $$$v$$$. Then in this case we get a total distance of $$$dist(u,u_{\alpha})+dist(v,v_{\alpha})+x$$$.

We find the maximum of both of these cases, and return the answer.

Cool. Cool theory. Doesn't work.

Explanation for the code:

Variables:

• depth: Saves the depth of a node from the root

• mcd: Saves the distance of the maximum distant node in the subtree for the i'th node. Could be zero, if all the members of the subtree are at a negative distance.

• dp[i][j][0]: Saves the $$$2^j$$$th parent of $$$i$$$

• dp[i][j][1]: Saves the distance of the $$$2^j$$$th parent of $$$i$$$ from $$$i$$$.

• vector<pii> al[MAXN]: The adjacency list representation of the tree.

Methods: - dfs1: As named, does a $$$DFS$$$. AIM: To create dp[i][0][0], dp[i][0][1], mcd, and depth. The logic behind calculating the mcd is that you get the distance for each child of a the node, and we add the edge weight and compare it to the current mcd value. So yeah you might have got the point.

• main: Creation of dp, running dfs1, running a loop for each query et cetera. In the loop, we get the answer for the case 2, int maxD initially. Then we calculate the answer for the case 1. If the two nodes are not at the same level, then we can we bring them on the same level. Let's assume they have a difference of diff in between their levels, then we can jump up this diff. That is a $$$O(log N)$$$ operation in my opinion.( Not opinion, I know but humble++). This can be done by:

• Move MSB to LSB. That is, if diff=14=(1110), then we go to 2^3rd parent, then from there, go to 2^2nd parent, then from there 2^1st parent, and voila, we're at our destination.

Now, what both our nodes are at the same level, so we go up starting from the 2^19th parent, and go on to j>=0, in order to find the highest ancestors that do not match. In the end, we reach at a point, that is just below the LCA. That is, the parent of u and v is the LCA. Meanwhile, we're also updating our dist variable so store the information of the distance we traverse.

In the end, we compare the values of maxD and dist. Whichever is the greater, is output as the answer.

Here is my code:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<math.h>
using namespace std ;

#define f(i,s,n) for(int i=s;i<n;i++)
#define X first 
#define Y second
#define MAXN 300005

typedef long long ll ;
#define pii pair<ll,ll>
ll  depth[MAXN], mcd[MAXN];
ll dp[MAXN][20][2] ;
vector<pii> al[MAXN] ;

ll dfs1(int node,int par)
{// to create the depth and mcd arrays
    ll mcdV = 0  ;
    for(auto x:al[node]) 
        if(x.X!=par) 
        {
            dp[x.X][0][0] = node ;
            dp[x.X][0][1] = x.Y ;
            depth[x.X] = depth[node]+1 ;    
            mcdV = max(mcdV,max(x.Y,x.Y+dfs1(x.X,node))) ;
        }
    return mcd[node] = mcdV ;
}
int main()
{
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    int T;cin>>T;
    while(T--)
    {

        int n,q ;cin>>n>>q;
        f(i,0,n+1) al[i].clear() ;
        f(i,0,n-1)
        {
            int u,v,w; cin>>u>>v>>w ;
            al[u].emplace_back(v,w) ;
            al[v].emplace_back(u,w) ;
        }
        memset(dp,-1,sizeof(dp)) ;
        memset(depth,0,sizeof(depth)) ;
        memset(mcd,0,sizeof(mcd)) ;
        dp[1][0][0] = 0 ;//parent of node 1 is 0
        dp[1][0][1] = -1e18 ;//distance of 1's parent from it is very loooww
        // depth[0] = -1 ;
        depth[1] = 0 ;
        dfs1(1,0) ;//dp[i][0][0], depth, mcd filled up now.
        f(j,1,20) f(i,1,n+1) dp[i][j][0] = dp[dp[i][j-1][0]][j-1][0], dp[i][j][1] = dp[i][j-1][1]+dp[dp[i][j-1][0]][j-1][1] ;
        //dp created for binary lifting.
        f(i,0,q)
        {
            int u,v,x ;cin>>u>>v>>x ;
            ll maxD = mcd[u]+x+mcd[v] ;
            //check if the path to lca is greater than this.
            if(depth[u]>depth[v]) swap(u,v) ;// u should  always be at the lower depth
            int diff = depth[v]-depth[u] ;
            long long dist = 0 ;
            while(diff)//log(3e5)~20
            {
                int jumpto = floor(log2(diff)) ;
                dist+=dp[v][jumpto][1] ;//<----this way of keeping distances might be wrong
                v = dp[v][jumpto][0] ;
                diff -= (1<<jumpto) ;
            }
            /*
            while(diff)
            {
                int jumpto = diff&(-diff) ;
                v = dp[v][(int)log2(jumpto)][0] ;
                dist+=dp[v][(int)log2(jumpto)][1] ;
                diff-=jumpto ;
            }*/
            //reached the common level 
            for(int j=19;j>=0;j--)//20 
            {
                int av = dp[v][j][0] ;
                int uv = dp[u][j][0] ;
                if(av!=uv)
                {
                    dist+=dp[v][j][1]+dp[u][j][1] ;//jumping simultaneously upwards
                    v = av ;
                    u = uv ;
                }
            }
            //parent of u and v is the lca 
            dist+=dp[v][0][1]+dp[u][0][1] ;
            cout<<max(maxD,dist)<<"\n" ;
        }
    }
}
/* 
1
7 3
1 2 1
1 3 -2
2 4 3
2 5 -4
5 7 5
3 6 6
2 3 1
5 4 2
5 6 0

Expected answer:

10
7
5

 */

See these two submissions:

A

B

The only difference between the two being that A uses a hand-made function I stole from here:

int add(int a, int b) {
 	int res = a + b;
 
 	while (res >= MOD) res -= MOD;
 
 	while (res < 0) res += MOD;
 
 	return res;
}

This function is easy to understand. I am just not sure, why using this only, the running time of the program went down from 936ms to 561ms. That difference is bigger than expected. Can anyone help with, why is this happening? Why exactly is this function faster than simply using %MOD?

I have seen manytimes, that the winner of a Div 2 contest has solved both the A and B problems in less than 6 minutes. How is that done? You have to read, think and implement a question. Unless it's answer is a single line, it takes some time to implement a solution. I tried to solve a series of Div 2 B questions to increase my speed, and if the solution is obvious it takes me approximately 6-7 minutes, and otherwise 11-12 minutes.

I know that these people have a lot of practise, but is there any other tip they can share so that I (and other people like me) can improve our speed in contests?

My solving procedure: 1. Read 2. Think, come to a solution (ummm, obviously)

I do not use a template. I include #include<bits/stdc++.h> library. Then I do a using namespace std;. Then since writing for loop many times takes time, I define a macro like #define f(i,s,n) for(int i=s;i<n;i++). And then I start implementing. Since these questions are much easier, we mostly don't need another method.

Do templates save time here? Is there any other improvement I can make?

Any suggestions are welcome :)

I recently solved 743-D. This required me to create an adjacency list of size 2e5. So, I'd to create a vector of vectors, i.e vector<vector<int>>. If one checks the size of a vector<int> variable, then we'll get 24 bytes. So, $$$4.8 \times 10^6$$$ bytes = 4.8MB. The question clearly mentions that we're given a total of 256 MBs. So the problem here might be that the stack size is smaller than 4.8 MB.

1. So, What is the stack size, and the heap size?

My solution, that used this approach got an MLE (memory limit exceeded).

So, I decided to use the heap memory instead, (by using the new keyword). Here is the submission. The code is obviously harder and less clear. So,

1. Are there other ways to avoid heap usage? Is there something obvious that I'm missing?

2. Are there some easier and obvious ways to use the heap memory?

Any help regarding this is appreciated!

I'm trying to solve 721-C, and thus saw the editorial. I submitted this solution, and it is getting WA for test case 14, which has 50 vertices as input. My solution is counting 50 vertices, whereas in the answer, there are less than 50 vertices. So, there must be a problem in counting the total weight of the path(i.e. the total time taken to reach nth node from 1st node). But there seems to be jo such errata in my view. Plus, the code seems to work for smaller test cases (i.e. with lower $$$n$$$). Therefore, it might be an overflow issue. But that too doesn't seem like the issue.

Any help is appreciated!

Hello there.

I've been trying to log into/register to the UVa Online Judge. The problem being that, it isn't sending me any verification e-mails. I need to practice it's questions, in parallel to the book "Competitive Programming 3", by Halim & Halim.

Any help is deeply appreciated.

Moon.