I did this in pretty naive way…
stored all the queries in vector pairs…
sorted the vector pairs with first element increasing and corresponding second element decreasing…
for e.g if pairs are (1,2) (2,3) (2,1) (2,4)… the results of sorting would be (1,2) (2,4) (2,3) (2,1)…
then…
j=0;
for i from 1 to n:
if pair.at(j).first==i:
count all the occurrences of pair.at(j).second (since vectors are sorted, just increment j and keep checking
count all occurrences of next number and if the next number is 1 less than previous number that this count shouldn't be greater than count(previous number)+1
if its not 1 less than previous number than count shouldn't be more than 1
count all the occurrences of (i,m).. let this be k
count all the occurrences of (i,1).. lets this be f
if all the conditions above are satisfied answer is (m+k)-(f+1)
else its -1
else:
ans is m-1
</pre>
http://www.codechef.com/viewsolution/3885273
is working fine for every test cases, but I’m getting wrong answer. Can any one please tell me which test case is failing?
I used the following approach:
Store queries in struct A {int i,j;}
Sort A in increasing order of rows and corresponding decreasing order of columns
count=0
for i=1 to n {
if A[count].i!=i
print m-1
continue;
k=A[count].j;
if k!=m
ans=m-k-1, next=k+1;
else
ans=0, next=-1;
for j=k to 1 {
freq=0;
while(A[count].j==j && A[count].i==i)
count++,freq++;
temp=j+freq;
if(temp>next)
ans=-1;
break;
ans+=(next-temp);
next=temp;
}
print ans;
}
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.