November Cook - Off Discussion

[saurabhshadow]

Why no editorials till now for November Cook-off @vijju123 @admin ?

[mahlasachin]

what is wron with this code?
this code is giving wrong answer.
problem is CodeChef: Practical coding for everyone
#include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n],h[n];
for(int i =0 ;i<n;i++)
cin>>a[i]>>h[i];

	sort(a,a+n);
	int diff[n-2];
	for(int i = 1;i<=n-2;i++)
		diff[i-1] = a[i+1] - a[i-1];
	sort(diff,diff+n-2);
	//for(int i =0 ;i<n-2;i++)
		//cout<<diff[n-3-i]<<"  "<<index[n-3-i]<<endl;
	sort(h,h+n);
	int area = 0;
	for(int i = 0;i<n-2;i++)
		area += h[n-1-i]*diff[n-3-i];
	if(a[1]-a[0]>=a[n-1]-a[n-2])
		area += (a[1]-a[0])*(h[1])+(a[n-1]-a[n-2])*(h[0]);
	else
		area += (a[n-1]-a[n-2])*(h[1])+(a[1]-a[0])*(h[0]);
	cout<<area<<endl;
} 

}

[vijju123]

Editorialist is working on them. Thats all I can update.

[saurabhshadow]

As far as we know editorials are supposed to be prepared before the contests.

[ravi_469]

can you explain me the reason why this needed
else
{
if(arr[i][j]!=0)
ret++
}

[pulkit_mittal]

Remove the last if else condition.
Add those terms in diff. array,i.e.,(a[1]-a[0]) and(a[n-1]-a[n-2]).
Now diff contains n elements.
Sort and multipy.
NOTE-I did the same mistake during contest.

[mohitz_007]

You. Have not defined n while declaring a[n]

[akshayakgec]

Oh! I get it now thanks for the help : )

[i_64]

November Cook - Off Discussion

If index (i+r) or (j+c) is out of bounds, the question says assume the cell to be 0(zero). So, if (index within bounds) check if arr[i][j] == brr[i+r][j+c] else check if arr[i][j] == 0. I’ve just replaced brr[i+r][j+c] by zero, as per the problem statement. To avoid this confusion, you can do as @ritesh1340 has done, declare a larger array so that you never go out of bounds, and initialize it to zero. That way you don’t need the if else conditions.

[thedarkknight]

can you send your solution for ROBOTS using segment tree

[anon25504910]

Ig I have stored 3 values per node: x shift caused due to range pf queries [L…R], y shift caused due to range [L…R] and angle shift caused due to range [L…R]. Build like this:
Say you have a parent with left and right pointers l and r. Then you can calculate length of shift caused by R, and the angle of this shift is sum of the angle of left + angle of right. Now we can resolve this length into x and y components, and add them to the x and y shifts of left. This gives x and y shifts for the parent. And sum of angular shifts gives angle.
Now, for query, I assume you know how to search a range in the segtree: walk down, which is the same as resolving the interval into at most \log N intervals that exist in the segtree. Note that due to the way in which the recursions are called, the “leftmost and bottommost” interval is calculated first, and so on. This means each round of querying can add to the current angle the angle due to this subinterval; this angle can now be used as a ‘base’ for the next subinterval. So, somewhat like a standard segtree query but slightly different.

[bspraju]

For the SIGNTURE problem, though the problem statement does not call out specifically that dr and dc should be choosen in such a way that all the black cells have to be considered from B, how can a signature be same if some of the black cells are not considered from B. For test case 4, how can the signatures be same with no errors. If we select dr and dc such a way that some of the black cells in B move out of index range, they should be counted as part of the flip. Otherwise it is like matching signature only to part of what is signed in B and ignoring the rest of black cells from B. May be the problem statement is not looking for that, but it does not make sense to say the signatures are same.

[vkjha1010]

This video editorial might be useful for understanding the concept behind ROBOTS problem of november’19 cook off : [Tutorial] Codechef Nov'19 Cook Off - ROBOTS - YouTube

[anon2040365]

Loved your explanation bro