×

# icpc kolkata solution

 0 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 484●9 accept rate: 10%

 0 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 answered 04 Nov '15, 00:10 4★rvns03 11●1 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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