November Cook - Off Discussion

Since N, M is small, you can do brute force. Try for all - n < dr < n, -m < dc < m
and calculate error.
Error: Difference between original & translated new matrix + Values in original which are not translated but are 1.

I don’t understand how solving 1 problem and then sleeping is literally enough to bring me up a star…

1 Like

SIGSEGV is caused by some exception, like divide by zero, array index out of bound etc.
check your loop. Like you have declared your array of size n i.e. your indexes will be in range 0 to n-1, but in 5th line inside your loop, you are accessing index n (when i = n-1 & you are trying to access arr[i+1] ), which is not possible (called array index out of bound exception).

You deserve >=5 stars

Great approach brother :ok_hand:

2 Likes

Don’t need to do trapezium.

As the question asks for 2s, this is the triangle portion of the points (abs(h1-h2) * abs(x1-x2) + (min(h1,h2) * abs(x1-x2) * 2) for the area for each 2 point segment (two triangles on top of each other make a rectangle).

From this, you can see the best answer will have the biggest h1,h2 for the biggest difference in x1, x2. Sort x1 and x2 based on the distance they have from their neighbors, and height by accending order. The closest x1 and x2 should be matched with he smallest heights. This pair array should then be sorted by x, and the cordinates should be entered into the function above to find the individual areas.

Yep, the switch statement is wrong in implementation. I see you’ve picked up the cases correctly, but 0 does not always give +2. It changes the angle. So the first ‘1’ would give +1, the second 1 would give 0, the third one would give -1, etc (going around the circle). The different cases change the angle, so you need a %6 somewhere.

else {
if (l != 0) {
x = (cx[r] - cx[l-1]);
y = (cy[r] - cy[l-1]);
}

			else {
				x = cx[r];
				y = cy[r];	
			}

This bit is kinda wrong. I don’t know why you’re minusing the x (it’s a variable value each time).

The sin and cos calculation are also only ever 0.8, -0.8, 0.5, and -0.5 so you can save on time there.

However, in this question you also had to memoize previous calculations which I failed to do.

The distances between the x are variable.

You want the max heights to be where the max distances between x are (biggest area gains).

distance between first and last is just to one neighbor, for all others to all neighbors.

In which order will we take the height ?

Heights are the x coordinates…Then any order as ending or descending order of differences of consecutive point but multiply the maximum height differences with maximum of sum of parallels . I didn’t tried but hopefully that’s the correct way

Actually too few participants were there in this cookoff for div 1 due to end semesters rarely I dont participate in contests at codechef and codeforces but the exams were also coming o I preferred exams over the competition but when I solved first question in one go I regret my decision not to participate as the first question of div1 as unusual was very easy to solve.

easy solution link.

plesase see the small code

This is the basic approach when all the points are consecutive but see when points are non consecutive your approach will fail see the link of my solution
easy-code

Thanks, I will try with Brute force…

Yeah, I had endsems until friday + codechef certification yesterday. Was kind of an onlooker, solved but did not submit during the contest window.

I was just going through my solution of BIGRES and realized that i did not write what i intended to, still got AC during contest !

Solution submitted during contest
https://www.codechef.com/viewsolution/27936782
Submitted in practice
https://www.codechef.com/viewsolution/27941380

Notice the difference in lines 19 and 20 of both solutions
I got AC because java initializes array with 0

Can anyone help me figure out where i am wrong with approach for ques ROBOTS.
My submission link is : https://www.codechef.com/viewsolution/27939515

Can someone explain me the approach for the problem The Biggest Restaurant.

It is the only mistake i made during the contest. Rest of my solution was correct.:frowning: