I made a submission to the following problem: here. Problem description(modified) is as follows:
There is a large block of height N cells and length N cells. The block is made up of vertical columns of soil, each of which is one cell long. Each column has a continuous vertical gap, with the ith column having its gap from the li th cell to the hi th cell (starting from the bottom, 0-indexing). That is, in the ith column, there is no soil from the li th cell to the hi th cell (both inclusive). We need to build additional gaps by clearing some cells of soil so a track of height H is created for N consecutive columns. Find minimum number of soil cells that need to be removed.
I wrote an O(n) algorithm for the task, but somehow its getting a WA in larger subtask and after spending a lot of time I am unable to figure out why. Here is a link to my submission: submission. Hence posting this question so may be if someone is feeling generous they can help me out.
Thanks in advance.
Code submitted:
#include <iostream>
#include <climits>
#define SIZE 1000000
using namespace std;
int main(void) {
int t, n, h, a, b;
long long *values = new long long[SIZE];
cin>>t;
while(t--) {
cin>>n>>h;
for (int i=0; i<n; ++i) {
values[i] = 0;
}
for (int i=0; i<n; ++i) {
cin>>a>>b;
values[a] -= 1;
if (b<=n-2) {
values[b+1] += 1;
}
}
long long prefixSum = 0;
for (int i=0; i<n; ++i) {
prefixSum += values[i];
values[i] = n+prefixSum;
}
long long mudPresent = 0;
long long minMudPresent = LONG_MAX;
for(int i=0; i<n; ++i) {
if (i<h) {
mudPresent += values[i];
} else {
if (mudPresent < minMudPresent) {
minMudPresent = mudPresent;
}
mudPresent += values[i];
mudPresent -= values[i-h];
}
}
if (mudPresent < minMudPresent) {
minMudPresent = mudPresent;
}
cout<<minMudPresent<<endl;
}
delete values;
return 0;
}
What is weird about this is that could not find a mistake even after I wrote a test case generator file. I ran my program and compared my output with someone else’s accepted solution (using diff utility). I found no difference on multiple runs. Hope somebody can help me out. Here is the test case generator script:
#!/usr/bin/env python
from random import randint
f = open('testCases1.txt','w')
t = randint(1, 10000)
f.write('{}\n'.format(t))
for _ in xrange(t):
n = randint(1, 10000)
h =randint(1,n)
f.write('{} {}\n'.format(n,h) )
for _ in xrange(n):
l = randint(0, n-1)
hi = randint(l, n-1)
f.write('{} {}\n'.format(l,hi))
f.close()