спс

And I hope not the last:D

Юра, он такой)

Заложил пацана.

Минутка беларусской солидарности на кодфорсес.

I liked question B even though my solution got hacked. It did not seem tough(probably because it was level B and I was expecting it to be easy) at first look but required careful observation.

Thanks a lot

Thank you!

And netman's graph will be much more interesting if his rating goes from red to grey again and becomes lower than worse :D

I'll think about it. It seems I'll move 2014-2015 CT S02E02: Codeforces Trainings Season 2 Episode 2 (CTU Open 2011 + misc).

Он больше не сможет официально принимать участие в контестах div2.. Теперь последнее место снова свободно!

Вряд ли. Как минимум половина напишет плохо.

Поправка: Coder Strike я не учитывал, и была таки одна решенная D.

по мне так. составить задачу проще, чем решить чужую. Во время контеста у тебя 2 часа и кроме задачи D, у тебя есть еще A,B,C. А на составление задачи у тебя есть сколь угодно времени, и емакс под рукой.

Да и я думаю, если Gerald пропустил задачи в раунд, то все ок.

I know. Focre.

Yeah, same, my solution for E last time was apparently flawed but worked because of weak testdata.

А всю же публику КФ волнует, будешь ли ты писать это раунд или нет.

Мотивация — будет удобная причина пропустить одну или несколько из пяти запланированных пар:) Хотя в середине сентября для этого и причин не надо:)

Nope, I love this time, in China, I always get up at 11:00am and go to bed at 3:00am, now I'm in very good health!

Elo rating system can't provide high ratings to all ! therefore good luck to all !

unfortunately it crashes at the beginning of the contest, when most of the participants are submitting for problem A.. Hope that future contests will run smoothly :)

Nice to meet you~

Actually, x4776.

Whoops.. nothing can change him :D

http://i.imgur.com/B6sMIkH.png

See now, Seems like he is back on usual track :)

don't let that fool u. he solves problems just so that he can get Pretests passed and then hack others (unsuccessfully, ofcourse).

гению, который придумал несимметричное отношение "быть синонимами"

10 мин. смотрел и непонимал, почему в первом примере ответ не "1 3"...

apparently, fiterr can. :D

ДП[количество взятых отрезков][позиция]

dp[i][j] — максимальная сумма заканчивающаяся в i, поделённая на j частей размера m.

dp[i][j] = max(dp[i-m][j-1] + sum[i-m + 1] -sum[i + 1],dp[i-1][j]);

sum[i] = a[i] + a[i + 1] + ... + a[n]

И тогда еще вопрос, почему неправильно k раз брать максимальный по сумме подотрезок длины m и удалять его из массива?

присваиваем каждой уникальной строке номер. Строим граф. Потом обходим дфсом и для каждого слова находим минимум.

4000 60 60 0 0 ... 0

or

5000 1 5000 1000000000 1000000000 ... 1000000000

I got two hacks with these

dp[i][j] = max(dp[i-1][j], dp[i-m][j-1])

DP : dp[i][j] denotes optimal answer when we choose i m-length sub-arrays before index j+1. Also b[j] is sum of first j elements of array. Then : dp[i][j] = max(dp[i][j-1],b[j]-b[j-m]+dp[i-1][j-m]); //You either choose j-m+1...j as a sub-array or not.

I guess it is about overflow.

Answer could not fit in 32-bits type.

DP : dp[i][j] denotes optimal answer when we choose i m-length sub-arrays before index j+1. Also b[j] is sum of first j elements of array. Then : dp[i][j] = max(dp[i][j-1],b[j]-b[j-m]+dp[i-1][j-m]); //You either choose j-m+1...j as a sub-array or not.

i did it by simple dfs. Will see is wrong or not after systests

Simple DFS+DP won't work. You'll need SCC+DP.

Consider this case:
1
rrr
2
rrr rrrr
rrrr e

or even this one:
1
eee
2
eee efef
efef a

Submissions are skipped when exactly the same code is submitted before and judged.

It has also happened to one of my friend. Only submitted a single code to a problem but it was skipped with "JUDGEMENT CALL".

Moreover, some solutions get ML on Java7, but AC on Java8.

Why my 1st question is skipped?

UPD: да, можно сократить использование памяти, храня не всю матрицу ДП. Но получив 190МБ из 256 я бы не стал усложнять код

Решать можно с O(n) памяти. Достаточно хранить последние m + 1 слоя динамики. смотрите мое решение: 7836016.

1. Сreate a directed graph of rules (rule = edge in graph).
2. Find all strongly connected component.
3. For all component find min vertex in it (minimum number of 'R' or minimum length)
4. Compress graph in tree (component in old graph = vertex in new) and update min for all components (using DFS).
5. For all worlds in text find vertex => find components => add min to answer

I'll Try to explain my solution.

Let's forget about the words we have for now and focus on the synonyms. Let's model the problem as a directed graph problem with vertices as the words we have in the dictionary and there is and edge from word a to word b if word a can replace word b. Each word has a cost of <Number of Rs,Length>, If the cost of some word a is smaller than the cost of some word b, then it's always better to substitute word a with word b. But Notice that word b can also be replaced by another word c for example if c has a smaller cost.

So the first solution that comes to your mind is a simple dfs from each word to find the word with the smallest cost to be replaced with. The problem with this idea is cycles. If you started at some word and through the dfs you went back to that node again then words of this cycle can replace each other and the optimal solution is that they are replaced with the word with the smallest cost.

Wikipedia : "A graph is said to be strongly connected if every vertex is reachable from every other vertex". So words of a certain strongly connected component here can replace each other so let's find all strongly connected components and treat them as one node with cost equal to the minimum of the costs of the node of this component.

In our new graph there is an edge from node a to node b, if there is any edge in the old graph starting from any node in component a and ending in any node in component b. Now we are sure that in our new graph there isn't any cycles and we can run the dfs we mentioned before to get the cost of the representative node of each strongly connected component.

Finally back to our words, The cost of a certain word is the cost of the representative node of the SCC in which this node lies.

Note A common hack in this problem was that the answer may not fit into a 32-bit integer.

Here is my solution 7840587, I hope you understood my explanation :)

your submission link is wrong it will be 7839186

Unlike java, which directly gives out of bounds exception, C++ silently tries to access the memory index.
Two cases can occur:
1. the memory access is not allocated to the current program: in this case it is SIGSEGV(e.g. allocating a[1000] and accessing 10^7th element.
2. The memory access is allocated to current program: like allocating a[1000] and b[1000] and then accessing a[1005] could give some element of b since such small arrays are allocated mostly contiguous. So, if the memory access does not cause SIGSEGV and is not altered by an intermediate code logic, it will behave as normal (extended) part of array, and hence the program gives correct answer.

It is contest too???