Red Alert! :P

Oh, come on, 5 hours till the contest, why sleeping at all?

I always hated English class -_-.

challenge accepted:))

if you don't submit anything your rating will not be changed, also you can unregister by finding your name in the list and then clicking on the X sign

If you don't submit anything , your ratings will not be screwed

Not everyone in the list is a problem setter :)

Yeah.I got a wrong answer because that.It's stupid.At least, they could put it in statement description in this form, not 10^9 + 9...

Unpredictability.

Now I know what was wrong with my code :(

Single change of line gets acc :/

Уже даже и закончилось ;)

A pretty solid amount. If we're talking both divisions obviously.

Good! Today you have answer for n,k<=15,tommorow to n,k<=30 ... after around 7500 days you certainly have correct solution :D

shen chemi dzma gemeixede aqett O_o mogityann azrovnebaa ,ra iyoo kaii mitxarii ertiii haa?

Please, wait, we can't discuss the problems yet.

(-- apparently I should hide this --)

I don't think so. Div2 B was simple if you just look backwards than forward. Div2 C took me 30-40 min with all that analysis :P

Было 2 макстеста в претестах.

Hm, that possibility of not submitting code if one solved it too late is wrong and should be changed...

The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 104), separated by a space .

Read the input line properly, its given distinct n,m

I'm a bit luckier than you. My rating now is 1698 -_-

I undersatnd you, man.Just take a look at my rating.I had contest when it increased being on positions like 300 and now, it decreased me ~100 taking position 300.So a differnce of differnces of more than 100 having the same position :(

You got your brother man!! :D check this out http://codeforces.me/profile/dc26

Kind of similar story :p

Codeforces Round #295 (Div. 2) 114 3 +52 1699
Codeforces Round #294 (Div. 2) 366 3 -52 1647
Codeforces Round #293 (Div. 2) 212 4 +73 1699

1699 to 1699 ._.

мы просим вас не обсуждать в комментариях задачи и решения до 14:10 MSK сегодняшнего дня

I still don't understand the idea of that problem.Was stupidly easy.You had just to implement it without needing an idea or something.I say this even thouth I solved it...it wasn't interesting, and compared to the others it doesn't find its place in this contest.The rest of the problems seemed ok event thougth that A and C were counting problems and I didn't read D and E during the contest

There were only 20 minutes left when I truly understood the meaning of Problem B.T^T

Question like this (involving complicated, non-trivial process) should deserve explanation of the sample input at least.

maybe DP, and with some combinatorial mathematics?

Above formula works when k > 0. When k = 0, then simply output s

Consider some digit d and all summands, where this digit is the i-th least significant. It will add 10ⁱd to the answer for every way to choose the +s that makes that digit the i-th least significant in some summand. That means there are no +s on the next i positions (between two digits) and there is one (or the end of the string, which gives 2 cases) on the i + 1-st position. There are no other restrictions, so we just need to put K - 1 +s on N - 2 - i positions or K on N - 1 - i positions; the number of ways to do that is given by binomial coefficients.

Another optimisation lies in adding up the same thing for all digits d farther than i from the end of the string at once, by quickly counting how many such digits there are.

5
ACGTC
Answer: 1 ("CCCCC")

Maximum possible value for a string is MAXIMUM_NUMBER_OF_ITERATIONS * n * n.
For "ACGTC", MAXIMUM_NUMBER_OF_ITERATIONS is 2 for 'C'. So this value is 50.

UPD: MAXIMUM_NUMBER_OF_ITERATIONS means maximum frequency.

Если бы было написано

    return -Long.compare(v1 - v2, 0);

То это бы гарантированно заходило. Основная идея: сравнение бывает , где a, c порядка 10⁶, а b, d порядка 10¹¹. Если забыть вычитание 1, то будет сравнение , в виде компаратора сравнение (a + b)c - (c + d)b c 0. Здесь прозрачно происходит переполнение на bc — примерно на 10²², но это происходит по модулю 2⁶⁴. Результат будет аналогичен сравнению ac - bd с 0.

К сожалению кажется, что можно подобрать контртест в текущем написании, но он будет сильно зависит от выбранного алгоритма сортировки. Для Arrays.sort, Collection.sort, std::sort, и random_shuffle + sort возможно потребуются разные тесты. В исходной версии ограничения были не 10⁶ а 10⁹. Более того, нижняя граница на a_i, b_i была не 1, а 0. Так же при прочих равных было необходимо минимизировать количество апгрейдов. Тесты я составлял в таком формате, а затем по требованию упрощения для школьников стремительно переделывал их. Это могло вызвать некоторые проблем сверх вышеперечисленных.

Call f[c] the number of letter c in the string. Call maxF is the maximum value of all f[c]. Call count the num of letter c that f[c] = maxF. The answer to this problem is count^n. I found the answer by writing brute-force solution first, then try some input to observe the rule.

k => Amount of letters with bigger frequency in input

n => Lenght of input

sol = k^n % MOD

My solution

http://codeforces.me/submissions/dc26

Observe a particular character. In following cases, I am calculating distance of only 'A'.

ABBB, ACCC -> 4
AABB,ACCC-> 8
AAAB,AAAC-> 36
AAAA, ABBB-> 16

Hence you can see, formula is something like L*X1*Y1
where
L=length
X1=frequency in 1st string,
Y1=frequency in last string.

So Distance reduces to summation of N*X*Y for each of 4 characters, "A, C, G, T"
Now N and X are constant.
We have to decide Y to maximize the product.
Now Suppose my String was AAAC. Now what string should I choose to maximize the product.

Frequency of A is 3, C is 1. So A will be the major contributor, I will get maximum when my other string is AAAA

Now if my string is of type AACC, both A & C are contributors. So I can make a string of C's and A's
I know the length i.e. 4 in this case. Now for every position , I can select either 'A' or 'C'.
So m answer here is 2^4.

Similiarly.
"AACCTT"
I can chose, 'A' 'C' or 'T' for every position.
So answer is 3^6.

Is this what you want?

What is the logic behind this solution ??

Well there are only 4 characters, and the max results has 60k digits, which should be able to fit in the time limit.

You can use priority queues. I'm not sure this is the answer you are looking for :)

You also can sort all of the cubes and use two iterators for the current upper cube and the corresponding cube it lays on.

He won't tell, but you can see this submission: 10118102

http://opentrains.mipt.ru/zksh/

Здесь должны появиться, думаю...

The editorials for all problems are coming. I'm sorry for the delay.

Short description: div 1d was greedy. if we use assign op for any skill, then it's optimal to use as first op, so change highest assign op for every skill i to "sum b-a[i]" and discard the rest.

Now every mult op multiplies answer by b, sum op multiplies answer by (a[i]+b)/a[i]. Greedily take highest multiplication factor until you can't pick any more operations. Print operations used for a skill in the order "type 1, type 2, type 3".

Note that when you use a sum operation in a skill, factors for the other sum operations on the same skill change (mult doesn't affect anything because it's only done in the end). The way I solved this was keeping only the highest sum op for every skill in the priority queue and updating factors when needed.

The solution is not a "greedy" topological sort of the graph. You can also remove nodes that have non-zero in-degree but after their removal, the connected component they are part of must remain connected. So you should greedily remove nodes that don't affect "connectedness".

first person can take 0, 1, 2, 6, 9 he will choose 9

second person can take 0, 1, 2 he will choose 0

first person can take 1, 2, 4 he will choose 4

second person can take 1, 2 he will choose 1

first person can take 2, 6 he will choose 6

second person can take 2, 3 he will choose 2

first person can take 3, 7 he will choose 7

second person can take 3, 8 he will choose 3

first person can take 5, 8 he will choose 8

second person take the remaining 5

so the result will be 9041627385 % 1000000009 = 41627304

explained already!! http://codeforces.me/blog/entry/16707#comment-215954

Try n=3, m=7.

That code goes 3 -> 6 -> 5 -> 4 -> 8 -> 7, when in fact it is better to go 3 -> 2 -> 4 -> 8 -> 7.

I thought Problem B and D are very similar, so I don't understand your claim.

It should have been mentioned that Vasya and Petya are cosmonauts working on this experiment in zero-gravity conditions.

Ok man, at least you didn't walk up to the computer screen at 2 AM in the morning, and see that all problems but E are math.

Man you have no idea how I felt after that -__-, and you're complaining about 1 problem.

There needs to be more diversity in CF rounds, you can't just make 4/5 problems math, or dp, or whatever. It's just not interesting when you do that.

You know, when I was solving this problemset — I was actually happy that problem B was 2D instead of 3D)

Well. I feel like I should reply something.

Regarding problem B, I don't feel like this problem stands out from the problemset in a bad way. It probably didn't feature wonderful insights, but I like this problem too; if I would have created this problem, I wouldn't hesitate to include it in some of my rounds.

The statement might not be in the best shape, I must agree. However, this is quite certainly not savinov's fault. The point is that the problems were prepared collectively, with me being the lead of the process. We decided to change the problem B in the last moment due to unforeseen circumstances (basically, it turned out that the former problem B was featured in some contest earlier), and savinov kindly provided his problem. It might have had some issues, but then again, every problem has issues until it is triple-checked by different people. So, plainly, it's my fault that the problem didn't get the attention it deserved.

The strings you provided don't attain the maximum value. Have you tried computing the value p(s, "GGGGGGGGGGGGGGG")?