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.

• +12

By ProblemAsker, history, 5 months ago,

Problem: Given n cities, m edges, each edge connect node U_i-V_i with distance W_i and you get happiness-value C_i each time you travel this edge , you want to travel from city s to city t within distance not exceed than K. What is the maximum happiness value you can get? (note that you can visit any city more than once)

Constraint: N<=300 , M<=5000 , K<=2000

(I have tried dijkstra solution that dp[i][j] denote the maximum happiness value that you can get in city 'i' within distance 'j' but it gave me WA. Can you explain why??)

• +1

By ProblemAsker, history, 5 months ago,

• 0

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

Thank you.

• +48

My friends always confused almost all the time when i explained my solution to some random problem that we are practice even our level is the same.

How do you explain some complicated solution to your friends? Do you have any tip and tricks? Thank you very much in advance.

• +1

By ProblemAsker, history, 10 months ago,

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

• 0

By ProblemAsker, history, 11 months ago,

Problem statement:

There are N<=1e5 ordered-pairs (x1,y1),(x2,y2),(x3,y3),...,(xN,yN) with all different value

( if i!=j then x[i]!=x[j] and y[i]!=y[j] ) , 1<=x[i]<=1e5 , 1<=y[i]<=1e5

task: find total sum of x[i]+x[j] for all 1<=i,j<=N if(i!=j and x[i]>x[j] and y[i]<y[j])

For example:

Input:
N=4
{1,4}
{3,2}
{7,1}
{10,100}

Output:
22


(there are {(1,4),(3,2)} , {(1,4),(7,1)} , {(3,2),(7,1)} ==> sum=(1+3)+(1+7)+(3+7)=22

thank you very much in advance.

• 0

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.

• +3

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



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

• +9

Problem statement : Given unsorted array A of length N , there are Q queries

For each queries : Find number of element in range L to R which it's value is in range X to Y

Constrant: N<=2e4 , Q<=2e5 , 1<=L<=R<=N , 1<=X<=Y<=2e9 , 1<=a[i]<=2e9

I know this problem can be solved using segment tree, but can this problem be solved using other techniques? maybe sqrt decomposition and how?

Thank you very much in advance.