159.md (3477B)
1 Source: https://codeforces.com/blog/entry/4089 2 3 Qualification Round 1 4 5 A [158A - Next Round](/contest/158/problem/A "VK Cup 2012 Qualification Round 1") 6 7 Just sort. Notice 0 in the array. 8 9 B [158B - Taxi](/contest/158/problem/B "VK Cup 2012 Qualification Round 1") 10 11 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. 12 13 C [158C - Cd and pwd commands](/contest/158/problem/C "VK Cup 2012 Qualification Round 1") 14 15 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; 16 17 D [158D - Ice Sculptures](/contest/158/problem/D "VK Cup 2012 Qualification Round 1") 18 19 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)). 20 21 E [158E - Phone Talks](/contest/158/problem/E "VK Cup 2012 Qualification Round 1") 22 23 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). 24 25 Qualification Round 2 26 27 A [159A - Friends or Not](/contest/159/problem/A "VK Cup 2012 Qualification Round 2") 28 29 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. 30 31 B [159B - Matchmaker](/contest/159/problem/B "VK Cup 2012 Qualification Round 2") 32 33 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. 34 35 C [159C - String Manipulation 1.0](/contest/159/problem/C "VK Cup 2012 Qualification Round 2") 36 37 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 :) 38 39 D [159D - Palindrome pairs](/contest/159/problem/D "VK Cup 2012 Qualification Round 2") 40 41 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. 42 43 E [159E - Zebra Tower](/contest/159/problem/E "VK Cup 2012 Qualification Round 2") 44 45 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). 46 47 Forgive my poor English :) 48 49 gl and hf tonight!