### TuHoangAnh's blog

By TuHoangAnh, history, 4 weeks ago,

you are given an array A of $n$ positive integers ( $0<A[i]<10^9$ ) and $r$ moves.

on each move: you can choose any subarray of A (which contains only positive elements) and decrease all elements in that subarray by one.

your task is to maximize the number of $0$ values in your array.

print that number after $r$ moves.

input:

• $n,r$

• $A[1],A[2],..A[n]$

ouput:

• number of $0$ values after r moves

example input:

$6$ $2$

$0$ $2$ $1$ $2$ $2$ $3$

output

$4$

• subtask1: $n<=10;r=1$
• subtask2: $n<=10;r<=5$
• subtask3: $n<=200;r<=200$
• subtask4: $n<=200;r<=10^9$
• subtask5: $n<=2000;r<=10^9$

• 0

By TuHoangAnh, history, 2 months ago,

recently, i want to practice on http://www.usaco.org/index.php. But i cant create an account because of the Gmail Delivery Issues, can anyone help ?

• -4

By TuHoangAnh, history, 3 months ago,

in this problem 1682B - AND Sorting, with the input:

1

8

0 1 2 7 4 5 3 6

it seems like the answer is not correct, if im wrong, pls point out my mistakes.

• -13

By TuHoangAnh, history, 5 months ago,

given an integer $n$, find the number of $(i,j,k)$ so that:

$1<i<j<k<=n$.

$i*j*k$ is a perfect square.

$3<n<=10^5$

• -5

By TuHoangAnh, history, 5 months ago,

given an array consists of $n$ integers and an integer $p$, find number of pair($i,j$):

so that $i<j$ and $(a[i]*a[j])$ $mod$ $p$ $=$ $(a[i]+a[j])$ $mod$ $p$

$n<=10^5$

$1<p<=10^9$

• +6

By TuHoangAnh, history, 6 months ago,

there are n piles of coin, the i'th pile has A[i] coints. Alice and Peter want to play a game. They play alternatively, on each move, they can remove some coins from any piles.The winner is the last person to remove all coins from the last pile. in the begining, they can know who is the winner, so the loser will maximize the number of moves and the winner will try to minimize it. Printf the number of moves if both players play optimally.

• -9

By TuHoangAnh, history, 6 months ago,

given an undirected graph, you have to remove some nodes to maximize the number of connected components.

when removing a node, you have to remove all its edges.

• +12

By TuHoangAnh, history, 7 months ago,

given an integer $n$, you have to find $a,b>0$ so that $a+b=n$ and $LCM(a,b)$ is maximum($LCM$ is the least common multiple of $a,b$).

printf the maximum $LCM(a,b)$

i have come up with a bruteforce solution. I will consider all pairs of $a,b$ that have sum equal to $n$. And calculate the value of

$LCM(a,b)=(a*b)/GCD(a,b)$. ($GCD$ is greatest common divisor).

But, this solution seems too slow when $n<=10^9$. Is there a better solution for this problem ?

• +3

By TuHoangAnh, history, 7 months ago,

given 2 intergers $N,M$.

you have an array of $N$ integers and $M$ queries. Each query has 2 types:

type "1": $1$ $pos$ $val$ (change the value at position $pos$ to $val$)

type "2": $2$ $l$ $r$ $k$ (printf the value of the minimum element in range [l,r] that's not smaller than $k$)

i used segment tree with multiset to solve this problem, i'm wondering why my code got WA.

here is my code:https://ideone.com/6DtYsJ