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
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.
thx for correcting my mistake :)
This is not tutorial of VK 2015, can some body remove the tag?
Thanks for all!
You output nothing on this test. What is your question?
B taxi. wrong answer on 67. can't even see inputs!
http://ideone.com/cTEsEx
Use ideone.com to share code.
I solved problem D using Manacher's Algo and prefix sums. 95691489
On test case 37 the answer's shown as 3 . If n=3 and the numbers of students in each group are about 3 3 2 then it should need 2 cars .why the answer is 3????????? maximum students in a group are 4;
same issue. did u find any solution for that somehow;