cdschenshuai's blog

My Favorite Problems
By cdschenshuai, 11 years ago, In English

It's a post recording problems that I think is helpful to MY problem solving ability.
Caution: May NOT fit your appetite!
2B - The least round way
3D - Least Cost Bracket Sequence
Chinese solution
5C - Longest Regular Bracket Sequence
7B - Memory Manager
7D - Palindrome Degree
Finding longest palindromic substring using Manacher's algorithm in O(n)
9D - How many trees?
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 - Ball
Binary Indexed Tree. A 2D version can be found here
13C - Sequence
13E - Holes
Divide array with length n into sqrt(n) consecutive blocks
14D - Two Paths
Very good problem, reference
14E - Camels
reference
16E - Fish
Conditional probability
18D - Seller Bob
recommended solution 253348
18E - Flag 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 - Checkout Assistant
Tricky 0-1 knapsack problem.

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

"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 hi; 1 ≤ hi ≤ N

Princess calls any nonempty subset s1... sm of these dwarves sympathetic if the following condition holds:

There are T test cases, each contains N — the number of dwarves and N integers hi — 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 106

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")

→ Reply