Iwillcomebackstronger's blog

By Iwillcomebackstronger, history, 4 weeks ago, In English

given a 2d(N*N) matrix...N<=5*10^3 ...maximize F(a,b,c,d)=A[a][b]+A[c][d] -|a-c|-|b-d| ...0<=A[i][j]<=10^9. output max value of F for (a,b) not equal to (c,d) i.e. 2 distinct points. i was only able to think of bruteforce hence TLEd :(

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please help in finding the correct approach :D

»
4 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Here is another problem from the same contest which I am unable to figure out:

X and Y are playing a game on a given array with n elements. X removes an element from the array. Y removes the element at the middle position of the remaining array. This game continues till no elements remain. Maximize the elements picked by X. And output the sum of the elements of X.

Constraints:

  • 1 <= n <= 4*10^5
  • 1 <= a[i] <=1e9

Input Format

n followed by n spaced integers denoting the n elements of the given array.

Output Format

A single number denoting the maximum sum of elements X can get to

Sample Input 1:

4

1 2 3 4

Sample Output 1:

7

Sample Input 2:

4

5 15 10 5

Sample Output 2:

20

How would you go about solving this?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

One of my friend asked me this problem yesterday . Here is a link to my solution to this problem .
Public Test Cases are passing .. And I'm sure it will pass main tests .

PS: Tell me if you want me to explain my approach

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Iwillcomebackstronger (previous revision, new revision, compare).