UpAndDown's blog

By UpAndDown, history, 4 weeks ago,

Hello Codeforces,

I have prepared a mashup. It'll take place on Thursday at 17:35 (UTC+3). You will be given 7 problems and 2 hours and 15 minutes to solve them.

I did my best to do this problems:

Challenging, interesting, only in A algorithms and data structures aren't used.

With clear statements

Available in Russian and in English

Difficulties are 800-1600-1700-1700-1800-2000-2400

UPD: The registration is opened now.

Congrats to MarioPariona117 and pavlovoleg4889 for solving all the problems!

• +11

 » 4 weeks ago, # |   0 Can someone tell, how to implement C in less than O(n^2)? The brute force would be for the current range pick the minimum, subtract it from a and add that to b. Am I right?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Use sparse table to calculate the minimum. The preparation will take O(n log n). Then just cover the maximal possible ranges with segments. Code#include using namespace std; int st[200000][20], sti[200000][20], a[200000]; int n; pair rmq(int l, int r) { int j = __lg(r - l + 1); return st[l][j] < st[r - (1 << j) + 1][j] ? make_pair(st[l][j], sti[l][j]) : make_pair(st[r - (1 << j) + 1][j], sti[r - (1 << j) + 1][j]); } string solution = ""; int solve() { queue>> q; q.push({0, {0, n - 1}}); int ans = 0; while(!q.empty()) { auto [delta, p] = q.front(); auto [l, r] = p; q.pop(); auto [mn, i] = rmq(l, r); if(delta != mn) { ans++; solution += to_string(l + 1) + " " + to_string(r + 1) + " " + to_string(mn - delta) + "\n"; } if(i > l) q.push({mn, {l, i - 1}}); if(i < r) q.push({mn, {i + 1, r}}); } return ans; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &(a[i])); st[i][0] = a[i]; sti[i][0] = i; } for(int j = 1; (1 << j) <= n; j++) for(int i = 0; i + (1 << j) <= n; i++) st[i][j] = st[i][j - 1] < st[i + (1 << (j - 1))][j - 1] ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1], sti[i][j] = st[i][j - 1] < st[i + (1 << (j - 1))][j - 1] ? sti[i][j - 1] : sti[i + (1 << (j - 1))][j - 1]; cout << solve() << "\n"; cout << solution; return 0; } 
•  » » » 4 weeks ago, # ^ |   0 Thanks!
•  » » 4 weeks ago, # ^ |   +3 I implemented C using stack. In stack there are elements always in increasing order. When you add element that is smaller than top element, you erase all elements from stack that are greater than should be.For example, let $a = [1, 5, 7, 2, 4]$.Step $1$: $s = [1]$, $b = [0, 0, 0, 0, 0]$Step $2$: $s = [1, 5]$, $b = [0, 0, 0, 0, 0]$Step $3$: $s = [1, 5, 7]$, $b = [0, 0, 0, 0, 0]$Step $4$: $s = [1, 5, 7]$, you pop last element($7$) and add $2$ to the range $[3, 3]$. Now $b = [0, 0, 2, 0, 0]$Step $5$: Now $s = [1, 5]$. Then you pop last element again ($5$) as it is greater than $2$ and add 4 to the range $[2, 3]$. Now $b = [0, 4, 6, 0, 0]$.Step $6$: Now $s = [1, 2]$ and $b = [0, 4, 6, 0, 0]$.Keep going like that and you will construct the array. Time complexity: $O(n)$.
•  » » » 4 weeks ago, # ^ |   0 Can you explain how are you deciding the range to which we add, like in step 4 you said, add 2 to the range [3, 3]. Why is that?
•  » » » » 4 weeks ago, # ^ |   +3 We add to the range from element of top of the stack (in this case $7$, index $3$) to the element in which we are currently in (in this case $2$, index $4$) minus 1. In step $4$ we add 2 to the range $[3, 4)$.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by UpAndDown (previous revision, new revision, compare).