Hogwarts.dropout's blog

need help in d2c question (contest finished)
By Hogwarts.dropout, history, 3 years 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 :(

P.S. solved finally

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

Comments Comments (3)
| Write comment?
»
3 years 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?

→ Reply
»
3 years 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

→ Reply