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

×

icpc kolkata solution

Hey guys, Can anyone give an approach or link their soln for 2nd problem of icpc kolkata online round 'Finding Hardest Sum Value' ? https://www.codechef.com/ACMKOL15/problems/KOL15B

asked 03 Nov '15, 23:09

sanket407's gravatar image

4★sanket407
4849
accept rate: 10%


Perform maximum sum subarray DP for each of the N*M points in all 4 directions. It can be done in O(4 * N * M) time. Now, iterate through each point in matrix, fixing it as meeting point of all 4 persons. Each point's optimal value can be found in O(1) time, using the already computed values. Find the best point and report its value

link

answered 04 Nov '15, 00:10

rvns03's gravatar image

4★rvns03
111
accept rate: 0%

Thanks.. Still new gotta learn more dp algos Btw that O(4 * N * M) time for computing subarrays for all n*m points?? Each direction max subarray dp will take O(N) time too right?? So should,nt it be O(4 * N * N * M )

(04 Nov '15, 21:00) sanket4074★
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,110
×99
×39

question asked: 03 Nov '15, 23:09

question was seen: 2,103 times

last updated: 04 Nov '15, 21:00