CHEFBM - Editorial

editorial
, , , ,
21

why am i getting wrong answer http://www.codechef.com/viewsolution/3900322

22

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

2 2

3 2

2 2

23

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

1 Like
24

Thank you !

25

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.

26

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

27

I also did it without sorting the input P values. I used dictionary for this. You can have a look at my explanation -
http://discuss.codechef.com/questions/42668/chef-and-strange-matrix.

28

at least you are getting RE for

 100000 100000 1
 1 1
29

Iā€™m getting compilation error on IdeOne - http://ideone.com/xhCPmz

30

Try

100000 100000 1
1 1

on your computerā€¦

31

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

32

WA is coming plz provide the test cases where my code fails http://www.codechef.com/viewsolution/3901670 ā€¦

33

authorā€™s sol is not accessible??

34

Can anyone tell me the complexity of solution in editorial.
I think it should be

O(n*(p[i]+n))

O(n) for each row
then O(p[i]) queries of a row then calcuating cost O(n)

am i ryt?

35

according to me ā€œThe value only changes if the 1st nd lst values are changedā€ā€¦is that right??

36

Will this work for this test caseā€¦?

100000 100000 100000

1 1

1 2

1 3

.

.

.

1 100000

37

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>

here is my solutionā€¦ http://www.codechef.com/viewsolution/3891770

38

http://www.codechef.com/viewsolution/3897839
This seems quite fast still TLE.
Reasons???

39

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:

  1. Store queries in struct A {int i,j;}

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

Thanks.

40

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.