Qualification Round 1

Just sort. Notice 0 in the array.

Choose the 3 and 1 as much as possible. And let 2 combine with themselves. If there are more 1s and 2s, let two 1s combine with 2, and every four 1s take same taxi.

Implement with stack. If the string begin with '/', let top = 0, else remain the top; Then process the substring one by one, when meeting ".." , top--; else remain the top;

The number of new regular polygon's edges must be the factor of the given polygon. Listing all the factors take O(sqrt(n)) time. Then choose the best point take O(n). So the time complexity is O(n*sqrt(n)).

It's a classic DP problem. Array dp[i][j] stands for the min rightmost endpoint when choosing at most j segments from the first i segments . dp[i][j] =dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]). When the dp array is completed , find the max value of left[i+1]-dp[i][k] and rightmost point — dp[n][k]. Totally take O(n*n).

Qualification Round 2

Compare every two records and find the right friends. Give every name a unique number so as to avoid counting same friend twice. If a and b is friends, let friend[a][b] = true.

Establish two hash tables counting the number of the size (say 2) exiting in set makers and set caps. Obviously the sum of min number of every size in two sets is the first answer. Similarly establish two hash tables in order to count the number of the same size and same color. The hash function can be hash(color, size) = color*1000+size.

C 159C - String Manipulation 1.0

Because the length of string is at most 100*2000, so we can build 26 line-segment-trees to count the 26 Latin letters. The way to build tree and find the position of K-th letter is quite simple if you under stand line-segment-tree :)

A dp method is really great~ , sum[i] stands for the number of palindrome string in the first i letters. palindrome[i][j] judges weather the substring i...j is a palindrome string. dp[i] is the answer for the first i letters. dp[i] = dp[i-1]+Sum( palindrome[j][i]*sum[j-1] ) for all j<=i && j>0 . sum[i] = sum[i-1]+Sum(palindrome[j][i]) for all j<=i.

sort the array with compare condition (cube[i].color < cube[j].color ||(cube[i].color==cube[j].color && cube[i].size>cube[j].size)). Then for the first i cubes , there is a array Max_cube, Max_cube[j] records the max sum of j cubes' size with same color. To the cube i+1, if it's the k-th largest size of its color. Compare the answer with cube[i+1].size + max(Max_cube[k],Max_cube[k+1],Max_cube[k-1]). The time complexity is O(n*logn).

Forgive my poor English :)

gl and hf tonight!

In 159D - Palindrome pairs, if you know a method to find all the subpalindromes fast, you can get a better than O(L^2) solution:

Make two Segment Trees for counting the starts and the ends of palindromes.

If a palindrome(for example, odd) has center at position K and maximum length 2 * D + 1, then: 1 palindrome starts in K and ends in K, 1 starts in K — 1 and ends in K + 1, ..., last starts in K — D and ends in K + D. So, for adding their ends and starts in O(log L), we use segment updating.

What is the answer on the task? It's just a sum: for all K = 1, 2.., L — 1 we multiply the number of palindromes, that ended in K(exactly), and the number of palindromes starting later, i.e. st[K + 1] + st[K + 2] + ... + st[L]. Each number we can get in O(log L), using ST.

Yeah, it's a better solution. And it seems that suffix array can work well in finding all palindromes , but i'm not good at it :( .

There is O(n) solution. There is way to find palindromes is O(n) using Z-function-like algorithm. And we can to perform all queries to segment trees offline. First preprocess all Add queries for O(n), and then answer all Sum queries.

can you please explain your approach how this Z-function works here? it will be really helpful !

I can't remember what talk about 6 years ago. There is original article in Russian http://e-maxx.ru/algo/palindromes_count You can translate it using machine translation, but I think this transation isn't good https://translate.google.ru/translate?sl=ru&tl=en&js=y&prev=_t&hl=ru&ie=UTF-8&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2Fpalindromes_count&edit-text=&act=url There was project far transalting site "e-maxx.ru" in english try to google it

thanks a ton for this !!

though it make little difference in this problem, but it is good!

I am quite new to sport programming so I have never implemented a segment tree. I heard about it, though, but thought it was complicated. Anyway, I think my solution to 159C - String Manipulation 1.0 is quite neat :)

In short: binary search in a Fenwick tree.

Slightly longer: we start out with 26 arrays, all filled with 1's and having a length of k*repeats[c], where repeats is an array containing the number of occurrences of each character in the initial string. Then, we build a Fenwick tree on top of each of these arrays. After that, we start processing the request. For each request p_i, c_i, we perform a binary search in the corresponding Fenwick tree in order to find the leftmost position with p_i 1's before it. Then, we replace the 1 in that position with a 0. Each search takes O(log(k*repeats[c_i])) queries to the Fenwick tree, each being of O(log(k*repeats[c_i])) complexity, which yields O(log^2(k*repeats[c_i])) per each request. The entire complexity of the algorithm is O(n*log^2(k*|s|)).

After processing all requests, we extract the result by merely moving through the input string k times, each time either printing the corresponding character (if there's a 1 in its array) or omitting it.

I also use this method. It really works. This is my code. 12708008

thank you for your source code, but could you please explain this part : (i dont really understand why you update the tree with 1)

for ( int i = 0 ; i<26 ; ++i ) { int veSize = ve[i].size(); for ( int j = 1 ; j<=veSize ; ++j ) { tree[i].update(j,1); } } thanks :)

I was trying a tree solution for C, but was getting wrong answers and eventually decided to make a solution that supposedly took advantage of the fact that the string is cyclic. Yet in reality, I think it can easily become a solution that needs O(sqrt(|ss|)) time to process each command. (Where ss is s repeated k times) (Currently it is O(|s| + k ).

There are initially k fragments of the ss string what you could do is for each of the k fragments, ad each letter, know the number of times the letter appears in the fragment and the positions of those appearances.

Now, in order to delete the P-th instance of a letter in the overall string (ss), you can first do a O(|k|) loop to find the fragment that has the p-th instance (Use the sums for each fragment instead of going through the letters in the fragment manually). After you find the fragment, you can use a O(|s|) loop to naively remove the [p — (sum of the letter counts of previous fragments) ]-th instance of the letter in the fragment.

This only looks like abusing the format of the string, because you can adapt it to work in O(sqrt(|s|)) time for any string (not just cyclic). So, let's say that ss has |ss| elements, you can always split it into O(sqrt|ss|) fragments of O(sqrt|ss|) letters each. The overall complexity would become O(sqrt|ss|) per step. The constraints make this good enough.

I am trying understand the 158E Phone calls solution but it seems a little complicated for me. In my little experience with dp I haven't found a problem like this. Could you explain the solution in more detail? Please!

Suppose we processed the first i calls and j of those were ignored, the best way is to minimize the last minute of conversation (i.e. maximize the length of freetime until the current moment). It's the meaning of dp[i][j]. If you still can't get it, feel free to point out what you are confused :)

Problem is, topicstarter's formula for dp[i][j] is wrong. It should be:

dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]), not

dp[i][j] = min(dp[i-1][j], max(dp[i-1][j-1],left[i])+length[i])

Here is my submission with this solution: 1355912.

In my opinion, understanding its meaning is more important. If you know how it work, it isn't difficult to get the correct formula.

The meaning is pretty straightforward. Suppose that you know, for all previous i's and j's, the least time at which all calls end. You are currently considering whether it is a good idea to add the current call to the ones you omit, or not. This depends on the time all calls are going to end at.

If you choose to omit it, you need to look at the time at which i-1 calls ended, and you dropped j-1 of them (because the newly dropped call is going to be the j-th).

Otherwise, you're going to look at the time at which i-1 calls ended, out of which j were dropped (since it is always preferable to drop as many calls as possible). Then, you should find the time at which the i-th call is going to end. Since you already know when i-1 calls ended and when the i-th call is supposed to start, you should find the time at which it actually starts — by merely taking a maximum. After that, you just add its length to the time it starts.

You are interested in minimizing the time, so you take the minimum.

Thanks for your replies! I was out for a day and I was unable to reply. Already understand the solution.

I am used to solve DP problems with top down strategy using recursion since it's easier to me to understand the solution.

I know that recursion is expensive and it should be avoided when possible so I am trying to change my strategy.

Thanks again!

Thank you very much that made it very clear, just started learning dp, I would never have got it if you didn't posted this, it's been 7 years, since this post was made, but I wanted to ask a question, how do you form the base case that is what values must be stored initially in the two-d array dp[i][j]? is there a procedure you follow, what do you check or think before you form dp[][] for initial cases. thank you

thx for correcting my mistake :)

if somebody can help me here in 158b, my test case 74 is wrong but my code seems to be okk. its in gnu c++ 4.6

## include

using namespace std; int main() { long n,ne,i,count=0,newe,fours=0,three=0,two=0,ones=0; cin>>n; short s[100005]; for(i=0;i<n;i++) { cin>>s[i]; if(s[i]==4) fours+=1; else if(s[i]==3) three+=1; else if(s[i]==2) two+=1; else ones+=1; } count=fours;

was somebody able to solve D using python? I implemented the DP solution above but I run out of time in test case 9 and the subsequent ones.

On my machine python finds the solution in ~9 seconds (past the time limit).

how can I find out if somebody ever solved this problem in Python?

This is not tutorial of VK 2015, can some body remove the tag?

Here is my Solution for 158D - Ice Sculptures: 15272199 My ans got WA in test case 39. Can anyone help finding my bug.

Thanks in advance.

Thanks for all!

You output nothing on this test. What is your question?

Thanks for all!

B taxi. wrong answer on 67. can't even see inputs!

http://ideone.com/cTEsEx

Use ideone.com to share code.

http://ideone.com/cTEsEx

Can someone help me with 158B - Taxi ? I did exactly as this editorial guides, I took the number of 4's and added them to the number of taxis, then I combined the 3's with 1's. Now, either (i) 3's are in excess or (ii) 1's are in excess or (iii) none of the 1's or 3's are left.

I combined the 2's with themselves. Now, either (a) an extra 2 is left or (b) isn't. Taking these 6 cases:

(i)(a) I added the number of 3's left to the answer and the 2 goes in a seperate taxi.

(ii)(a) I added at max two 1's with the 2, and then combined the remaining 1's in groups of fours.

(iii)(a) only that last 2 is left, which goes separately.

(i)(b) I added the number of 3's left to the answer.

(ii)(b) I combined the remaining 1's in groups of four.

(iii)(b) nothing is left, everyone has been grouped.

It seems to work, but I'm getting a wrong answer on test case 66. (49551813) The test case is too big and isn't shown fully. I can't find where it's wrong. Can someone help?

I couldn't read the cases, but in a nutshell, all you have to do is this.

4 takes 1 taxi,

3 takes 1 taxi + it can give lift to 1.

2 takes 1 taxi + it can give lift to 2 as well as to 1,

1 can combine into groups of 4 to get taxi.

If you want to take a look at my solution here it is : https://codeforces.com/contest/158/submission/50441428

Can I do this problem with dynamic programming?

Those who are stuck with Problem number 159D - Palindrome pairs

A is definitely not worth being rated as 1800. [old comment, ignore]

800 u mean?

Before rating changes recently, it was rated 1800.

158A - Next Round

why my code is getting a runtime error on test case 4?

Hello @hanfei19910905,

I see that your tip for problem 158A — Next Round, says Just Sort.

But in problem statement it says that:

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: ai ≥ ai + 1).

Since it clearly says that the array is already sorted in decreasing order. ai ≥ ai + 1

where can i get the code for these problems