ZCO15004 Please help me debug my code

anon85470456 · April 16, 2020, 9:01am

Problem statement is here : CodeChef: Practical coding for everyone
Its failing for one test case.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int main()
{
	//freopen("in.in", "r", stdin);
	
	int n;
	cin >> n;
	
	vector <pair<int, int> > v;
	
	for(int i = 0 ; i < n ; i++)
	{
		int p, q;
		cin >> p >> q;
		
		v.push_back(make_pair(p, q));
	}
	
	sort(v.begin(), v.end());
	
	int x[n + 2], y[n + 2];
	
	x[0] = 0, y[0] = 0;
	x[n + 1] = 100000, y[n + 1] = 0;
	
	for(int i = 1 ; i <= n ; i++)
	{
		x[i] = v[i - 1].first;
		y[i] = v[i - 1].second;
	}
	
	int left_small[n + 2], right_small[n + 2];
	
	stack <int> stk;
	stk.push(0);
	
	for(int i = 1 ; i <= n ; i++)
	{
		while(y[stk.top()] >= y[i])
		{
			stk.pop();
		}
	
		left_small[i] = stk.top();
		stk.push(i);
	}
	
	/*for(int i = 1 ; i <= n ; i++)
	{
		cout << left_small[i] << " ";
	}*/
	
	while(!stk.empty())
	{
		stk.pop();
	}
	
	stk.push(0);
	for(int i = n ; i >= 1 ; i--)
	{
		while(y[stk.top()] >= y[i])
		{
			stk.pop();
		}
	
		right_small[i] = stk.top();
		stk.push(i);
	}
	
	//cout << endl;
	
	for(int i = 1 ; i <= n ; i++)
	{
		//cout << y[right_small[i]] << " ";
	}
	int ans = 0;
	
	for(int i = 1 ; i <= n ; i++)
	{
		ans = max(ans, (x[right_small[i]] - x[left_small[i]]) * y[i]);
		
		//cout << x[right_small[i]] << " " << x[left_small[i]] << endl;
	}
	
	for(int i = 1 ; i <= n + 1 ; i++)
	{
		ans = max(ans, (x[i] - x[i - 1]) * 500);
	}
	
	cout << ans;
}

everule1 · April 16, 2020, 11:20am

Here’s a test case. I wouldn’t have been too surprised if it passed. It fails only on a super specific test case.

Warning, large test data

Your code gives

However the answer is

The correct rectangle has a height of 499, starts from 99600 and ends at 100000.
It’s an easy fix. Your logic is correct.

anon85470456 · April 16, 2020, 11:31am

Hi @everrule1, Thanks for your response. Can you please guide me on how to generate these kind of test cases?

everule1 · April 16, 2020, 11:33am

I found the mistake, and then made the test case. It’s very unlikely a random test case would break your code

anon85470456 · April 16, 2020, 11:34am

Oh. OK. Thank you so much

anon85470456 · April 16, 2020, 11:54am

Thank you @everrule1. Got AC. I was so frustated while debugging this solution that I actually wrote the whole solution from scratch again and that one actually passed, but I couldn’t figure out the mistake in this one.
Off topic but why does your name show different on discuss profile and codechef profile?

everule1 · April 16, 2020, 1:34pm

After emptying the stack, you are pushing 0, not n+1.
About my name, that you’ll need to ask codechef. They haven’t responded for 2 months.

anon85470456 · April 16, 2020, 1:59pm

oh

relaxxpls · October 6, 2020, 5:06am

@everule1 my sol too is failing for just the first case of the first sub task. The method used is similar to Keshav Dhandhania’s Method except that I’ve added the top right boundary corner and the top left boundary corner to the list of points before calculation of the next and previous smaller element.
The test case you had sent too is working just fine.
Further I’ve tried to bruteforce my solution against 4,000 random cases and still none fail.

Any help please?

everule1 · October 6, 2020, 10:05am

Your input is wrong. Instead of checking temp, you should take minimum of all y.

Also Stop using 100000 in your code!!!.

Use

const int MAXX = 100000;
const int MAXY = 500;

relaxxpls · October 7, 2020, 12:28am

@everule1 I’ve made the required change updated soln here but yet no success. The same case is failing again.