eleganc's blog

By eleganc, history, 9 months ago, In English

Given an array of length n. The task is to make the sum of all the subarrays of length greater than two positive. To do this, you can replace any element with any integer x where -10^18 < x < 10^18. Find the minimum number of replacements needed to make the array positive.

Constraints: -10^9 < arr[i] < 10^9 and n < 10^5

Example:

Test Case 1: Arr = [-80 100 -80] Ans = 1

Test Case 2: Arr = [-10 19 -10 2] Ans = 1 (by making arr[2] = 10^18)

Full text and comments »

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

By eleganc, history, 14 months ago, In English

Given a matrix consisting of characters of the type:

  1. Single digits
  2. '-'
  3. '+'

Find the maximum value which can be evaluated using a valid expression in the matrix.

A valid expression is defined as a contiguous array:

  1. Starts from any cell with a numeric value and is either in the left to right direction or in top to bottom direction.
  2. The final expression doesn't contain any consecutive operators. Eg. '3' '+' '-' '1' is not allowed.

Example TC:

n = 7, m = 5

matrix =

'1' '+' '3' '-' '2'

'-' '2' '+' '3' '+'

'1' '-' '4' '-' '4'

'+' '2' '-' '7' '+'

'2' '+' '5' '+' '9'

'+' '1' '+' '8' '-'

'2' '-' '0' '-' '2'

Answer: 2 + 5 + 9 = 16 evaluates to the maximum value. Hence the answer is 16.

Caution: We may have a matrix like ['4' '4' '5' '-' '-' '5' '1'], in this case we are free to take 445 or 4, 5, 5, or 44 to 45

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By eleganc, history, 18 months ago, In English

Hi, I recently faced this problem in an OA. Any approaches to solve this?

An array consists of N elements. We want to minimize the absolute difference between adjacent elements of the array. We can change any integer to any other integer however at most K changes are allowed. If n <= 1 return 0.

Here is the exact problem link: https://www.codechef.com/CRK32020/problems/KEVIN?tab=statement There is some hint toward binary search, but I don't precisely infer how it is to be applied.

Constraints: 1 ≤ k ≤ n ≤ 2000 -1e9 ≤ Ai ≤ 1e9

Eg. N = 6, K = 3 Arr = [1 2 3 7 8 9] Here Arr can be transformed to [1 2 3 4 5 6] in 3 changes. And the answer becomes 1.

Full text and comments »

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

By eleganc, history, 18 months ago, In English

Hi, I faced this question in a recent mock assessment. I cannot think of any approach to solve this. Ideas are welcomed. Problem: A new method has to be derived for decrypting secret codes. THere is a secret array arr of length n, along with a 2D array query with dimension m*2, where each row denotes a pair (L, R) which denotes the sum arr[L] + arr[L+1] + .... + arr[R]. The goal is to determine all the indices of arr whose value can be identified.

Eg. n = 4 query = [[1, 3], [1, 2], [4, 4]]

First query gives the value of arr[1] + arr[2] + arr[3]. The second query gives the value of arr[1]+ arr[2]. Third query gives the value of arr[4] directly.

Using the above only index 3 and 4 can be determined (1 based indexing). So ans = [3, 4].

Constraints: 1 <= n <= 1e5; 1 <= m <= 1e5; 1 <= l <= r <= n

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it