Comments

Then raise some. For example, contact companies for sponsors or even OI veterans for support.

Prize money for top participants.

tourist aura?

I still haven't received T-shirt from last year's event :/

On ArpaCodeforces Round #383, 7 years ago
0

"This graph is bipartite" ?

On ma5termindHackerRank 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

Wow that's tricky. Is the problem solvable then ?

+18

Any hint for Div1.600 ? There seems to be a crucial insight ?

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 arsijoCodeforces 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 gongy2D 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 gongy2D 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 gongy2D 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.sshBlackRock 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.sshBlackRock 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.sshBlackRock 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.

Code: http://pastebin.com/akXMX9Dc

On pranjal.sshBlackRock 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]).

Code: http://pastebin.com/uFwdA9Q3

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/

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/

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/

+5

I got 100 now. Can you improve the checker so that it accepts output with no endl ?

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')

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

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.

I haven't known that algorithm. If that is the official solution, I had no chance in this contest.

Can anyone give me some hints on the second and third problem (Gold division, "censor" and "fencing") ?

Maybe that only happens on Codeforces, on my PC cin/cout are significantly faster.

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 NeodymCodeforces 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).

Till now I could not believe that my simple back — tracking solution passed E (shocked when looking at the editorial).

On NeodymCodeforces 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 :))

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.

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.

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).

Thanks, I got it. Sorry for bad English. (I have already edited my post) Hope you can help me with my homework.

Thank you, my mistake, fixed

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]

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)

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.