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;
}
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
499
99999 499
99600 1
99400 1
99200 1
99000 1
98800 1
98600 1
98400 1
98200 1
98000 1
97800 1
97600 1
97400 1
97200 1
97000 1
96800 1
96600 1
96400 1
96200 1
96000 1
95800 1
95600 1
95400 1
95200 1
95000 1
94800 1
94600 1
94400 1
94200 1
94000 1
93800 1
93600 1
93400 1
93200 1
93000 1
92800 1
92600 1
92400 1
92200 1
92000 1
91800 1
91600 1
91400 1
91200 1
91000 1
90800 1
90600 1
90400 1
90200 1
90000 1
89800 1
89600 1
89400 1
89200 1
89000 1
88800 1
88600 1
88400 1
88200 1
88000 1
87800 1
87600 1
87400 1
87200 1
87000 1
86800 1
86600 1
86400 1
86200 1
86000 1
85800 1
85600 1
85400 1
85200 1
85000 1
84800 1
84600 1
84400 1
84200 1
84000 1
83800 1
83600 1
83400 1
83200 1
83000 1
82800 1
82600 1
82400 1
82200 1
82000 1
81800 1
81600 1
81400 1
81200 1
81000 1
80800 1
80600 1
80400 1
80200 1
80000 1
79800 1
79600 1
79400 1
79200 1
79000 1
78800 1
78600 1
78400 1
78200 1
78000 1
77800 1
77600 1
77400 1
77200 1
77000 1
76800 1
76600 1
76400 1
76200 1
76000 1
75800 1
75600 1
75400 1
75200 1
75000 1
74800 1
74600 1
74400 1
74200 1
74000 1
73800 1
73600 1
73400 1
73200 1
73000 1
72800 1
72600 1
72400 1
72200 1
72000 1
71800 1
71600 1
71400 1
71200 1
71000 1
70800 1
70600 1
70400 1
70200 1
70000 1
69800 1
69600 1
69400 1
69200 1
69000 1
68800 1
68600 1
68400 1
68200 1
68000 1
67800 1
67600 1
67400 1
67200 1
67000 1
66800 1
66600 1
66400 1
66200 1
66000 1
65800 1
65600 1
65400 1
65200 1
65000 1
64800 1
64600 1
64400 1
64200 1
64000 1
63800 1
63600 1
63400 1
63200 1
63000 1
62800 1
62600 1
62400 1
62200 1
62000 1
61800 1
61600 1
61400 1
61200 1
61000 1
60800 1
60600 1
60400 1
60200 1
60000 1
59800 1
59600 1
59400 1
59200 1
59000 1
58800 1
58600 1
58400 1
58200 1
58000 1
57800 1
57600 1
57400 1
57200 1
57000 1
56800 1
56600 1
56400 1
56200 1
56000 1
55800 1
55600 1
55400 1
55200 1
55000 1
54800 1
54600 1
54400 1
54200 1
54000 1
53800 1
53600 1
53400 1
53200 1
53000 1
52800 1
52600 1
52400 1
52200 1
52000 1
51800 1
51600 1
51400 1
51200 1
51000 1
50800 1
50600 1
50400 1
50200 1
50000 1
49800 1
49600 1
49400 1
49200 1
49000 1
48800 1
48600 1
48400 1
48200 1
48000 1
47800 1
47600 1
47400 1
47200 1
47000 1
46800 1
46600 1
46400 1
46200 1
46000 1
45800 1
45600 1
45400 1
45200 1
45000 1
44800 1
44600 1
44400 1
44200 1
44000 1
43800 1
43600 1
43400 1
43200 1
43000 1
42800 1
42600 1
42400 1
42200 1
42000 1
41800 1
41600 1
41400 1
41200 1
41000 1
40800 1
40600 1
40400 1
40200 1
40000 1
39800 1
39600 1
39400 1
39200 1
39000 1
38800 1
38600 1
38400 1
38200 1
38000 1
37800 1
37600 1
37400 1
37200 1
37000 1
36800 1
36600 1
36400 1
36200 1
36000 1
35800 1
35600 1
35400 1
35200 1
35000 1
34800 1
34600 1
34400 1
34200 1
34000 1
33800 1
33600 1
33400 1
33200 1
33000 1
32800 1
32600 1
32400 1
32200 1
32000 1
31800 1
31600 1
31400 1
31200 1
31000 1
30800 1
30600 1
30400 1
30200 1
30000 1
29800 1
29600 1
29400 1
29200 1
29000 1
28800 1
28600 1
28400 1
28200 1
28000 1
27800 1
27600 1
27400 1
27200 1
27000 1
26800 1
26600 1
26400 1
26200 1
26000 1
25800 1
25600 1
25400 1
25200 1
25000 1
24800 1
24600 1
24400 1
24200 1
24000 1
23800 1
23600 1
23400 1
23200 1
23000 1
22800 1
22600 1
22400 1
22200 1
22000 1
21800 1
21600 1
21400 1
21200 1
21000 1
20800 1
20600 1
20400 1
20200 1
20000 1
19800 1
19600 1
19400 1
19200 1
19000 1
18800 1
18600 1
18400 1
18200 1
18000 1
17800 1
17600 1
17400 1
17200 1
17000 1
16800 1
16600 1
16400 1
16200 1
16000 1
15800 1
15600 1
15400 1
15200 1
15000 1
14800 1
14600 1
14400 1
14200 1
14000 1
13800 1
13600 1
13400 1
13200 1
13000 1
12800 1
12600 1
12400 1
12200 1
12000 1
11800 1
11600 1
11400 1
11200 1
11000 1
10800 1
10600 1
10400 1
10200 1
10000 1
9800 1
9600 1
9400 1
9200 1
9000 1
8800 1
8600 1
8400 1
8200 1
8000 1
7800 1
7600 1
7400 1
7200 1
7000 1
6800 1
6600 1
6400 1
6200 1
6000 1
5800 1
5600 1
5400 1
5200 1
5000 1
4800 1
4600 1
4400 1
4200 1
4000 1
3800 1
3600 1
3400 1
3200 1
3000 1
2800 1
2600 1
2400 1
2200 1
2000 1
1800 1
1600 1
1400 1
1200 1
1000 1
800 1
600 1
400 1
200 1
Your code gives
199500
However the answer is
199600
The correct rectangle has a height of 499, starts from 99600 and ends at 100000.
It’s an easy fix. Your logic is correct.
1 Like
Hi @everrule1 , Thanks for your response. Can you please guide me on how to generate these kind of test cases?
I found the mistake, and then made the test case. It’s very unlikely a random test case would break your code
1 Like
Oh. OK. Thank you so much
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?
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.
2 Likes
@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?
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;
everule1:
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;
@everule1 I’ve made the required change updated soln here but yet no success. The same case is failing again.