Maybe that he tell you how to solve these problems will be better.

Да он все равно потухнет

What a D problems!
0 Accepts for D in div2
1 Accepts for D in div1

Who's graph?
Me?!

"Score distribution will be announced soon." Soon = 2 minutes before start ? :|

Зашёл в тему, чтобы написать такое же сообщение.

You Misunderstood the question :D Read it again.

I looked my code many times and I couldn't find my bug. Damn it!!!

I'd guess something like:

3
aba
bcc
ccc

(answer should be FIRST)

I think it's something that stops solutions (like mine, that I couldn't fix in time) that don't account for the fact that the same string can be made by multiple correct paths. Like, if you make the state of the game a position on the board, the choices are to go right or down. But since the game is played with strings, not (directly) with paths, there can be more than two valid moves from a given state. (sorry if confusing)

you can see that after the contest !!!!!

в E динамика dp[построенный суффикс числа][сколько переходит в следующий разряд — от 0 до 5]. Отдельно считаем, какие суммы можно получить из 6 чисел из множества {0, 4, 7} и потом этот подсчет используем в динамике

Можно делать перебором с запоминанием: функция go(x) пытается перебрать, сколько четверок и семерок мы ставим в последний разряд, и запускается от числа (x - 7a - 4b) / 10, если это число делится на 10.

Либо у меня кривые руки, либо бин.поиск там не подходит, ибо никто не говорил, что функция получится монотонной.

Yups, and in both divisions : )

Указывай дивизион хотя-бы, а то не очень понятно

У меня ретроанализ, по состоянию мы в такой диагонали и наши строки кончаются в такой маске позиций доски. Чтобы работало быстро сначала предподсчитаем все достижимые состояния. А памяти 170 метров — 2*20*(1<<20) интов, хотя вообще там реально состояний пару миллионов.

nevermind

Вроде нас только разность волнует, храним ее в значении ДП. Если заранее клетки пронумеровать, не так все сложно получается.

Кстати, суммарное количество состояний будет не O(n2ⁿ), а O(2ⁿ), потому что сумма геометрической прогрессии по диагоналям.

Вместо состояний колово ашек и бшек можно считать динамику количество ашек минус количество бшек.

Через несколько минут, сейчас идёт системное тестирование.

I think some pre-operation can change the order to O(nlog n).

the solution will look like L L L . . L R . . R R R

check the solution for each possible combination of Ls and Rs

The solution for any combination =

L*(number_OF_L) + R*(number_OF_R) + (QL or QR * abs(n-2*number_OF_L)-1)

take the best

I spent the whole time trying to find a dp equation for it but it actually is a simple simulation question. Answer to the problem is MIN(all weights from right arm , first from left arm and rest from right arm, first and second from left and rest from right and so on until all from left arm).

Take the case when we pick first and second from left arm and rest from right arm.Here, we get the minimum when we take w1 from left, w(n-1) from right , then w2 from left arm and then w(n-2) followed by rest from the right.This will remove the 2*qr overhead from the last 2 weights in the right and so on for the rest of the cases. Hope it helps!!

You have to choose some index i (0 <= i <= n), such that the robot takes all the items <= i with the left hand, and all items > i with the right hand.

The cost of taking the items, will be l * sum of weights of items <= i + r * sum of weights of items > i. Additionally, by choosing i, the robot takes i items with the left hand and n-i items with the right hand. If he takes the same number of items with each hand, or one more with the left/right hand, it's possible to alternate taking the objects. Otherwise, the additional cost for repeatedly taking items with one of the hands will be Ql * max(0, i — (n-i) — 1) + Qr * max(0, n-i — i — 1).

If you precompute the cumulative sum of all weights in an array, you will be able to find the cost of choosing i in O(1), and you just need to find the minimum cost for 0 <= i <= n.

C 30-ого на 700 опустился:)

С 1027-го до 868)))

And only 1 person in Div 1 solved problem D too? I think the problem setter should have put the 2 Ds in H position!

A x492
B x37
C x127
D x1
E x137

I think that's unfair for those who just haven't read E on time. Maybe the authors meant some complicated solution instead of 3d dynamic programming?

4769568 Nice solution for C div2

В комментариях выше есть ответ.

оно будет описано в разборе

Read the huge discussion above -- you understood the problem wrong.

it's not a simple game on the board — it's game with strings. After each move the string is fixed not the position an the grid. So in the test 4 after second move players have string "cb" and the next move for the first player is string "cba" — this is correct string and so the final string is "cbaaaaaac"and the first player win.

The player are not moving on the board but are actually constructing strings & checking whether they are "good". For the 4th Test case:
5
cbbbb
bcbbb
aacbb
aaacb
aaaac

• In the first turn, FIRST chooses "c" since this is only good string available.
• Then, SECOND chooses "b" again because this is the only possible good string of length 2.
• Now, in the third turn, FIRST looks for the paths with the current string on the board. It find two paths one horizontally left & other vertically down. On horizontal, she has choices "b" & "c". On Vertical path, she has choices "c" & "a". She chooses "a" because subsequently it would lead to her victory. .
  .
  the game continue
  .
  .
  Finally the string is cbaaaaaac if both play optimally & hence "FIRST" wins. Hence, this is the correct answer. Hope this helps to understand the problem. I also missed this point and got a WA.

There are one object with weight 93

if your robot use left hand, the cost will be 93*78=7254

if your robot use right hand, the cost will be 93*94=8742

the minimum cost is 7254, but your output is 0.

он причем единственный, кто решил D Div1

Меня в очередной раз порадовал сюжет "мама решила подарить сыну массив" :)

:)
(for those intrigued, as I was: WA on test 7)

It was trying to prevent you from that hack but didn't succeed!

Просто автор не хочет меня расстраивать :)

1. Скорее всего завтра.
2. Обычно обновляется через час после контеста.

X is a valid GCD if for each a_i we have n_i * X <= a_i <= n_i*X + k for some numbers n_i. For each value of X we can try each possible multiple of X, and count how many elements in the array are in the range [n_i*X,n_i*X+k] by using an array d[p] = number of elements in the array less than p. We simply pick the greatest X for which all elements a_i were inside the ranges of X's multiples.

If we check every X (2<=X<=1000000) and its multiples (1 <= n_i*X <= 1000000), we make around 10^7 constant time queries. This is fast enough to pass the time limits.