http://www.codechef.com/viewsolution/3904846 is my solution to the problem, I have tried all the test cases provided in the above answers and also the sample test case and it is working fine, I’m not able to figure out why my code is getting a WA.
i ma getting compilation error due to array size is too large … #include <bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
return ((a)>(b)?(a):(b));
}
int a[100000][100000];
int main() {
// your code goes here
int n,m,p,i,j,ans,x,y,flag=0;
cin>>n>>m>>p;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[i][j]=j;
}
}
while(p–)
{
cin>>x>>y;
a[x][y]=a[x][y]+1;
}
for(i=1;i<=n;i++)
{
ans=0,flag=1;
for(j=m;j>1;j–)
{
if(a[i][j]>=a[i][j-1])
{
ans=ans+(a[i][j]-a[i][j-1]);
}
else
{
flag=0;
break;
}
}
if(flag==0)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
return 0;
}
Since the explanation states “We can use map to perform this process efficiently”, I assume it means that we have to add an entry in our map which shows that (j-1) and (j+1) are not increased. Or more plainly, j+1 and j-1 are increased by 0.
sorting is a very expensive operation. Initial cost is M-1. Consider this. If first element is increased, cost goes down by 1. If last element is increased, cost goes up by 1. If any other element is increased, as long as it is smaller than next, cost is unaffected. Hope you get the rest of idea, like checking if it was previously smaller and now larger and all that too.
@darkshadows : this kind of discussion (specially commenter’s reply) clearly shows that there is a lack of effort in editorial making. Similar responses have been in the last long challenge when you were the editorialist (@xwllos0 saved your day by his solution GERALD08 - Editorial - editorial - CodeChef Discuss). Please don’t slack off on your work, it is an important reason for codechef to attract competitive programmers.