You are not logged in. Please login at www.codechef.com to post your questions!

×

FEB16 Long : SEATL

Complexity : O(Number of Distinct elements in matrix * N)

Concepts : Maps , sets .

While a lot of people might have used O(NM*(N+M)) approach and recieved TLE even for subtask 1. The number of test cases are not specified for each subtask.

Now instead of generating the count matrix , that is the maximum count of each element in that row+coloumn, we would rather do it number by number.Its given that the numbers are between 1 to 10^6 or we can say the maximum number of distinct elements in the matrix can be atmost N*M ,

We will have map data structure to store the coordinates of each element in the matrix. And from this we can find the length of the largest cross,and then print maximum length of cross of all elements.

Here is my working code in python : Solution

asked 15 Feb '16, 17:41

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

edited 29 Feb '16, 15:21

admin's gravatar image

0★admin ♦♦
19.7k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,312

question asked: 15 Feb '16, 17:41

question was seen: 1,034 times

last updated: 29 Feb '16, 15:21