My solution to 1839D Ball Sorting

Правка en9, от _Shivom_, 2023-07-29 10:52:48

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.

История

 
 
 
 
Правки
 
 
  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)