CHEFBM - Editorial

editorial
, , , ,
21

Can someone please provide a test case for which my answer gives WA?
Here’s my solution. :CodeChef: Practical coding for everyone

22

Can anybody spot where am i going wrong?

http://www.codechef.com/viewsolution/3854787

23

hey its working for test cases on my pc why it is showing Runtime error on here please Help!!
www.codechef.com/viewsolution/3932903

24

For such a query we also store (j-1,0) and (j+1,0), because these two indexes are also effected."

Can anyone expand on this line? Where do we store that?

25

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;
}

26

for input

1 4 5
1 3
1 2
1 2
1 1
1 1

it returns -1

initial matrix

   *
  **
 ***
****

after additions

 ***
****
****
****

so the result should be 1…

2 Likes
27

@ashish424 see this…pLUZzO - Online C99 Compiler & Debugging Tool - Ideone.com …u r printing extra numbers!!!

2 Likes
28

try this case…

4 1 1
1 1

ans should be:-

0
0
0
0

urs is…

1
0
0
0
29

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.

30

i corrected that …but it is still showing wrong answer
http://www.codechef.com/viewsolution/3900322

31

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.

32

@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.

7 Likes
33

You mean test cases? Those are not available…

34

I did that way and got AC also. But i was just thinking if some way of the above kind(using sort) exists.

35

Will your program work if increments were not in order?? like

2 2

3 2

2 2

36

I m storing the input index values (i,j) in a vector and sorting them first as per i.

1 Like
37

Thank you !

38

I used sorting operation and TLE error, with running time of 1.01.
Then I messed up and used Java, runnimg time 7.3 sec.

39

I still didn’t get your sort and compare logic however. If only last element is incremented, how would you compare??

40

I also did it without sorting the input P values. I used dictionary for this. You can have a look at my explanation -
Chef and Strange Matrix - general - CodeChef Discuss.