- I met this problem as a subproblem many times and tried to find a solution for it but failed ,So I make an elegent statement for the problem asking for someone's help :
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
In the last Codeforces Round 878 (Div. 3) I was trying to solve problem B using count subset sum function . 208751901
By generating a vector containing all the powers of 2 ,and search for how many different subsets such that their sum is less than or equal value k. It uses backtracking to explore all possible combinations of including or excluding each element in the subset. But as expected it gives me TLE as its time complexity is equal to (2^N) Each recursive call further branches into two recursive calls until the base cases are reached , This doubling effect results in an exponential time complexity. I am not exactly asking about problem B as I have already solved it . I am asking about how to implement this function with less time complexity using DP maybe O(n) , O(n^2) or even O(n^3) .
I am very sorry about this but it is clear that there are some problems from the latest contests whose solutions are offered for free on YouTube, and this has intensified recently, especially in the last 3 div2 contests and solutions to C,D problems have been published, and this exhausts a lot for the contestants under the rating of 1200 and 1300 , I will not paste the channel link so as not to spread more, but I hope that you will suggest me how to report these cheaters to codeforce officials to take strict action against them .
Name |
---|