Coding ninjas - weekend contest 102

The first 2 probs were just formality kind of stuff, the main crux was the second half of the problems that were the main deciding factor for the ranks.

So, I'll be putting the logics for only the last two.

The logic of the Positive-Negative Sequence Problem:-

There were just 2 things required for this, 

1) idea of Sliding window Technique and 

2) understanding that sliding window is applicable here.

The problem clearly stated that X will be negative and Y positive and we needed elem <=X and >=Y so that means that for X i'll be considering the negative elems of the array and the positive ones for Y.

Now, Keeping in mind that we need a subarray...using the sliding window technique, whenever I'll get a - elem I'll add that in say sum1 and for + elem will add that in sum2 and will keep expanding the window untill both the conditions are met.

If the condition is met, So we know that we got a subarray! But... we can try to reduce the len of this by removing elems from this, so now we'll start contracting the window from the left, and whatever elem will be removed will remove it's contribution in the respective summation.

If by removal of any elem either of condition gets false then we again need to expand the window else just update the minimum len of the subarray.

The problem was trying to misguide us towards thinking of this problem as a Subsequence one or something. I took like 12 minutes to get the conclusion of this idea and then started implementation.

The logic of the Good Tree Problem:-

The Problem also just required you to have 3 things:-

1) Previous Idea of going from 1 vertex to other using the adjacency list thing, 

2) A basic idea of recursion cause we had to check for vertices with colors 1 and 2, so had to make some logic on top of just going from 1 vertex to other.

3) Cause we needed all the pairs of the vertices with color 3, one must have the idea of using 2 loops to achieve that. Although this is like a very basic thing but still is a requirement according to me, cause this can be a whole separate problem for someone new to programming.

The problem is super easy if you can visualize that you are going from 1 vertex to other in a graph(through all the possible ways) and in the process you are continuously checking for the colors of nodes. 

The solve function is what I am using for exploration stuff, the base conditions are:-

1) if all the 3 conds(conditions) that is I get 1 vertex with color 1 another with color 2 and that I reach the final destination vertex, in this case solve would return True

2) if after exploring every neighbour True is not returned means, not possible so return False.

The visited and all stuff is part of the technique of exploring the path using the adjacency list, if you get a confusion with the working of the recursion or if you are getting queries in visualising the process then I would prefer to understand the adjacency list stuff first before approaching this problem.

Well, this problem would have been easier for people who had done the POTDS of GFGS for the last 2 months cause I remember that I had like 2 or 3 probs like this, not all same but mostly the feeling of exploring a graph was same.

I wouldn't call this an easy one for me at all, in fact I did this in like the last minute so definitely that was close.

Overall...

This contest was much awaited by me, cause the last time I attempted Weekend Contest 101, that was my first contest participation in Coding Ninjas was a bummer, I couldn't solve 2 problems that I should have been able to solve and this time I had made my mind to get all the 4 probs and luckily I could do that with 1 min on the Clock. I am little satisfied by the performance, I had a rank of 178 something in this, well, that is fairly better than the 1180 that I had last time.