CARRAY - Editorial

Problem Link:

Practice

Contest

Setter: Misha Chorniy

Tester: Ke Bi

Editorialist: Rashad Mammadov


Difficulty:

SIMPLE

Prerequisites:

Greedy Algorithms, Sortings

Problem:

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.

Time Complexity:

O(N \cdot logN), per test case.

Space Complexity:

O(N)

4 Likes

why even after 1 wrong submission gennady is placed at 1 ?
@admin ?

1 Like

Because he is gennady,just kidding.

He submitted much earlier so no effect of that 10 min penalty.

@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.

1 Like

10 minutes*

no it was @lhic who was first to submit all 5 problems ?

he was ranked 1 until gennady solved 5th with a wrong submission …

@admin recheck ur rank list and time of submission

dp[x] = max(dp[x-1], 1+dp[prev]) for x>0 && x<n where prev = floor((x-b)/k);

dp[0] = 1;

dp[-ve] = 0;

Will this solution work?
If no then what is wrong?

Thanks in advance.

Irrelevant comment incoming:

Oh my god. My eyes are so addicted to latex variable highlighting that bold highlighting seems off XD.

XDXD

1 Like

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. :slight_smile:

Where are the rest of the editorials ?

1 Like

@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.

@square_root_pi

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)

1 Like

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.

My solution : https://www.codechef.com/viewsolution/17482252
sample solution accepted with same algo : https://www.codechef.com/viewsolution/17480167

A bit disappointed. @admin Could you please have a look.

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.

1 Like

https://www.codechef.com/viewsolution/17487618

My solution is giving TLE error. I have used same strategy to solve the problem.
can anyone tell how can i optimise this!

xD. Its Greedy. I applied Dp + Segment tree + binary Search + Sorting <3 <3…

https://www.codechef.com/viewsolution/17475801

Can you please check this? Is there something I am missing?