Editorial/explanation for feb 17 2nd poblem

problem:-https://www.codechef.com/FEB17/problems/MAKETRI/
plz help out

I have read that if array is sorted in increasing order than for each adjacent elements of array( say a,b) inorder to find third side (say c) ,so as to form non degenerate triangle , there is no nedd to check for all three triangle inequality conditions , insted only one i.e if c<a+b then c is valid side.
So how can i use this logic? plz help me

1 Like

I have heard that someone made an editorial for this problem here :stuck_out_tongue: - https://discuss.codechef.com/questions/92733/feb-17-maketri-editorial-unofficial

Give that Editorial a full read before attempting solution. Will save you headaches later on ^^

Your faults are in MAX, MIN and Sorting.

I say, MAKE YOUR OWN FUNCTION instead of using macros. Macros can give you some unexpected errors because of their pure “Find and Replace” type of working.

When i replaced your qsort with normal sort, I got full AC.

Link to your AC solution (Its in C++ tho ) - https://www.codechef.com/viewsolution/14288968

Now, why is your qsort wrong?

Because here-

int cmp(const void *p,const void *q)
{
	int a,b;//WHY INT?? :p 
	a=*(int *)p;//WHY INT?
	b=*(int *)q;//WHY INT?
	if(a<b)
	return -1;
	else 
	return 1;
} 

When the values get upto 10^18, your qsort fails to sort them in correct order. Thats it, these were the 2 bugs here :slight_smile:

1 Like

Quick Explanation

Sort the array, then take adjacent lengths A_{i} and A_{i+1}. Perform union of intervals for the solutions of each pair:

S = \bigcup_{i = 1}^{n - 1}{\begin{cases} [L, \bar{R}] & A_{i+1} < L \\ [\bar{L}, \bar{R}] & L \leq A_{i+1} \leq R \\ [\bar{L}, R] & R < A_{i+1} \end{cases} }

where

\bar{L} = max\{L, A_{i+1}-A_{i}+1\}
\bar{R} = min\{R, A_{i}+A_{i+1}-1\}

We can perform the union by sorting these intervals and maintaining a stack. Then the answer is |S|.


Proof / Long Explanation

Let C be the side we want to test such that L \leq C \leq R is satisfied. We have two other sides A and B from the array, where A \leq B.

Case 1

Suppose C is longest side. This means A \leq B \leq C and we have to satisfy A+B > C. In one loop, the rightmost A and B that are not more than C will give the maximum. Satisfying both inequalities:

Given: B \leq L
L \leq C < A + B \&\& L \leq C \leq R
L \leq C \leq min\{R, A + B - 1\}
\therefore C \in [L, min\{R, A + B - 1\}]

Case 2

Suppose C not the longest. Ergo, A \leq B and C < B. This means that we want to satisfy A+C > B \iff C > B - A. We want to minimize B-A to get the biggest union. Satisfying the inequalities:

Given: L < B
B - A \leq C \leq R \&\& L \leq C \leq R
max\{L, B - A + 1\} \leq C \leq R
\therefore C \in [max\{L, B - A + 1\}, R]

Now, we show that A=A_{i} and B=A_{i+1}. To show that, we show that A and B must be adjacent. In case 1, we want to maximize A+B. Indeed, having them adjacent gives the maximum. In case 2, we want to minimize B-A. The minimum pair must also be adjacent. \blacksquare

1 Like

One thing, there’s a concise way to do union of intervals. I suggest you to take a shot at this fully-detailed editorial by @vijju123
for the implementation details! :smiley:

1 Like

Lmao, i wanted to give that guy a surprise XD

1 Like

I used the same logic , mentioned in the below post infact same code of c++,in c still getting wrong answer for few test cases

my solution (in c):- https://www.codechef.com/viewsolution/14288641
editorail’s solution (in c++) :- https://www.codechef.com/viewsolution/13063924

still not getting all test cases accepted :frowning: plz guys

i have used ur logic , and code also but in c still wrong answer for few cases
my solution:- https://www.codechef.com/viewsolution/14288641
ur solution (AC) :-https://www.codechef.com/viewsolution/13063924

Thats not “Some” test cases lol. Its like, the half of them. XD

Dont worry dear, I am already debugging your code ^^

bro have u identified mistake for half test cases

Yes, i am fixing it atm. Will give you corrected code^^

thanks bro btw (MIN,MAX) were right only qsort was wrong :slight_smile: good luck bro

Perhaps. I first removed them and got few more cases to pass, so i assumed there must be something. Good you got AC finally ^^