FEB-17, MAKETRI Editorial (Unofficial)

@swamicoder I agree with you. This is our community and we should be sharing our ideas and contribute to maximize the knowledge building. I am fortunate to have been a small part of journey of this editorial and I remember that it all started with this question

https://discuss.codechef.com/questions/91822/your-logic-for-chef-and-triangles

Now I would like to say one thing. My IAS research topic was Crowdsourced Knowledge Building: Finding Ideal Skillset distribution for maximal knowledge building. I found a mathematical model for the same and thus I would just give a glimpse of the dynamics of knowledge building in crowd sourced environment like StackOverflow, Wikipedia, Quora or our CodeChef discuss community. I will stick to CodeChef discuss community for explanation.

Lets frame base for our understanding. KBS is knowledge building system (CodeChef discuss community) in this case. KU stands for Knowledge Unit. For Q-A community KU is question,answer or vote. Now most important concept in crowdsourced knowledge building is triggering and internal knowledge.

Internal knowledge as the name suggests refers to the knowledge which you possess which is quite small and is constant for isolated system. Major component of knowledge building is Triggered knowledge .

I will give a simple example to simplify things. Suppose I ask you the names of states of India and you say 16 names rapidly, this is your internal knowledge. But then you get stucked and then I give you a hint of say Haryana and you immediately get names of its neighbouring states like Punjab, Uttarakhand etc. This is triggered knowledge. Had I not prompted Haryana, you might not have recalled these names. This is called Triggered knowledge (Recollected Triggered Knowledge).

Triggering is like throwing apples to each other. Best thing is that one KU triggers other KU by some factor which is called triggering factor. Thus, simplifying the stuffs, had the above question not been asked, then we might not have answered and thus our approach might not have come into notice. Also had this question not been asked, some of us might have still been struggling to tackle this problem. Thus, this question triggered some of us and we answered the question, thus adding new KU(answers or unique approaches to the problem) to the KBS which was possible only due to triggering.

Thus, on the whole, I want to say that we should be sharing our approaches and discussing rather than complaining for editorials because this will trigger some of us and we will get some KU in our KBS which would never have come in the community.

I know this might be hectic for most of you and there are various terms like Newton hypothesis, Ortega hypothesis, Internalization, Externalization etc. But @swamicoder your idea has triggered me to apply skillset model for CodeChef discuss community to maximize knowledge building of this community. I framed my model for StackOverflow and Wikipedia but this can be applied here as well.

Please note that I am neither publicizing my research nor my approach to this problem :stuck_out_tongue:

In case anyone did not get idea of triggering or if anyone wants to explore more they can drop a comment.

And @vijju123 kudos to you bro again for an awesome editorial and keep up the good job.

Thanks

nice editorial! Worth reading.
Gonna implement on my own.
thanks mate.

https://www.codechef.com/viewsolution/13089642

done !
it will work for the disjoint cases right?

@ashishsb95

Yes, your code is perfectly fine and it is running for disjoint cases too. I am sorry for replying late, I have an assignment due today, so I m kinda running here and there for material (XD).

Side Note: Do you people want me to put up those additional test cases too? Cause I thought that one could check himself/it’d be enough to see the reference codes. If you people need something more in editorial then suggestions are always welcome! :slight_smile:

@utsavgoel

Your code fails to check if the possible values of triangle lie inside interval of [L,R] or not. See here. If your run your code against the 3rd corner case I posted in the end, your code would fail as-

Compilation Successful
Input (stdin)
3 50 80
1 5 15
Your Output
-74

It simply updates the values without checking if the lower/upper limits are inside L and R or not. You will take max of start[I] and L, but what if start[I] is more than R? Similar argument holds for end[I].

Check the reference codes carefully. We put have used-

if(interval_end[i]<L || interval_start[i]>R)
            continue;
		// make sure we don't go less than L
		interval_start[i] = max(interval_start[i], L);
		interval_end[i] = min (interval_end[i], R);

The if statement at the start is worth million dollars, as it would immediately skip the iteration if the intervals lie completely outside [L,R]. Hope that clarifies your doubts :slight_smile:

1 Like

Thanks @vijju123 for this excellent editorial and also to @meooow for his clear solution
Thank you very much learnt a lot and very happy that count of partially solved problems decreased by one:)

@vijju123 @meooow @inovation123
What is wrong in this submission. CodeChef: Practical coding for everyone

    import java.math.BigInteger;
    import java.util.Arrays;
    import java.util.Scanner;
    class MAKETRI {

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int n = in.nextInt();
	BigInteger l = in.nextBigInteger();
	BigInteger r = in.nextBigInteger();
	BigInteger answer = new BigInteger("0");
	BigInteger arr[] = new BigInteger[n];
	for(int i=0;i<n;i++)
		arr[i] = in.nextBigInteger();
	
	Arrays.sort(arr);
	
	Range obj[] = new Range[n-1];
	for(int i=0;i<n-1;i++){
		obj[i] = new Range(arr[i].subtract(arr[i+1]).abs().add(BigInteger.ONE), arr[i].add(arr[i+1]).subtract(BigInteger.ONE));

	}
	
	//finding range in O(n)
	BigInteger low = r.add(BigInteger.ONE);
	for(int i=n-2;i>=0;i--){
		if(obj[i].start.compareTo(r)>0 || obj[i].end.compareTo(l)<0){
			continue;
		}
		BigInteger effEnd = low.min(obj[i].end);

		BigInteger effStart;
		if(obj[i].end.compareTo(low) >= 0){

			effEnd = effEnd.subtract(BigInteger.ONE);

		}
		if(obj[i].start.compareTo(l) < 0)
			effStart = l; 
		else
			effStart = obj[i].start;
		low = effStart;
		answer = answer.add(BigInteger.ONE).add(effEnd.subtract(effStart));
	}
	System.out.println(answer);
}

static class Range{
	BigInteger start;
	BigInteger end;
	Range(BigInteger start, BigInteger end){
		this.start = start;
		this.end = end;
	}
}

}

kudos to you bro for such a nice and detailed editorial, awesome explanation and I am sure this editorial is gonna help many newbies and motivate them to enjoy competitive programming. Keep up the good work :slight_smile:

1 Like

No bro, to be honest you have a HUGE contribution towards it too!! I was simply in love with your code and the comments you added there. They were simply mind-blowing! :slight_smile:

Thanks dear :slight_smile:

Nice effort @vijju123 :slight_smile:
A few things:

  1. I understand that you explained the problem in detail but the length of the editorial might scare the beginners.
  2. Since we are asked to find the combined length of the intervals and not the intervals themselves, we can avoid the stack.
  3. We do not need to sort the intervals before going over them because they are guaranteed to be already sorted by their ending values (by triangle inequality).
    The last two points will reduce the size of your editorial considerably. I can help you with the code if you are willing to make the changes :slight_smile:
4 Likes

@vijju123 Thanks for the complement but seriously editorial is amazing, keep it up :slight_smile:

1 Like

Thanks bro :slight_smile:

@meooow is right. The editorial is too scary for every one to grip each and every line. This question belong to easy level so i don’t think that there is any need for such a big and bulky explanation. You should try to cut down some part of it so that everyone could able to give time to read this one. I hope you will consider that point.

@meooow. Yeah…length :3. That’s something I tried to contain (and failed miserably lol).

I would love to see your POV too! I sorted the intervals because it was easy to have “feels” when they are sorted by starting positions (and most of the codes I came across used same implementation. So I felt its easier to connect).

Why don’t you put up your POV as an answer? I can redirect the people quoting there “In case you want a quicker way, check meoow’s answer below. Else if its easier to connect with this implementation, proceed below.” Or anything you say. I am perfectly fine with it :slight_smile:

We are trying our best. I tried editing and will keep editing till it is best suitable to everyone’s needs. I kinda knew the explanations were bulky, but I don’t want anybody to have a blank face and go googling like crazy after reading editorial. I just wanted this editorial to be independent and self sufficient :). That’s all!

Hey @vijju123 here is my solution. No structs, no stacks, no sorting of intervals. And I think you should update your explanation to make it simpler, it’s your editorial after all :stuck_out_tongue:

1 Like

Thanks! I shall do the needful by tomorrow evening. (Please excuse me for today, I am dead tired after writing this editorial. I think you can feel me here :p)

Yes bro! I will try my bestest best to edit the editorial and make it crispier by tomorrow evening. Actually I would have done that now…but I have these monstrous college assignments. But truthfully, it was a good learning experience and I hope I get such a support from you, community and everybody here in future as well!!! :slight_smile:

sure bro I am a learner myself, just learning bit by bit daily by you all amazing people and I can understand your pain because I have Mid sem knocking the door from next week :slight_smile:

1 Like