I don't get the code :))

What does that graphic mean ? I don't get the point.

I don't think that it's that big of a deal for contests. On the other hand, STL may be really useful sometimes.

Well, from my expirience you can write less code using C++ as opposite to Java, and C++ is much faster than Java. I myself migrated from Java to C++. And I find C++ very pretty after using Java!

But you don't have to migrate from Java to C++ to get successful in contests like ACM ICPC. Moreover, Java is really good because of having built-in long arithmetics. Btw it's much easier to handle bugs with Java, because it simply doesn't allow your program to compile if you have commited some minor mistakes. You can spend a lot of time trying to find annoying typo in your code, since it most probably will compile.

It doesn't really matter wether you use Java or C++, because it's just an instrument. What matters is your skills and knowledge, so you better use a language, which seems to fit you better.

This much time is left.

We call it cold joke too in Turkish. Actually, it's also called cold joke in English.

Ok. I downloaded it. Sorry for the inconvenience.

When I run this on the sample, I get:

contests
heroes
ladies
s

And the last line is missing the newline character. It seems that Perl interprets newline as line separator instead of final character for each line ("lady\n" vs. "lady", "").

hello

IMHO, most interesting thing is to find out what test case #3 checks for. First, I thought it was because of problem misunderstanding, But so much time have already been lost for rereading((

I wrote DP optimized by segment tree. I think there is a better solution.

Code

Let's denote by dp[i] = the length of the longest subsequence that fits the properties in the problem statement, ending by element i. You may easily calculate this in O(n^2), but this won't fit into the time limit. In order to optimize this aproach, you will need to use 2 Fenwick trees and a usual array (or just one single segment tree). Let's denote by x[i] = the largest dp[j] already calculated with it's v[j] = i (i.e. the largest dp with a fixed value), then the first Fenwick tree will mantain maxima on segments of the form [1,i] from x, the second one on segments of the form [i,n] and the usual array will be the vector x. Hope this helps.

thanks!

this is a really nice idea.

My idea is as follows.

Since all numbers are between 0 and 10^6, we can store the length of the longest valid sub-sequence ending with each number. We can store those values linked with their numbers in a max-heap. We begin to traverse the given array. For every number x that we encounter, we erase the values for x-1 and x+1 from the max-heap. Then we update the length of the longest sub-sequence ending with x. After that we put values for x+1 and x-1 back in the max-heap. Note that since the length of the original string is at most 10^5, max-heap's size won't be greater than 10^5.

Here is the code: http://pastebin.com/yRqtUSxV I have used STL set for the heap.

D: I didn't succeed with Trie, it gives ML

C: I'm afraid map+dsu+dfs will not work in 0.5 s (compress the destinations with map, find all connectivity components, mark some of them as "cycled" and find the wire that should burn in every "cycled" component)

That's all I can say.

D was a typical cycle-finding problem. One can use the hare and the tortoise algorithm to solve it. You can find it on Wikipedia. It is a simple algorithm with tons of applications.

For C, Ralor's idea is pretty close to the solution. One needs to find the maximum spanning tree for the given graph.

C explanation -> Find mst using kruskal

But edges go in descending order of reliability[since we dont want minimal reliability edges to be included in ans]

And if same reliability, in descending order by cost[since we want higher cost]

Now insertion order is just the reverse of this

test_
1 1
4
MRMRMRM
right answer is 10, and your answer is 7

B can be solved by backtracking, Precompute if you can achieve a sum S using L elements if the elements {a1, a2, .. } (can be represented using a mask) are available.

Then use backtracking to fill each of the empty cells, and keep checking after each assignment whether the assignment is possible or not.

code

No tricks. Just a recursion, column by column.

You should read from "input.txt" not from stdin.

Look at Floyd's cycle finding algorithm or Hare and the tortoise algorithm. It will work in O(n)

Have you found a solution?

as x₀ = x₁ = ... = x_i, and you know x₀ = a₀ + b₀ and a₀ is fixed in s * p / 100, you only need to find the right b₀. you can do that using binary search for values between 0 and s and checking if it needs more or less months than m for this b₀. this checking can be done in O(m): at the end of m months, check if there's still some debt left. here is my code: http://pastebin.com/Va8yCuGH