2 952
Subscribers
No data24 hours
-47 days
-1230 days
Posts Archive
2 952
public int maxNonOverlappingSegments(int[] A) {
int n = A.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = hasXORZeroSubseq(A, i, i) ? 1 : 0;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k+1][j]);
}
}
}
return dp[0][n-1];
}
private boolean hasXORZeroSubseq(int[] A, int start, int end) {
// check if there exists a non-empty subsequence of A[start..end] that has a XOR value of 0
}
2 952
def shortest_subarray(colors, C):
n = len(colors)
color_count = [0] * (C+1)
left, right = 0, 0
min_length = float('inf')
count = 0
while right < n:
color_count[colors[right]] += 1
if color_count[colors[right]] == 1:
count += 1
while count == C:
min_length = min(min_length, right - left + 1)
color_count[colors[left]] -= 1
if color_count[colors[left]] == 0:
count -= 1
left += 1
right += 1
if min_length == float('inf'):
return -1
else:
return min_length
Python
2 952
import itertools
def permutation_cost(s):
# Get all possible permutations of the first 20 lowercase English letters
permutations = list(itertools.permutations(s))
# Set initial minimum cost to a large number
min_cost = float('inf')
for perm in permutations:
cost = 0
# Iterate through the permutation
for i in range(len(perm) - 1):
# If the next letter appears before the current letter in the permutation, add 1 to the cost
if perm[i] > perm[i + 1]:
cost += 1
# Update minimum cost if necessary
min_cost = min(min_cost, cost)
return min_cost
s = 'abcdefghijklmnopqrstuvwxyz'[:20]
print(permutation_cost(s))
2 952
def A(s):
return s[::-1]
def B(s):
return ''.join(random.sample(s,len(s)))
def C(s, t):
l1 = list(s)
l2 = list(t)
l3 = [ ]
while l1 and l2:
if random.random()<0.5:
l3.append(l1.pop(0))
else:
l3.append(l2.pop(0))
l3.extend(l1)
l3.extend(l2)
return ''.join(l3)
def solve(m):
m = m[2:-2]
s, t = m.split(',')
if s==t:
return s
S = A(s)
t = B(t)
n = ''
while C(s, t)!=m:
n += random.choice('abcdefghijklmnopqrstuvwxyz')
Python
Telegram:- https://t.me/It_7sem
2 952
given an array A of size N.
You are allowed to choose at most one pair of elements such that distance (defined as the difference of their indices) is at most K and swap them.
Find the smallest lexicographical array possible after
Notes:
An array x is lexicographically smaller than an array y if there exists an index i such that xi <y i1 and x_{j} = y_{j} for all 0 <= j < i . Less formally, at the first index i in which they differ xi < yi
Input Formats@gman
The First-line contains Integers N Ea an integer, N, denoting the line i of the N subsequent lines (where describing A[i]. of elements in A. N) contains an integer
The next line contains an integer, K, denoting the upper bound on distance of index.
Constraints
Here as all the array values are equal swapping will not change the final result,
Here A=[5,4,3,2,11 K we can swap elements at index 0 and index 3 which makes A= [2,4,3,5,1].
Here A=[2,1,1,1,1] K we can swap elements at index 0 and index 3 chat which makes A= [1.1.1.2.11
bool swapped = false;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j <= min(i + K, N - 1); j++) {
if (A[i] > A[j]) {
swap(A[i], A[j]);
swapped = true;
break;
}
}
if (swapped) break;
}
if (!swapped) return A;
else return A;
C++✅
Infosys
Telegram:- https://t.me/It_7sem
