On Charis02 → How to attract contestants to Regional OI?, 3 years ago +8 Then raise some. For example, contact companies for sponsors or even OI veterans for support.
 On Charis02 → How to attract contestants to Regional OI?, 3 years ago -30 Prize money for top participants.
 +3 tourist aura?
 On mogers → Facebook Hacker Cup 2017 Announcement, 7 years ago +5 I still haven't received T-shirt from last year's event :/
 On Arpa → Codeforces Round #383, 7 years ago 0 "This graph is bipartite" ?
 On ma5termind → HackerRank HourRank-15, 7 years ago +16 I didn't use DP but combinatorics instead.Firstly, the number of permutations of a multiset having N elements, including M duplications, is N!/(2^M). Let's denote M as the total number of duplications in the initial multiset.Let's calculate the number of permutations having at least K successive equal pairs: - There are R=(N-K*2) remaining elements which do not belongs to these pairs. - There are (M_choose_K * K!) ways to select and order the pairs. - There are R!/(2^(M-K)) ways to order the remaining elements. - There are (K+R)_choose_K ways to "merge" the selected pairs with the remaining elements.The formula is (M_choose_K * K!) * R!/(2^(M-K)) * (K+R)_choose_K.Then I used the inclusion-exclusion principle to obtain the answer.My code: http://pastebin.com/B2ZsF4Zc
 On Yury_Bandarchuk → HackerRank HourRank 14 Invitation, 8 years ago +11 Wow that's tricky. Is the problem solvable then ?
 On memset0 → Topcoder Single Round Match 701, 8 years ago +18 Any hint for Div1.600 ? There seems to be a crucial insight ?
 0 Consider the sorted version of the input string. The most crucial observation is that the best answer must be a prefix of this string.Let's binary search the length of the answer, the only problem is how to check it fast. An useful insight is that any prefix contains every positions of the same character, except one. So the problem reduce to this: Given the picked positions, select some more positions in order to fulfill the requirement, this can be done greedily in O(N).
 On arsijo → Codeforces Round #371, 8 years ago +15 Problem C appeared on round 13 (http://codeforces.com/contest/13/problem/C). The only change is the resulting sequence must be 'strictly' increasing, but the idea is the same.
 On gongy → 2D Range Update and Query, 8 years ago +13 Well, simply view the matrix as max(m,n) * max(m,n) if you want :)In fact quadtree is built separately on each dimension, so you don't have to make sure the matrix is square.
 On gongy → 2D Range Update and Query, 8 years ago +13 Add submatrix and query sum of submatrix can be supported using 2D BIT (thus possible using 2D segment tree). But I believe add submatrix and get max on submatrix cannot be done the same way as the 1D case, and quadtree is the best I know for such cases.
 On gongy → 2D Range Update and Query, 8 years ago +5 It's impossible to achieve log^2 worst case time complexity. But you can use quad tree instead, which gives O(N) per update/query.
 On pranjal.ssh → BlackRock Codesprint , 8 years ago +10 Somehow the contest disappeared from the archived contest list and my contest history. It's been a month and I haven't got any email from BlackRock.
 On pranjal.ssh → BlackRock Codesprint , 8 years ago +6 Let A and B be two selected elements, in which we can make exactly one element to be "special" (i.e it's probability become 100%).If we make A become special, the income is: F(A) = A.price*100 + B.price*B.prob;If we make B become special, the income is: F(B) = B.price*100 + A.price*A.prob;When it's better to make A become special ? The condition is exactly F(A) > F(B). This is what the compare operator do in my code.Now if you look closer to the expression F(A) > F(B), it's actually: A.price*(100-A.prob) > B.price*(100-B.prob).
 On pranjal.ssh → BlackRock Codesprint , 8 years ago +5 I only use backtracking with meet in the middle principle. Backtrack for the first 2^(N/2) possible configurations, save the difference of them in an array count[]. By difference I mean the remaining characters if we trim the similar prefix. Each configuration can be represented by a binary mask smaller than 2^(N/2), which is small. Do the same brute force backward, now use count[] to re-calculate the answer.
 On pranjal.ssh → BlackRock Codesprint , 8 years ago +6 Sort the elements by P*(100-C). Now if we pick M elements, then it's optimal to make sure that the first K elements can be sold. Use heap to build two arrays prefix[] and suffix[], where prefix[i] = sum of K largest Price*100 in the first i elements, and suffix[i] = sum of (M-K) largest Price*Prob in the last (N-i+1) elements. Finally answer = max(prefix[i] + suffix[i+1]).
 On tweety → Croatian Olympiad in Informatics 2016, 8 years ago 0 My AC solution for "Dijamant" is O(N*K*(N + K)), but I think it's hard to generate a test case where it fails.For each node u store a set A(u) of its super classes. To check for "diamond" after adding node U, let L be the list of nodes that U inherits from, we need to test if there is any two nodes (x, y) from L, such that (neither x inherits y, nor y inherits x) and (A(x) intersects A(y)). To eliminate the first condition I filter the list L to make it contains only the deepest nodes (no other nodes in L inherits from these), this part is O(K*K). From the reduced list check set intersection in O(K * N), this can be done effectively using std::bitset<>.Any idea for better asymptotic ?(Edit) code: http://paste.ubuntu.com/15595579/
 On tweety → Croatian Olympiad in Informatics 2016, 8 years ago +3 Task "Palinilap"I used polynomial hash to quickly check equality of any pair of substrings.Compute Inc(i, j) = number of palindromes we'll get if s(i) is changed to character j. Compute Dec(i) = number of palindromes will be "destroyed" if s(i) is changed.After binary search for each center, we got the first mismatched position L, R. Update Inc(L, s[R]) and Inc(R, s[L]), again use binary search + hash to calculate the bonus. The Dec[] array is changed in range [L+1..R-1], this is just offline range update of linear functions.Finally answer is max(initial_palindrome_count + Inc(i, j) + Dec(i))Time complextity: O(NlogN + N * 26)(Edit) code: http://paste.ubuntu.com/15595576/
 On tweety → Croatian Olympiad in Informatics 2016, 8 years ago 0 Task "torrent"If there is one source, then make it the root: F(u) = answer for subtree u. Transition is simply sort the children descending F(), F(u) = max(F(v1)+1, F(v2)+2, ...).For the first subtask, iterate the edges on the path a->b, delete that edge, then solve for the two parts. Complexity O(N * NlogN).Binary search (or ternary search) for the split edge gives O(logN * NlogN), which solves subtask 2.(Edit) code: http://paste.ubuntu.com/15595565/
 On fushar → TLX Open Contest Beta Round #2, 9 years ago +5 I got 100 now. Can you improve the checker so that it accepts output with no endl ?
 On fushar → TLX Open Contest Beta Round #2, 9 years ago 0 I have no idea why the feedback of my submissions for C keeps showing that my code did not pass sample cases, I did test them on my local computer !!! (my TLX account is 'leduc')
 On xuanquang1999 → Need help with this problem..., 9 years ago +3 Using Deque for the RMQ problem is applicable when our range queries are monotonic, that is, L[i] <= L[i+1] and R[i] <= R[i+1] with L[], R[] are left and right bounds of ranges. The algorithm is some kind of sliding window algorithm which you can find the pseudo code here: http://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on
 On xuanquang1999 → Need help with this problem..., 9 years ago +16 The problem is solvable in O(N). Instead of directly delete K digits, we can try to find the biggest number with N-K digits. This can be done with simple greedy. Let the string be s[1..n], for the first digit, pick the biggest one in s[1..n-k+1], suppose you find it first at index i1, then the range we should consider for the second digit is s[i1+1..n-k+2], then you got i2, .etc... Observing that these ranges are monotonic, a deque is enough, or you can build a RMQ sparse table, or a Segment tree.
 On speedy03 → The USACO 2015 February contest , 9 years ago 0 I haven't known that algorithm. If that is the official solution, I had no chance in this contest.
 On speedy03 → The USACO 2015 February contest , 9 years ago 0 Can anyone give me some hints on the second and third problem (Gold division, "censor" and "fencing") ?
 On I_love_Hoang_Yen → Yet another blog post about cin vs scanf, 9 years ago +13 Maybe that only happens on Codeforces, on my PC cin/cout are significantly faster.
 On vitux → Codeforces Round #262 (Div. 2) Editorial, 10 years ago +2 In the contest, when I saw n <= 8, I think that may be brute-force works. I tried to implement a slow brute-force consider all points in the circle and realize that there is a 'pattern': if n is even, then we only need points of types (0; r) and (0; -r), else with odd n, it is sufficient to use the points which have maximum distance from O (there are 8 points which have that property), plus 2 points (0; r), (0; -r), we get 10 points in total. So a back-tracking algorithm to deal with these 10 points is enough ! (Actually in my solution, I use up to 27 points, just to ensure the correctness). It seems that the solution described in the editorial uses the same idea as mine, but it need to check all points on the convex hull. Anyway, these are only guesses, I cannot prove it yet.
 On Neodym → Codeforces Round #262, 10 years ago 0 Recently I am having an OI training course which focus on approximate algorithm, so that solution came to me naturally (but yes, I was really lucky).
 On vitux → Codeforces Round #262 (Div. 2) Editorial, 10 years ago +3 Till now I could not believe that my simple back — tracking solution passed E (shocked when looking at the editorial).
 On Neodym → Codeforces Round #262, 10 years ago 0 Contest is over ! I solved C by binary-search the answer + O(n) check. D seems to be hard with that xor operator. I got E pass pretest using back-tracking n elements from a set of a few boundary points. Hope my solution can get AC.Upd: Yeah!!! E Accepted. Hello Div 1 :))
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 Your idea seems promising. I hope we can have a private chat to figure out some details. I can only use Fenwick tree with getSum or getMax operations, it will be cool if i can use Fenwick tree for getFloor method.
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 I have just read basic information about Set. Thanks for your idea, it will work. But because I use PASCAL (not C++), implementing Set is such a challenging task.
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 I have no idea about Map data structure. The problem is just a weekly homework and I think it can be solved using pure C (raw arrays).
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 Thanks, I got it. Sorry for bad English. (I have already edited my post) Hope you can help me with my homework.
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 Thank you, my mistake, fixed
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 I think you have misunderstood my question, there are O(N^2) sums. I am not asking for prefix sums, but sums of consecutive elements. Sum[i..j] = PrefixSum[j] — PrefixSum[i-1]
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 So, for each i, we use an inner for loop to find the best S[j] such thạt S[j]+M <= S[i] (here partial sum means the sum of elements a[j..i]) I think the complexity is O(N^2)
 On ladpro98 → A problem about sum of sub-arrays, 10 years ago 0 Can you give me more details. I try to sort the SUM array but then I am unable to Bin-Search since the positions has changed.