CHEFBM - Editorial

editorial
, , , ,
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.

41

at least you are getting RE for

 100000 100000 1
 1 1
42

I’m getting compilation error on IdeOne - xhCPmz - Online C# Compiler & Debugging Tool - Ideone.com

43

Try

100000 100000 1
1 1

on your computer…

44

but on VS2010 it is working fine. also on codechef, WA is coming, Not the compilation error

45

author’s sol is not accessible??

46

according to me “The value only changes if the 1st nd lst values are changed”…is that right??

47

Will this work for this test case…?

100000 100000 100000

1 1

1 2

1 3

.

.

.

1 100000

48

Its easy using map etc without sort. @miiitd7042075 My sort logic is like taking one count array[m] where the array index will be the coloumn value, i’ll increment each time as per the input.
i.e if in input (taking m=4) for row 2, colomn 3(incremented twice) and 4 incrmented once i.e. array for row 2 will be 0201 (array is 1 indexed). Add the index values to it i.e. array is now 1435(doing this way 0+1, 2+2, 3+0, 4+1). This array finaly should be in sorted order for ans to be m-1 else ans=-1.

49

remove

printf("input:");
printf("output:");

at least

1 Like
50

Limits for M are not clear, should not it be M>=2 instead of M>=1, How could M == 1?

51

Why can’t we just store j and j+1 on query (i,j), because j-1 is already in order? I am storing in sorted map to check if j < j+1

Can somebody please tell me what is wrong with this approach

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

52

@darkshadows (or anyone else) sir, please elaborate how when a[i][j] is incremented j-1th index is also affected. I feel that the difference a[i][j]-a[i][j-1] may change, but the overall sum doesn’t change and it would be a[i][m]-a[i][0]. Also jth element is always greater than j-1th element for that particular increment. Hence the only index that is affected should be j+1.

53

found that j-1th element is not affected. Reason is clearly mentioned in the code. AC code can be viewed here.

54

@imdeepakg: it is sufficient to check j and j+1 on query (i,j). Here is my well commented accepted code link. As far as your approach is concerned I am not good in JAVA and not able to understand the code. Hope that my code may help you debug your code.

55

@birazdeli: check this well commented code. Hope this helps. Also, it is sufficient to check j+1 element. j-1 element is not required when j element is modified.