Hello.
I have a problem and I don't know how to solve it. if it is possible to give me hint for start or type of algorithm, etc, I will solve it. Thanks.
We have array $$$A$$$ with $$$n$$$ elements: $$$A[1], A[2], A[3], ..., A[n]$$$ ($$$1 \le A[i] \le 10$$$) ($$$1 \le n \le 1000$$$)
A $$$k$$$ is given beside elements of array. ($$$0 \le k \le 10n$$$)
We define $$$risk = 0$$$.
for each $$$i$$$, if $$$A[i - 1] > A[i]$$$, then $$$risk += A[i - 1] - A[i]$$$
for each $$$i$$$, if $$$A[i + 1] > A[i]$$$, then $$$risk += A[i + 1] - A[i]$$$
we want to $$$risk <= k$$$.
we can reduce one or increase one $$$A[i]$$$ at one step. so $$$risk$$$ will be calculated again. What is minimum steps need to achieve $$$risk <= k$$$?
Example:
in:
2 1
1 10
out:
8
in:
3 2
10 1 10
out:
8

Is it possible to help me? Thanks so much.

Hi.
I want to solve a question. I know how to solve it but I want a better way to solve it. in first line number n is given and in second line, n numbers is given. We call value of i-th number as P_i. For the i-th number and j-th number, if (i - j) (P_i - P_j) < 0 is true, then there is edge between i and j in graph. (graph is undirected)
We want to find connected component of graph and print vertices in each connected component.

Input 1:
4
2 3 1 4
Output 2:
2
3 1 2 3
1 4
(output: print number of connected component, then each line, first print number of vertices in that component, then print vertices in increasing order)

Memory limit: 128MB
Time limit: 1 second
1 <= n <= 1000000

I noticed that the property, is property for checking inversion in an array. However the nlogn approach is only for count inversions but if I want to find them, then I need linear search in merge each time and so,my algorithm is not nlogn anymore.
There is two approach for find components. one of them is DFS and other is Disjoint set how every we want to print connected component so I thick that I couldn't use Disjoint set.
because of time limit and memory limit, I didn't know a best way.
Is it possible to help me or give me a idea?
Thanks.

Hi.
I'm sorry. I have a question but I couldn't solve it. it doesn't belong to codeforces. In this question, we have a n * n matrix and we want to go from (1,1) to (n,n). we only can move left, right, up, down. but there is a special tag on some cells. if we are in a cell and there is a special tag around us (I mean 8 side of a cell), we can move directly to that. Question guaranteed that each row and each cell contain exactly one tag.
We want to find minimum move to go from (1,1) to (n,n).
Question give information in special way. for example:

Input 1:

3  
1 2 3

Output 1:

2

Input 2:

4
2 3 1 4

Output 2:

4

in first row, n will given. in next row, n numbers will given. The i-th number mean which row in i-th column contain tag. range of n is 1 <= n <= 300000.

memory limit is 256Mb
Time limit is one second

I think solution is dynamic programming (dp). Because of memory limit , we can't construct a 2D array for out dynamic programming but because we always need just two last state, I only use 3 array for dp. It solves memory limit however time limit is one second and my dp algorithm which calculate all way, failed. it is a simple dp. it calculate 3 state (go down, right and diagonal for special tag). Is it possible to give me a better way?
I'm sorry for bad English. Thanks.

Hi.
There is a problem but I didn't find it in codeforces. If you can help me to find it and solve it.
There is n cities and m road between them. roads are two-way. Capital is city z. We define city x critical for city y if all the ways for going from z to y, contain x. If we want to find that x is critical for y or not, an easy way is to use dfs to find that is there any way from capital to y or not. then do another dfs but x removed from graph (avoid dfs from going to x). based on this two dfs, we can understand that x is critical or not for y.
However in this new problem we want to find number of critical cities. (all x and y). However I don't remember that there is a capital or not. if there is no capital, then we must try all z too. If we do last idea, there is a time limit. I want a better way.

I didn't found problem in codeforces but I know that exists in codeforces, I just don't save it!
Is it possible to help me?
I'm sorry for bad English. Thanks.