When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ProblemAsker's blog

By ProblemAsker, 3 years ago, In English

Input: array A[] of length N (1<=N<=400) , K (1<=K<=400)

In one move : you can remove any subarray size at most K which all element in it are the same

Question: Find minimum number of moves to make array empty.

It’s from my past OI problem and editorial said it use Matrix Chain Multiplication DP, but I can’t come up with it.

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By ProblemAsker, 4 years ago, In English

I saw it publish now at lulu, What are your thought about it? Should i buy it?

Thank you.

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

By ProblemAsker, history, 4 years ago, In English

There are n*m matrix (n,m<=1000) each element in the matrix are between 1 and 1e9 Count number of all rectangle in matrix that contain all the same element

how to solve this? I have been thinking for 2 days. Thank you very much.

Example:

Input:

2 3

1 1 2

1 1 2

output : 12

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By ProblemAsker, 4 years ago, In English

Problem Statement:

Given two strings a,b of length m and n (1<=m,n<=1000) which only contains 'A' and 'B' letters, there are k<=100 queries.

For each query: Given string S of length m+n, check if this string can be form by string a,b by keeping their original order.

(let's a = {x0,x1,x2,...,xm} , b = {y0,y1,y2,....,yn} ; S may be {x0,x1,y0,x2,y1,y2,x3,...} or something like this : position of x0<x1<x2<...<xm and position of y0<y1<y2<...<yn)

More formally: string a and b must be subsequence of string S which doesn't use the same postition of S twice.

For example:

let a = "BAB" , b = "AB" ==> Posible string S is "BAABB" ,"BABAB", "ABBAB" but not "BBABA"

how to solve this problem? I think it's dynamic programming problem. Thank you very much in advance.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By ProblemAsker, 4 years ago, In English

Problem Statement:

given string S of length N (N<=2e5) , find smallest string by length which is a pattern of S (this string can be equal to string S by append it in some positive integer times)

For example:

Input: abcdabcdabcdabcd ==> Answer: abcd

Input: aabbaabbaabbaabb ==> Answer: aabb

Input: aaaaaaaaaaaaaaaa ==> Answer: a

Input: codeforces ==> Answer: codeforces

how to solve this in nlogn time? thank you very much in advance.

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it