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
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
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
CodeChef: Practical coding for everyone
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
Merge the two while loops to remove tle, set up and side initially as 1 and loop from i=0 to i<n to get ac
thank you so much bro
if first condition is false then it dont bother 2nd one , if first condition is true then it checks for second
I tried to find the max possible range offset first and then began checking for palindromes, but it gives WA for most of the test cases.
Code: CodeChef: Practical coding for everyone
Thanks!
1 Like
I got it why it doesn’t work
consider the example
5 5
1 1 1 8 1
1 8 1 8 1
1 1 1 8 1
1 1 1 8 1
1 1 1 8 1
Observe for (2,2) for my solution:
According to my solution - I am trying to get a square first and then compare element wise (without considering the continuity)
1
1
1 1 1 8 1
1
1
my algorithm will compare (2,0) and (2,4) - without considering that (2,1) != (2,3) hence there is no palindrome here, but it mistakenly adds this entry as well.
-for anyone who commits the same mistake
1 Like