My Favorite Problems

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	150

It's a post recording problems that I think is helpful to MY problem solving ability.
Caution: May NOT fit your appetite!
2B - Наименее круглый путь
3D - Скобочная последовательность
Chinese solution
5C - Наибольшая правильная скобочная подстрока
7B - Менеджер памяти
7D - Палиндромность
Finding longest palindromic substring using Manacher's algorithm in O(n)
9D - Сколько деревьев?
dp[i][j]: i nodes with height less than j, dp[i][j] = sum{dp[k][j-1] * dp[i-k-1][j-1]}(Choosing number k+1 as the root node)
12D - Бал
Binary Indexed Tree. A 2D version can be found here
13C - Последовательность
13E - Лунки
Divide array with length n into sqrt(n) consecutive blocks
14D - Два пути
Very good problem, reference
14E - Верблюды
reference
16E - Рыбы
Conditional probability
18D - Продавец Вася
recommended solution 253348
18E - Флаг 2
dp[level][colorA][colorB], so dp[level[i][j] = change + min(dp[level-1][ii][jj] (i != ii && j != jj), where change means differences between original level-th row and new 'ijijiji...ijij..' row. Time complexity is O(n*26*26*(m+26*26))
19B - Кассир
Tricky 0-1 knapsack problem.

Комментарии (3)

Написать комментарий?

Dixtosa

11 лет назад, # |

← Rev. 2 →

http://codeforces.net/contest/126/problem/B

& http://codeforces.net/contest/57/problem/C

→ Ответить

cdschenshuai

11 лет назад, # ^ |

Thank you so much for your recommendation, I'll have a try later

CountZero

+13

"Snow White and N dwarves" (Russian Code Cup 2013 Final, problem B)

Snow White has N friend dwarves numbered from 1 to N. The height of i-th dwarf is h_i; 1 ≤ h_i ≤ N

Princess calls any nonempty subset s₁... s_m of these dwarves sympathetic if the following condition holds:

$\text{[math]}$

There are T test cases, each contains N — the number of dwarves and N integers h_i — heights. For each test case, you have to print any sympathetic subset in the same format, or -1 if there is no solution.

Total N does not exceed 10⁶

Time limit 2s, memory limit 256Mb

Example:

Input

1
5
3 4 1 2 2

Output

4
1 2 3 4

140Mb archive containing all tests, checkers, author solutions, etc: here (folder "equality")

Блог пользователя cdschenshuai