CHFDORA - Editorial

Always love @vijju123’s editorials. Especially the related problems part and the extra parts that he includes!

2 Likes

If you write the second statement in your code i.e. while(A[i]%2==0 and i < n) ++i;
As Logical AND (\&\&) is a sequence point (Sequence point is a point in your instruction which makes sure that all the instructions written before it must be evaluated first and any side-effect must be complete) the expression A[i] % 2 == 0 will be evaluated first.
Now if the value of i is \geq n then it is the case of Segmentation Fault and your program will generate SIGSEGV Error.

Thanks for Reading
Peace :v:

I am sure if my solution is fast enough than other optimized solutions will be much more faster.
I think you can try increasing N*M to 5*10^5 or 10^6. Not sure though.

yeah i did the same thing and still got tle can someone explain why?

@vijju123 when can we expect the editorials of the challenge problems? and also of Army of me? Eagerly waiting for the editorial of Army of me :blush::blush::blush:

Very Good editorial!

1 Like

what does this line mean…
given constraints are:

  • 1≤T≤1001≤T≤100
  • 1≤N,M1≤N,M
  • N⋅M≤105N⋅M≤105
  • 1≤Ai,j≤1061≤Ai,j≤106 for each valid i,ji,j
  • the sum of N⋅MN⋅M over all test cases does not exceed 3⋅105

Why were 100 points awarded for the Brute force implementation? I feel that 100 pts should have been awarded for the O(N*M) approach using Manacher’s algorithm.

2 Likes

Great editorial! @vijju123:smiley:

1 Like

@doga5743
https://www.codechef.com/viewsolution/29015248
line 37 break

https://www.codechef.com/viewsolution/28964203

can some one tell why i am getiing TLE for three test cases for my solution and all other test cases are okay

Why I am getting time limit exceeded for the last two test cases. My python solution - Here.

can you please explain why min(N,M)<350 ?
thanks!

Because if min(n, m) > 350 then the condition n * m < 10^5 would not hold because 350 * 350 > 10 ^ 5 .

Read the editorial further and know more. I hope you know that clicking on those Arrow like things will reveal more content.

1 Like

https://www.codechef.com/viewsolution/29115055
I have implemented the same logic, still I’m getting WA in some testcases.
Please help

This is how I did in Java

  public static void main (String[]args) throws java.lang.Exception
  {
    // your code goes here
    Reader in = new Reader();
    int t = in.nextInt ();
    for (int i = 0; i < t; i++)
      {
        int r=in.nextInt();
        int c=in.nextInt();
        int[][] a=new int[r][c];
        for (int j=0;j<r;j++)
        {
            for (int k=0;k<c;k++)
            {
                a[j][k]=in.nextInt();
            }
        }
        int count=r*c;
        int ud=0;
        int lr=0;
        for (int j=1;j<r-1;j++)
        {
          if (j<r-j-1)
          {
               ud=j;
          }
          else
          {
               ud=r-j-1;
          }
          
            for (int k=1;k<c-1;k++)
            {
                if (k<c-k-1)
                {
                    lr=k;
                }
                else
                {
                    lr=c-k-1;
                }
                
                for (int q=1;q<=ud && q<=lr; q++)
                {
                    
                    
                    if (a[j][k-q]==a[j][k+q] && a[j-q][k]==a[j+q][k])
                    {
                        count++;
                    }
                    else break;
                }
            }
        }
        System.out.println(count);
      }

I just remembered, my nm(n+m) program passed with 0.03 seconds, just by auto coding the answer when an entire row is the same.
https://www.codechef.com/viewsolution/28704770

DONT PASTE CODE HERE