I’m trying to solve this problem using DP(2D, like we do for the knapsack problem). But I think my solution will get a TLE because of high constraints. I wanted to know if we can optimize the DP solution in some way?
I don’t think you can. The constraints are too large.
The constraints are indeed too big for 2D DP and a standard knapsack solution and I think it will be hard to optimize if you are starting from the wrong point.
Let’s say for optimal answer, we have x applications with 1 convenience points. Now, it is obvious we’d choose x applications greedily. Let l be numbers of applications with convenience 1. For each 1<=x<=l, we can get memory freed by removing x applications using prefix sums of ( array of apps with 1 convenience points in non-increasing fashion ). For the memory which is left, we can again choose greedily from apps having 2 convenience points. This can done by binary search over the prefix sums of ( array of apps with 2 convenience points in non-increasing fashion ).
Complexity- O(N \cdot Log(N))
To be honest, I wasn’t expecting this to work considering this was a Codeforces D, but a straight forward greedy without binary search and anything else, worked for me.
Approach:
Make two arrays of type 1 and type 2. Sort them in decreasing order each. Use two pointers one for array1 and second for array2, keep selecting greedily out of the two choices unless you make the desired sum. At last, keep removing type 1 items from the selected items until the sum is still greater than required.
Also, particularly in this contest, the E problem was more easier than even C and D, atleast for me.
Thanks a lot!
Thanks!!
here is the binary search way to find the optimal answer, Codeforces Round #697 (Div. 3) Problem D:Cleaning the Phone - YouTube check this out if you want to.
Thanks a lot for the video.
you have used binary search twice in the video but can we like get the ans just by doing it once ?
According to the question , n must be represented as :-
n = px + qy , where x is 2020 and y is 2021 and p,q are integers that can vary starting from zero.
Now , take q to the left hand side and remaining terms on the right hand side , you will get ,
q = (n - p*x)/y
Now iterate p from zero upto that value that makes numerator always greater than zero for the above expression , and if for any valid ‘p’ if the numerator is divisible by y then there also exists a valid ‘q’ which clearly proves that n can be represented as some multiple of 2020 and some multiple of 2021.
Thank you I understood it now, well explained.
Yes, why not.
We can perform binary search on any of the prefix sum array of convenience points after it is sorted in non-increasing order.
Link to Solution of D(Cleaning the Phone)
Click here for Explanation
If you identify the pattern, the problem becomes really easy.
Approach:
If any number divided by 2020 gives quotient n, then the numbers generated by sum of 2020 and 2021 will have the remainder of minimum 0 and maximum n (coz you can add 1 a maximum of n times - all 2021s).
Try with pen and paper, the pattern can easily be found.
Time complexity: O(1)
t=int(input())
for i in range(t):
n=int(input())
t=n//2020
r=n%2020
if(r<=t):
print("YES")
else:
print("NO")
Honestly, That was an amazing O(1) solution. Sorry for bothering you again but can you please share your thought process of how you came up with such an elegant solution in contest ?
Possible numbers that can be formed:
2020,2021
4040,4041,4042
6060,6061,6062,6063
8080,8081,8082,8083,8084
…
Do you see the pattern now?
If you just write first three possibilities, you would have easily cracked it, a pen and a paper is all it takes.
Ah… I see it now, thanks a ton for your help, I was banging my head on this since 2 hrs, highly appreciated.