I thought you stopped leaving such comments because of fear to be banned

Бывает) Благодарю, поправил.

Dude, with easy tasks everyone will solve them, so it become a speed contest, which is not "educational" and doesn't make sense, cause we are here to learn and have new ideas ...

I want hard tasks so others can get low rating!

if you want high rating you must have good rank the rating depends on rank not how many tasks you solve :)

This website is not for Iranian only !

This wouldn't have been a problem if you stuck to the terms of the nuclear deal

I agree!

I think you solved the problem in a more complicated way. It has simpler solution using some prefix sum and iteration without anything special.

https://www.codechef.com/COOK103A/problems/MAXREMOV

https://codeforces.net/contest/1132/submission/50837409

dp1[l][r][a] = Minimum to delete all in range l..r except for character a dp2[l][r] = Minimum to delete all in range l..r

You can straight up solve for DP(i,j) = answer for substring s[i:j]. It takes O(n³) time and O(n²) memory. See my solution here.

How to do the simulation?

Yup. However, you should probably do simulation in O(n + k) to avoid TL.

Well, model solution does something like that:

Let L be the least common multiple of all numbers from 1 to 8 (L = 840). Then, if in the optimal answer we need to use c items of weight i, we may write c in the following form: , where . Then we may merge items of weight i into p items of weight L, if we fix q.

This allows us to use the following dynamic programming solution: dp[x][y] — the maximum number of items of weight L we may obtain, if we tried x first types of items, and got total weight of y while using less than items of each type. Note that the second dimension should have size 8L, since it is the maximum possible sum we may obtain in this case.

But it seems that some participants used different heuristics and random. We aren't actually sure if such solutions should fail.

You could solve it my noticing that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16.

I think so, but with bad optimization you'get TLE on 22 or 27th test case.

was intended. It was more like "I'd like you to do linear simulation but won't mind if you sqeeze extra log on top of it".

https://codeforces.net/contest/1132/submission/50849148

The check function is linear time.

Let dp[i][j] indicate minimum number of ways to delete the substring from i to j. Now there are 2 possibilities either character at i and character at j are equal or not.

If str(i) == str(j) then dp(i)(j) = 1 + dp(i + 1)(j — 1) Else dp(i)(j) = min( 1 + dp( i + 1)(j) , 1 + dp(i)(j — 1))

I passed with the same complexity, but I had to use priority_queue, got 3 TLs because of multiset.

I hate such problems. Why Codeforces push us hard as hell in terms of time limit? I think correct time complexity is enough.

Ye, it probably did. Should've either set it the way you won't think of or make the constraints a bit lower.

Instead of using set, you should just put the element that you are sorting your set by, as an index in a vector because once you delete an element form the set you will never insert a smaller one back, so you can somehow call the set monotonous. Here is my solution with complexity O(log(1e13)*(N+K))

Because it exceeds time limit.

Check : 4 4 1 1 2 2 3 3 4 4

Here is possible to use partial sums approach. Also, you can use the event-based approach.

Given an array of numbers, partial sums is a technique used to get in O(1) the sum of numbers in an interval [l, r]. It works by iterating from zero to the length of the array adding up for every position the sum of the previous position. So if your partial sums array is called sum you can get the sum between [l, r] by doing sum[r]-sum[l-1]. Precalculate the partial sums array will take you O(n), where n is the length of the array.

In this case you can do the partial sums array such that sum[i] = k if there are k workers to paint the i-th fence. To make the partial sums without iterating from l to r every time, you can simply add 1 to sum[l] and -1 to sum[r-1] because you know in that positions someone will start painting and had finished painting respectively. Finally you make the sums, such that sum[i] += sum[i-1].

Now you can make partial sums again but counting the number of fences to be painted by zero, one and two painters respectively, to easily know for each interval [l, r] how many fences will not get painted if the corresponding painters covering that interval are not hired.

Note that this technique is useful for problems that does not have updates over the values of the array. If you find a problem where you can do partial sums and your algorithm does not pass in time because the update queries, try something like Fenwick Tree or Segment Tree.

The charges at the beginning of the (k + 1)-th minute don't matter.

Hint: Use a difference array to count how many painters paint each block in O(n). Then do some O(n²) brute force(Try picking any two painters and leave them aside).

More about the difference array

Suppose the string is "aaqwertyaaytrewqaa". You want the last character deleted be a

"aa"+ "qwerty" +"aa"+ "ytrewq" +"aa"

If you do "qwerty" and "ytrewq" independently you spend 6+6=12 steps.

If you do substring "qwertyaaytrewq" at once, you spend only 7 steps.

That's why it's not always optimal to do them independently.

I think in some circumstance that isnt the optimal way. Example: acbabca. Your solution will get 5 but 4 is the answer.

Same. Statement is very poor.

Why would you need either of those?

For example?

For a particular subarray [i, j], I'm just iterating through all possible positions k which would form the last position of the segment which would be deleted together. The character at k should be same as in i, of course. And, then in the transition we can stop considering one of the positions (either i or k as they are deleted together). So, both the transitions: ans = Math.min(ans, recurse(i, k — 1) + recurse(k + 1, j)); or, ans = Math.min(ans, recurse(i + 1, k) + recurse(k + 1, j)); should work.

You have one pair of "()" and one pair of ")(". So whatever you choose first, it is not correct.

http://www.usaco.org/index.php?page=viewproblem2&cpid=792

C is just the k=2 case with n,m <= 5000 of the problem above, which can be solved in O(nk+nlogn).

NO

first for each index i find the maximum index j such that j < i and a_j is greater than or equal to a_i,call this last[i]. this can be done in linear time using a stack.

consider ans[i] as the answer if we start our sequence from position i.now make a maximum segment tree on ans values and iterate i from 1 to n there are two cases :

1. i > k : in this case remove the value from position i — k and add 1 to positions in range [max(last[i] + 1,i — k + 1),i] , now the answer for query ending in position i is maximum value on our segment tree

2. i <= k : in this case you just have to add 1 to positions in range [last[i] + 1,i]

I got MLE right on tc 1 !!!

50864311

I used DP to solve C click here

I got 2WA(typos) during the contest.
Hacked.
2 more WA during up solving.
Finally Accepted?

my a problems have be hacked ,can you give me some adives?

DP or some brute-force

System test haven't started yet.

My rating changed as soon as I write this.

You have an error on line 19, you have pair<int, int> parr[n]; but it should be pair<int, int> parr[q];.

I implemented the method of above link, check my code. https://codeforces.net/contest/1132/submission/50925460

Everyone is protesting C against weak pretests.

HackerMan, Huh?

Well, luckily, the next div2C is more likely to be even easier than edu C!

As we all know that this educational codeforces round had 12 more hours to hack any solution.Maybe there was somebody interested in hacking solutions or they wanted to get a higher rank. So they tried their best to hack others' solutions(Holland_Pig's own opinion).