We are given a sequence A of length N, and a linear equation y = k \cdot x + b. We should find the longest subsequence B in A such that there is an order of B in which B_{i+1} \geq k \cdot B_{i} + b, for all possible i's.
Explanation:
The problem can be solved using a simple greedy approach. The first observation we need to do is k \geq 0, which means the function y = k \cdot x + b is always nondecreasing. That is, for two numbers x_{1} and x_{2} where x_{1} \leq x_{2}, y_{1} \leq y_{2} holds.
From here we get an insight that it is always better to take the smallest A_{i} as the first element of the sequence B because the smaller element gives more chance for choosing the next element of B. To get the longest subsequence we should continue in this manner. We can apply the same thing to the elements of A which are \geq k \cdot last(B_{i}) + b to choose the next one.
To implement this idea: first, we need to sort the sequence A. After that, we take the first element of A as the first element of B and always keep track of the y value of the last taken element in order to be able to look for the next valid element.
@square_root_pi because his total time to solve all the questions was lesser than other participants who solved all the 5 problems even after 1 wrong submission , 1 wrong submission just means a 20 minutes penalty and nothing more than that.
Btw you can check the time for each problem yourself if you use the Chrome Dev tools. Open RankList,Press F12, Go to networks tab, clear everything, and reload the page. You should find the one that is making an API call and fetching all the ranks along with their time.
@vivek_1998299@square_root_pi ACM rankings are scored by the number of problems solved, with a tie-breaker over the sum of times over all problems, with penalty time (in this case 10 min) for every failed solution. Gennady had the lowest sum of times, even with the penalty.
The total time is calculated as the sum of time from start for each problem,i mean lets say if there were 3 problems and i submitted all after 1:30 hour then my total time is 3*90=270,while lets say someone else submitted like 0:10,0:30,2:00 then his total time is 120+30+10 = 160 so even if he submitted late he won
(I also got to know abt this in icpc where we just messed up due to this rule)
I have solved it using the same algorithm. But gained a time limit exceeded verdict. I can see other Java solutions even using a scanner getting accepted.
Your idea is correct. Note that prev can’t be used as an index directly, you can use binary search to solve this.
You just have to solve the k=0 case separately.
