Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### StrawberryInsha2k's blog

By StrawberryInsha2k, history, 2 months ago, ,

I have been seeing a lot of questions like converting a number X to Y by following sets of operations.(add, subtract, multiply)Given a initial number x and two operations which are given below: Multiply number by 2. Add 1 to the number. i wonder if it can be solved using dp.

• +6

By StrawberryInsha2k, history, 2 months ago, ,

ll dp[27][27] = {0}, cnt[27] ={0};
ll ans = 0;
for (ll i = 0; i < str.length(); ++i) {
for (ll j = 0; j < 26; ++j)
dp[str[i] - 'a'][j] += cnt[j]; //what are we calculating using this dp and how
cnt[str[i] - 'a']++;
}

for (ll i = 0; i < 26; ++i) {
ans = max(ans, cnt[i]);
for (ll j = 0; j < 26; ++j)
ans = max(ans, dp[i][j]);
}

pf1(ans);

• +5

By StrawberryInsha2k, history, 2 months ago, ,

Hello everyone, can you please help me in this problem? If I am given an array of n integers of k distinct elements. Then how do I compute the maximum subarray which has exactly f distinct elements (f< k). (like of all the subarray which has f distinct elements among them the maximum length ) Example question: (in this problem f==k-1) https://www.codechef.com/problems/NOTALLFL

• +3

By StrawberryInsha2k, history, 2 months ago, ,

Hello everyone, can you please help me in this problem? If I am given an array of n integers of k distinct elements. Then how do I compute the maximum subsequence which has exactly f distinct elements (f< k). (like of all the subsequence which has f distinct elements among them the maximum length ) Example question: (in this problem f==k-1) https://www.codechef.com/problems/NOTALLFL

• 0

By StrawberryInsha2k, history, 2 months ago, ,

Hello dear friends! Just wanted to share few things with you all. This is the worst question on Codeforces ever (https://codeforces.com/problemset/problem/1341/C). I haven't seen a more complicated question than this. Seriously one would rather leave competetive programming than sit and solve this question. Codeforces should delete this question and blacklist the person who created this. Upvote to get this man suspended @Aleks5d

• -23

By StrawberryInsha2k, history, 2 months ago, ,

https://www.codechef.com/problems/PSHTRG Can you please guide me how i answer for the second query in this question?

• 0

By StrawberryInsha2k, history, 3 months ago, ,

• 0

By StrawberryInsha2k, history, 3 months ago, ,

I have studied about finding LIS (longest increasing subsequence) How do I extend that knowledge to find LIS where gcd(xi, xi+1) > 1? Please help me here is the link to the question https://codeforces.com/problemset/problem/264/B

• +7

By StrawberryInsha2k, history, 3 months ago, ,

How can I implement this question using binary search? https://codeforces.com/contest/1177/problem/B

• 0

By StrawberryInsha2k, history, 3 months ago, ,

I could do this question by barely hit and trial like i first computed prefix sum then start taking terms which are at i-k position but i still couldn't understand thy dynamic programming concept behind it. please just explain this to me i will be very much thankful to you https://codeforces.com/contest/1253/problem/C

• +1

By StrawberryInsha2k, history, 3 months ago, ,

Hello everyone! How can I do this question using segment trees? what type of array to create? https://codeforces.com/problemset/problem/1234/D

• 0

By StrawberryInsha2k, history, 3 months ago, ,

if x and y are two numbers ( >=1 && <= 1e9 ) how do i find all the factors of x*y in 1 second? Please help sample input : 158260522 200224287

• -17

By StrawberryInsha2k, history, 3 months ago, ,

https://codeforces.com/problemset/problem/1030/D Hello everyone, hope you all are fine. Talking with reference to this question. First of all we need to ensure that 2*m*n is divisible by k for integral points. Secondly , if besides origin two other points were to be a,0 and 0,b so a*b = 2*n*m/k then can we do it like we list down all the factors of 2*n*m/k let those be f1, f2 , ....... ,fn and then taking the leftmost and rightmost then the second-leftmost and second-rightmost and checking if either of left or right is less than <= n and the other is less than <= m. Would this work?

• 0

By StrawberryInsha2k, history, 3 months ago, ,

In this problem I don't know why we are taking remainder with three. Don't we have to just consider all the segments of length (k+1) only and determine the winner? https://codeforces.com/contest/1194/problem/D

• -5

By StrawberryInsha2k, history, 3 months ago, ,

Can anyone tell me how I prove this dp relation of selections of j object from i dp[i][j] = dp[i-1][j-1] + dp[i-1][j] if anyone can explain me the two states in the right hand side of the eqn it would be great. please explain the transitions and states in this problem.

• +8

By StrawberryInsha2k, history, 3 months ago, ,

Hello everyone, i just wanted to know why this solution cannot be solved using greedy approach https://codeforces.com/contest/1005/submission/76980469

• -5

By StrawberryInsha2k, history, 3 months ago, ,

In a weighted tree, how to find for some node (u) the distance to another node (v) (answering Q queries effeiciently)? Constraints N <=10^3, Queries <=10^3

• -3

By StrawberryInsha2k, history, 3 months ago, ,

Hello everyone, I have been having a lot of problem in solving this question and I have been looking for any help.

https://codeforces.com/contest/505/problem/C This is the question. Can you please help me find the recurrence relation? If you will read the editorial you will find that they have used relation: dp [ i ][ j ] = (the number of the gems on island i ) + max( dp [ i + j — 1][ j — 1], dp [i + j ][ j ], dp [ i + j + 1][ j + 1]), if i < m , j ≥ 2 but in recurrence relation we used to find out the previous state on (right hand side of the equation because that is how we solve sub-problems ) but here they have related dp[i][j] (current state ) with the state that will be achieved afterwards in the process that is dp[i+j+1][j+1], dp[i+j][j] and dp[i+j-1][j-1]. How are we solving sub-problems here? Can you please help me?

• +2

By StrawberryInsha2k, history, 3 months ago, ,

Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number M (1, 2 or 3) is fixed.]

T N C M

Sample Input:

3 5 3 1 5 2 2 6 2 3

Sample Output:

25 10 10

I defined dp[i][j] as the number of ways of distributing i coins to j charities. Then, a recursion relation should be derived in each of these three cases:

So for 1 at least 1 coin dp[i][j]=j∗dp[i−1][j]+dp[i−1][j−1]

I am unable to figure out the recurrence relation for at least 2 coins and at least 3 coins. Can you please explain the other two recurrence relation by clearly defining each states and transitions. I would be highly obliged to you and much of time will be saved.

Thank You

• 0

By StrawberryInsha2k, history, 3 months ago, ,

I have this programming prompt where I have been asked to find the number of permutations of a 32 coin toss sequence that do not have three consecutive heads in a row.

I have been tasked to find this with dynamic programming and I am having a hell of a time trying to figure out the recursive algorithm.

I have tried a two variable approach where I try and keep track of whether the previous two flips were heads or tails and then incrementing based upon that. I have also tried breaking it into sub-problems where I start with a singular toss and then work my way up the full 32 tosses.

And I'm having a hard time visualizing how to approach this and figuring out how to keep track of everything as the algorithm commences.

Any help would be greatly appreciated.

• +3

By StrawberryInsha2k, history, 3 months ago, ,

Alice plays the following game, loosely based on the card game "21".

Alice starts with 0 points, and draws numbers while she has less than K points. During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets K or more points. What is the probability that she has N or less points?

Input: N = 6, K = 1, W = 10 Output: 0.60000 Explanation: Alice gets a single card, then stops. In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Can any one please explain this problem?