Maybe this can help: https://codeforces.net/blog/entry/47516

You can follow my DP lists to practice Dynamic programming.

hack this submission if you can :) 56132099

The contest is running with no problems showing, i guess they still couldn't decide ;-)

If you solve all problems and take first place, that might be possible

I hope to become red after this round!

Why do u think so?

The creators of the contests have sufficient intelligence to differentiate problems of Div 2 from Div 3. Trust them.

I wish you good luck!

EDIT: when you get downvotes for cheering someone on xD

1.it won't be

And Nastya.

Also Tanya, Alice, and Bob.

It becomes zero in some questions(B) as they have to remove then xd

Really!?

Handle or Name ?

There they are!

invisibleforces !!!

Same here

EDIT : fixed

you just did

I like your handle.

seems like, it's gonna be an unrated contest

wait first 15 minutes

Sir, I share this concern.

< 10 lines in python for me

store array containing frequency of i in arr[i]. sort all values in reverse order, now for all elements after 1st element in array, its value is min(arr[i],arr[i-1]-1). Answer is sum of positive values in array.

Thanks, I think it'd be a bit easier to read if you posted this as a blog and if you have the implemented code, to share it.

Thanks for your effort. I looked into it. I found that explanation of Q.F was difficult for me to understand ( or maybe because i have used another method .) Can you tell me in short what you did ?

My method : I found out during the contest that if there is a solution which doesn't have max element (let's say m) . Then the only better option can be m/2 + m/3 + m/5.

getting tle in test case 6 problem g https://codeforces.net/contest/1183/submission/56137010

Edit : This is for Problem H.

Consider dp[i][j] -> number of distinct subsequences ending at i, of length j. Then,

Where prev[i][c] is the maximal index before i, that has value c.

it takes me more than 40 min to understand :(

You can consider the formula for how much additional charge you will need, where "out" is the number of days you don't charge: neededCharge = (out*a) + ((n — out)*b) — k + 1 Specifically, we need neededCharge to be less than or equal to 0, so we can set out based on that. Simplify to get out <= (k-n*b-1)/(a-b). So, set out = floor((k-n*b-1)/(a-b)) Then, if out is less than 0, your answer is -1. Otherwise, your answer is min(n, out).

dynamic programming dp [i] [j], the number of different strings of length i ending in j letter

In Division 3 rounds, hacking occurs for twelve hours after the contest. Ratings will update after the hacking phase and system tests finish.

The Hacking phase in Div.3 comes after the contest like educational round

The rating will come up after finish the Hacking phase

No its not you wold definitely get TLE or WA for that the solution . just consider a 100 letter string with same characters and k=99. you can use dynamic programming to solve it.

Hahaha, trying all possibilities? Did you read "substring" instead of "subsequence"?

Just as a side note, total possible ( without removing repetitions ) number of subsequences is $$$2^N$$$ where $$$N$$$ is the length of the given string.

Потому что если мы играем 2 раза тогда (20-7*2=6, 6/3=2 ,2+2<5) мы не можем закончить 5 раундов.

Yes

I remember once BinaryBoy did this with him self :|

Who are you LE_ROI? :D :D :D If you can prove this I will give you everything in this world. Please don't wast your time to see other code. Nijher chorkai tel dao. Copy past codeforce onek valo dhorte pare. I don't know who is sraman915. Hey Sraman are you know me? LE_ROI are you man or woman? :D :D :D

The question is all about finding the distinct subsequences of length K. after that one can easily figure out the solution. I googled it and found something relevant which I have also mentioned in my code.

I don't know _Md_AL_AMIN_ but after seeing his solution I think he has also used the same thing but he forgets to mention in his code.

It seems he has copy and paste code from Internet source. It is clear from inconsistent indenting. Many people have done this. I don't believe he has cheated.

Have a look at my submissions I got plenty of TLE's for the same reason on D. When you declare your array globally of size 2e5 and when there are 2e5 queries it will become O(10^10) because you are initially array of size 2e5 everytime. That's why array should be dynamic to take advantage of the fact that the sum of n over all queries is <2e5.

It is because you are generating a testcase with 200000 queries where n=200000. However, in the problem statement, it is mentioned that "It is guaranteed that the sum of n over all queries does not exceed 2*10^5 ".

Right now, hacking phase is going on which will continue for 12 hours. So, ratings will be changed later after the hacking phase ends.

Sure. Sub-problem : Count number of distinct subsequence in a string ? Sol — I'll use 1 based indexing. Let DP[i] be the number of distinct subsequnces ending with character s[i]. Then if character s[i] did not occured before then we can chain it to all distinct subsequence occured before this position i.e. we can freely choose second last position in our subsequence DP[i] = sum of all DP[j] for j < i. If s[i] occured before then we don't need to count second last position before last occurence of s[i] because they are already calculated DP[i] = sum of DP[j] for prev[i] <= j < i. where prev[i] = last occurence of s[i]. Base case is empty subsequence. DP[0] = 1.

Original-Problem — Just add length state in DP. DP[i][j] = Number of distinct subsequence having last character s[i] and is of length j . Base case DP[0][0] = 1.

This solution is O(n^3) but can be optimised to O(n^2) by calculating prefix sum DP for each length layer.

While finding best cost in problem : Start taking subsequence with maximum length.

In B we have a sure move to maximize the common price, if that is not possible there can't be a common price.

After sorting the prices, if we increase the smallest price by k(maximum possible increase), and if the product with largest price is less than a[0] + 2*k, then there exist an increment or decrement of a value less than k to reach that maximum possible price. But if the product with largest price is greater than a[0] + 2*k then there is no such price that the smallest and largest initial price product can have in common.

I think your solution is correct. After sorting the array, to print (a[0]+k) as answer, we need to just check if (a[n-1]-k)<=(a[0]+k) or (a[n-1]-a[0])<=2*k. Instead of checking only for a[n-1] (or max element), you are checking for all elements which is not necessary. So it should pass system tests.