CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • All Contests
    • June Long 2012
    • May Cook-Off
    • May Long 2012
  • DISCUSS
    • Forums
    • Blog
    • Wiki
    • Facebook
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Tutorials
    • Long Contest Ranks
    • Short Contest Ranks
    • Event Calendar
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » September 2009 (Contest VIII) » Smart Frog

Smart Frog

Problem code: G2

  • All Submissions

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


  • Submit

Comments

  • Login or Register to post a comment.

Please don't post source code

admin @ 1 Sep 2009 04:59 PM

Please don't post source code here.

Can the admins tell the

pr0ton @ 2 Sep 2009 11:54 AM

Can the admins tell the approximate size of input file ?

It would be really helpful, thank you.

Hi In test case 2nd, only 4

codesnooker @ 2 Sep 2009 01:13 PM

Hi

In test case 2nd, only 4 numbers are highlighted whereas answer is given as 5. Is it correct?

IMO answer should be 4.

 

6  2
4 5 3 8
9 7 8 9
9 9 9 5

 

There are 5 numbers

admin @ 2 Sep 2009 01:57 PM

There are 5 numbers highlighted in the second case.

What are they? I can see only

codesnooker @ 2 Sep 2009 02:09 PM

What are they?

I can see only 2, 3, 8, 5 only in my browser.

Ok Sorry,  I got it

codesnooker @ 2 Sep 2009 02:13 PM

Ok Sorry,  I got it

I don't know why am I getting

capt @ 2 Sep 2009 10:31 PM
I don't know why am I getting runtime error! I read the help section , but am still unable to understand the cause. @Admin Can you tell me about the possible causes... thanks in advance for the help !

why it exeeds time limit? I

mainak @ 2 Sep 2009 11:13 PM

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

madhav_iiith @ 2 Sep 2009 11:53 PM

@Mainak Biswas

 

Dude My O(MN log N) algo gets TLE.

Please do not discuss

admin @ 3 Sep 2009 03:11 AM

Please do not discuss approaches to the problem.

Hi, I am getting NZEC error.

Aby @ 3 Sep 2009 04:36 AM

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

admin @ 3 Sep 2009 01:14 PM

You might be having problems with Input / Output. Are you doing that in accordance with the input specifications ?

  Hi Anirudha, I am doing it

Aby @ 3 Sep 2009 02:51 PM

 

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

Aby @ 3 Sep 2009 04:19 PM

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

admin @ 3 Sep 2009 04:43 PM

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

Kiran Kumar Bali @ 4 Sep 2009 01:00 PM

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

admin @ 4 Sep 2009 01:55 PM

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

guptaanil2k1 @ 4 Sep 2009 09:42 PM

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

admin @ 5 Sep 2009 02:28 PM

This will be fixed in a couple of days.

 hi guys, i am new ti code

jasra @ 5 Sep 2009 03:47 PM

 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()

admin @ 5 Sep 2009 05:26 PM

Take a look at the rand() function.

can the frog jump to any cell

helloworld @ 5 Sep 2009 07:38 PM

can the frog jump to any cell to the right which satify the condition or only to the immediate right?

Read the problem statement

admin @ 5 Sep 2009 07:58 PM

Read the problem statement again. This has been explained in it.

my code is working perfectly

TheSadReaper @ 6 Sep 2009 10:37 PM

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

dinesh372 @ 7 Sep 2009 10:22 AM

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

triplem @ 7 Sep 2009 10:31 AM

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

ravi_m @ 7 Sep 2009 02:03 PM
What will be the result for 1 x 1 board? 0 or 1?

@santosh There are lots of

admin @ 7 Sep 2009 02:19 PM

@santosh There are lots of ways to optimize c++ code :)

@ravi Re-read the problem

admin @ 7 Sep 2009 02:27 PM

@ravi Re-read the problem statement. Your question has been answered there.

Hi.. in the problem it says

switchcase @ 7 Sep 2009 11:29 PM

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.

admin @ 7 Sep 2009 11:37 PM

The latter.

 hi, there is just one thing

Baba @ 9 Sep 2009 10:14 PM

 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???

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

Programming Competition Fetching successful submissions
Directi Go for Gold
CodeChef is a global programming communityCodeChef hosts online programming competitions
CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com