Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

### FameOfTheLegends's blog

By FameOfTheLegends, 6 weeks ago,

Can anybody help in this uber coding question.

There is a meeting scheduled in an office that lasts for time t and starts at time 0. In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. Note that the duration of the presentation can’t be changed. You can only change the start and end time. Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.

Constraints :-

1<=t<=1, 000, 000, 000 (t is the duration)

0<=k<=n

1<=n<=100, 000

e[i]<=s[i+1], 0<=i <n-1

s[i] < e[i] for 0<=i<=n-1

Can't none of you motherf***ers do this, thereby downvoting?

• -37

By FameOfTheLegends, 6 weeks ago,

When is result going to be declared. If our team rank is around 600 and there are around 10 teams in our college above us , then will we quality?

• +6

By FameOfTheLegends, 2 months ago,

I was doing this Problem on codeforces. It was a dynamic programming question and I am fairly new to dynamic programming.

I wrote a code whose main part is below

n,m,b,mod = li()
a = li()
dp = [[0 for i in range(b+1)] for j in range(m+1)]
dp[0][0]=1
for i in range(n):
for j in range(1,m+1):
for k in range(b+1):
if k-a[i]>=0:
dp[j][k]+=dp[j-1][k-a[i]]
ans = 0
for j in range(b+1):
ans+= dp[m][j]
print(ans%mod)


This was giving the correct output. But when I move the first loop to the end, then it gives the wrong answer.

for j in range(1,m+1):
for k in range(b+1):
for i in range(n):
if k-a[i]>=0:
dp[j][k]+=dp[j-1][k-a[i]]


The above code is giving incorrect output. Can anybody help me in understanding why does the loop orientation matters in this case.

• +1

By FameOfTheLegends, history, 2 months ago,

You are given an array A of N non negative integers. There are K empty slots from 1 to K. You have to arrange these N numbers into K slots( 2*K> =N). Each slot can contain at most two numbers filled into it. After all the integers have been placed into these slots, find the sum of bitwise AND of all the numbers with their respective slot numbers

Task: Determine the maximum possible sum

Note: Some slots may remain empty

Example A = [1,3,10,20,7,1] N = 5 K = 10 answer = 25

I did brute force and some test case passed.

How to do this question?

• +12

By FameOfTheLegends, history, 2 months ago,

given an array with n elements, and Q queries consisting of an integer find whether there exists an element in the array such that it's bitwise and is zero

1<=n<10^5 , 1<=q<10^5.

Can anyone tell how to do this question.

• +8

By FameOfTheLegends, history, 2 months ago,

find minimum number of integers, (where each such integer>=2) that divide all array elements. For example, if the array is [2,4,6,8,10] then the answer is 1 (because 2 divides all array elements). Another example, if the array is [2,3,4,9] then the answer is 2 (because we need at least 2 different numbers, 2 and 3, that satisfy the conditions).

Constraints: N<=10^3

Can someone help, I am not able to solve this problem.

• -15

By FameOfTheLegends, 2 months ago,

Question 1 — N boxes are Arrranged in a line. Each box is colored either with white or black. You can select any number of boxes from the starting and put it behind the last box in the same sequence as it was placed initially. you can perform this operation atmost once. For example string s="wbbb" . In one operation you can select "wb" and from the start and put it behind the last box "b".

Note: you cannot select all the n boxes.

You are required to find the minimum number of boxes whose colors must be reversed so that all the boxes in the sequence are of an alternate color, that is any two adjacent boxes are of different colors.

Input :  5
wwwwwbbww
wwwb
bwww
wwww
bbbbb

Output :
3
1
1
2
2


I was thinking of brute forcing the solution, that is doing operation for each length and then calculating for that configuration. Can anyobody tell the correct approach

• +7

By FameOfTheLegends, history, 2 months ago,

So I was doing this problem on leetcode.

I was doing in python. This is my code

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
ans = [];cur = []
def rec(index):
if index==len(s):
ans.append(''.join((cur[:])).strip())
return
for i in range(index,len(s)):
if s[index:i+1] in wordDict:
cur.append(" ")
cur.append(s[index:i+1])
rec(i+1)
cur.pop(-1)
cur.pop(-1)
rec(0)
return ans


On the for loop,

if s[index:i+1] in wordDict:


This creates a copy of string s from the index till i+1 and hence takes O(n) time. If i use string concatenation instead of this, the time complexity will be O(n^2) as strings are immutable in python . I could'nt use list as keys cannot be mutable in dictonary. So what should I do to make the for loop linear time complexity? Is there any way to make the string concatenation linear in python?