CHEFBM - Editorial

editorial
, , , ,
6

http://www.codechef.com/viewsolution/3857701
Can someone please check if this is giving right answers on your test cases? It can calculate results even if input of a row changes after changes in other rows, for example

4 4 6

3 2

2 3

3 2

2 4

1 2

32

7

Can the approach be this:
storing count of the incremented index(the coloumn), adding to it the index values. Sort this, if its same as the initial string, ans will be m-1 otherwise -1. For eg.

4 4 6
2 2
3 2
3 2
4 3
4 4
4 3

then for the third row, count(this array will be 1-indexed) will be 0 2 0 0, adding the index values to it, it will be 1 4 3 4. Now if i’ll sort this, i’ll not get the same array and hence answer should be -1. I implemented this here: LBmHGD - Online C++ Compiler & Debugging Tool - Ideone.com and its most obvious to give TLE. BUt is there any way I can optimize this??

8

Why does this ans give TLE:
http://www.codechef.com/viewsolution/3842031
It works fine on my computer.Please help.

9

Where shall i get the input file and output file?

10

Why does this ans give WA: CodeChef: Practical coding for everyone It works fine on my computer.Please help.

11

http://www.codechef.com/viewsolution/3897087
its working fine for every test cases…but getting wrong answer…can any one please help

12

why am i getting wrong answer CodeChef: Practical coding for everyone

13

WA is coming plz provide the test cases where my code fails CodeChef: Practical coding for everyone …

14

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?

15

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… CodeChef: Practical coding for everyone

16

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

17

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.

18

I really hate to do this,but i can’t figure out the error in this:
http://www.codechef.com/viewsolution/3902790
if anyone can provide any corner test cases.Thanks.

19

http://www.codechef.com/viewsolution/3903340
my code is working fine on my computer.but here i am getting wrong answer

20

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.

Please help me to figure it out.

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