Smart FrogProblem code: G2 |
All submissions for this problem are available.
Bibi the Smart Frog is playing a jumping game on an m x n rectangular board. There is a number written in each cell of the board (Bibi can read these numbers since he is very smart!)
Bibi starts the game by picking any cell on the board and stays there. At each step, Bibi will jump to another cell. He can either:
- Jump to the right to a cell in the same row, provided that the number written in that cell is not smaller than the number written in the current cell.
- Jump downwards to a cell in the same column, provided that the number written in that cell is not greater than the number written in the current cell.
To win the game, Bibi needs to jump through as many cells as possible. But no, he is not so extraordinarily smart that he could compute the optimal way to play the game. After all, he is only a frog, you know! Write a program to help Bibi compute the maximum number of cells that he can jump into.
Input
The first line contains t, the number of test cases (about 10). Each test case has the following form:
- The first line contains two integers m, n (1 <= m, n <= 500).
- Then, m lines follow, each line containing n numbers representing the rectangular board. It is guaranteed that no number exceeds 106.
Each test case is separated by a blank line.
Output
For each test case, print a single number that is the maximum number of cells that Bibi can jump into.
Example
Input: 2 2 3 2 1 1 2 1 1 4 4 6 2 5 2 4 5 3 8 9 7 8 9 9 9 9 5 Output: 3 5 Output details A possible set of cells that Bibi could jump into is marked in bold: 2 1 1 2 1 1 6 2 5 2 4 5 3 8 9 7 8 9 9 9 9 5
| Author: | admin |
| Date Added: | 15-08-2009 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, C, C99 strict, CAML, CLPS, CPP 4.0.0-8, CS2, D, FORT, HASK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, WSPC |
Comments

Fetching successful submissions

Please don't post source code
Please don't post source code here.
Can the admins tell the
Can the admins tell the approximate size of input file ?
It would be really helpful, thank you.
Hi In test case 2nd, only 4
Hi
In test case 2nd, only 4 numbers are highlighted whereas answer is given as 5. Is it correct?
IMO answer should be 4.
There are 5 numbers
There are 5 numbers highlighted in the second case.
What are they? I can see only
What are they?
I can see only 2, 3, 8, 5 only in my browser.
Ok Sorry, I got it
Ok Sorry, I got it
I don't know why am I getting
why it exeeds time limit? I
why it exeeds time limit? I think here it is not because of the algo to solve the problem, but due to i/p o/p operations only. then again i may be wrong. But if printf scanf these functions eat up a large chunk out of execution time, then many novices like me are out. My algo was O(N^3). but still it runs out of time. Is a algo of O(n^3) not optimum enough?
@Mainak Biswas Dude My O(MN
@Mainak Biswas
Dude My O(MN log N) algo gets TLE.
Please do not discuss
Please do not discuss approaches to the problem.
Hi, I am getting NZEC error.
Hi, I am getting NZEC error. I searched all the previous Forums in CodeChef, All the FAQs and Problem pages. I tried some of the suggestions mentioed there, but nothing worked out.Can you please help?
Thanks,
Abhijeet.
You might be having problems
You might be having problems with Input / Output. Are you doing that in accordance with the input specifications ?
Hi Anirudha, I am doing it
Hi Anirudha, I am doing it according to input specifications? I am testing my code using test cases mentioned here & few other test cases generated by me.
I am writing my code in C#2. Are there any specific guidelines for C#? I am reading input from Console & writing output to Console.
Thanks,
Abhijeet.
Please hepl me.. I am sure
Please hepl me.. I am sure there is some issue with IO only as I am writing this in C#. That is why I see very less C# submissions & still very few successful C# submissions.
Thanks,
Abhijeet.
There are other C#2
There are other C#2 submissions which are not getting a NZEC. So, you are probably doing something wrong with the IO or somewhere else.
Hi... i m new to CodechefThe
Hi...
i m new to CodechefThe code which i have submitted is working on my pc
but while submitting to u its saying Compilation error!!!
What could be the problem?
can we use any package in the JDK??
Waiting for the response
Your class should be named as
Your class should be named as Main. You should check out www.codechef.com/help for a sample solution in java.
Hi, previously i was able to
Hi,
previously i was able to see my last submission and able to download it. now that link is missing.
any reason that link has been removed?
This will be fixed in a
This will be fixed in a couple of days.
hi guys, i am new ti code
hi guys, i am new ti code chef.........
actually i wanted know do we generate the no. in the rectangular grid automatically...
if yes then plzz tell me how to do this ??
Take a look at the rand()
Take a look at the rand() function.
can the frog jump to any cell
can the frog jump to any cell to the right which satify the condition or only to the immediate right?
Read the problem statement
Read the problem statement again. This has been explained in it.
my code is working perfectly
my code is working perfectly but i am getting timed out.Other than changing cin &cout to printf & scanf,is there a better way to optimise a c++ code.
whether i have to give input
whether i have to give input for all the test cases once or
one by one for each test case
like for(i=1tonumoftestcases)
{
input
output
}
It makes no difference
It makes no difference whatsoever. All the judge does is have your program write all output to a file then compares that with the correct file.
What will be the result for 1
@santosh There are lots of
@santosh There are lots of ways to optimize c++ code :)
@ravi Re-read the problem
@ravi Re-read the problem statement. Your question has been answered there.
Hi.. in the problem it says
Hi..
in the problem it says to the right...does it mean immediate right or to any of the cells to the right as long as the other constraint is met?
The latter.
The latter.
hi, there is just one thing
hi,
there is just one thing about this smart frog problem that the frog starts the game from any cell he chooses ( as mentioned).. so the output must be initial cell position specific.. all the solutions n the one in the sample i/o depicts the maximum of all the cases.. shouldn it be the other way???