My solution to 1839D Ball Sorting

Правка en11, от _Shivom_, 2023-07-29 11:04:46

The Problem In Discussion is : https://codeforces.net/contest/1839/problem/D

Observations:
- The solution will be decreasing.
- Say you place some zeroes then each zero removes some contiguous subarray, the 0 is present in this subarray and subarrays of two zeroes don't overlap.
- A subarray that zero removes, give cost equal to the number of elements in the subarray.
- Now it is equivalent that each zero is present in the starting of the subarray that it is removing.
- So this can be solved with dp.
- This problem is very identical to LIS.
- In fact answer for the last query is always n — size_of_lis of the array.

State of dp
dp[i][k][2]:
1. dp[i][k][0] -> minimum no of removed elements upto index i such that you have used k zeros and i'th element is not removed.
2. dp[i][k][1] -> minimum no of removed elements upto index i such that you have used k zeroes and i'th element is removed.
'
Transitions:
1. If we are removing the i'th element, and we have used k zeroes, then, we are talking about dp[i][k][1], the transition would be :
— that we removed the (i-1)th element and we did it in k zeroes so we can continue the removal so dp[i][k][1] be dp[i-1][k][1] + 1 (as we removed the i'th element)
— that we didn't remove the (i-1)th element, so we have to place a zero just before the i'th element so we can remove it. So dp[i][k][1] = dp[i-1][k-1][0] + 1 .


2. If we are not removing the i'th element then we will find a previous element that we have not removed and
that element must be less then i'th element. (Because we have to maintain the sequence in increasing order).
So for all x < i, such that v[j] < v[i] we can say dp[i][j][0] = dp[x][j-1]][0] + (i-x-1 (this term is no. of elements between x and i)).
— there is a special case if i-x-1 is zero means that x is just the prev element of i, then we don't have to give j-1 zeroes before the x th index. so we can say dp[i][j][0] = dp[x][j][0].

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский _Shivom_ 2023-07-29 12:57:39 2 Tiny change: 'that ```v[j] < v[i]``' -> 'that ```v[x] < v[i]``'
en17 Английский _Shivom_ 2023-07-29 11:17:29 10 Tiny change: 'such that v[j] < v[i] we can sa' -> 'such that ```v[j] < v[i]``` we can sa'
en16 Английский _Shivom_ 2023-07-29 11:15:13 0 (published)
en15 Английский _Shivom_ 2023-07-29 11:14:44 78
en14 Английский _Shivom_ 2023-07-29 11:13:12 51
en13 Английский _Shivom_ 2023-07-29 11:11:42 11 Tiny change: 'dp**<br>\ndp[i][k][2]:<br>\n1. d' -> 'dp**<br>\n```c++\ndp[i][k][2]:```<br>\n1. d'
en12 Английский _Shivom_ 2023-07-29 11:10:33 506
en11 Английский _Shivom_ 2023-07-29 11:04:46 598
en10 Английский _Shivom_ 2023-07-29 10:58:47 539
en9 Английский _Shivom_ 2023-07-29 10:52:48 396
en8 Английский _Shivom_ 2023-07-29 10:49:35 2 Tiny change: 'ray that is is removi' -> 'ray that it is removi'
en7 Английский _Shivom_ 2023-07-29 10:48:49 444
en6 Английский _Shivom_ 2023-07-29 10:41:11 8 Tiny change: 'ervations:\n* The ve' -> 'ervations:<br>\n* The ve'
en5 Английский _Shivom_ 2023-07-29 10:40:59 61 Tiny change: 'ervations:' -> 'ervations:\n* The vector of solution will be a decreasing sequence.'
en4 Английский _Shivom_ 2023-07-29 10:40:17 4
en3 Английский _Shivom_ 2023-07-29 10:39:52 46
en2 Английский _Shivom_ 2023-07-29 10:26:24 20 Tiny change: '/problem/D' -> '/problem/D <br>\nObservations:'
en1 Английский _Shivom_ 2023-07-29 10:25:25 151 Initial revision (saved to drafts)