My solution to 1839D Ball Sorting

Revision en10, by _Shivom_, 2023-07-29 10:58:47

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 .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English _Shivom_ 2023-07-29 12:57:39 2 Tiny change: 'that ```v[j] < v[i]``' -> 'that ```v[x] < v[i]``'
en17 English _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 English _Shivom_ 2023-07-29 11:15:13 0 (published)
en15 English _Shivom_ 2023-07-29 11:14:44 78
en14 English _Shivom_ 2023-07-29 11:13:12 51
en13 English _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 English _Shivom_ 2023-07-29 11:10:33 506
en11 English _Shivom_ 2023-07-29 11:04:46 598
en10 English _Shivom_ 2023-07-29 10:58:47 539
en9 English _Shivom_ 2023-07-29 10:52:48 396
en8 English _Shivom_ 2023-07-29 10:49:35 2 Tiny change: 'ray that is is removi' -> 'ray that it is removi'
en7 English _Shivom_ 2023-07-29 10:48:49 444
en6 English _Shivom_ 2023-07-29 10:41:11 8 Tiny change: 'ervations:\n* The ve' -> 'ervations:<br>\n* The ve'
en5 English _Shivom_ 2023-07-29 10:40:59 61 Tiny change: 'ervations:' -> 'ervations:\n* The vector of solution will be a decreasing sequence.'
en4 English _Shivom_ 2023-07-29 10:40:17 4
en3 English _Shivom_ 2023-07-29 10:39:52 46
en2 English _Shivom_ 2023-07-29 10:26:24 20 Tiny change: '/problem/D' -> '/problem/D <br>\nObservations:'
en1 English _Shivom_ 2023-07-29 10:25:25 151 Initial revision (saved to drafts)