How did you solve MAXLIS?

1

How did you solve MAXLIS?

1 Like
2

It is a challenge problem It do not have any exact approach by the way my approach was to shift as many numbers as n,n-1,n-2 … to the back side of the array because we have to maximize the Longest Increase Subsequence . And number of such numbers which can be shifted without an issue were (k-1)/2;

2 Likes
3

Here’s my approach, that I got to by extending my first method that was similar to the one proposed by @anon31329220
First compute a longest increasing subsequence (LIS) L_1,…,L_s
Then we will extend this subsequence by choosing i1, i2 and moving the subsequence ]L_i1, L_{i1+1}[ right before the value L_i2. We choose such i1, j1, i2 so as to maximize the new LIS. We do so as long as we still can cut the sequence. (If you’re allowed k chunks from your sequence, then you’re allowed k-1 cuts in total)
However, actually maximizing would cost n² at each step, each step using 3 (or more likely 2 with some changes). You get k/3 steps, so a complexity of kn², which is too much. To solve this problem, you can first choose i1 so as to maximize the size of the subsequence ]L_i1, L_{i1+1}[ (O(s)), partition those values into the interval they should go to (~n/s*log(s)), and compute the LIS of each of these partition (~n/s*log(n)), chosing i2 so as to maximize the size of the found LIS. You can then update linked list A and decrease k from the number of cuts you had to do (at most 3). You can also update the LIS of your entire sequence for a cheap price.
The last bit would be to actually not move the entirety of ]L_i1, L_{i1+1}[, but instead [α, L_{i1+1}[, in order to force all of your cuts to be right before a value that belongs to the LIS, increasing the probability that a step will cost 1 or 2 cuts instead of 3.
For the biggest input, it would take me ~0.5s to compute all of this until k is 1, meaning that I could repeat the process, adding some randomness to get a slightly different result.
I hope that was clear, don’t hesitate to ask questions (I would advise against looking at my code, it’s an unreadable mess)

3 Likes
4

My solution :joy: it was absolute hit and trial

5

Sorry, You lost me in the second paragraph. Not able to follow your idea properly!

6

Ok so roughly and without any complexity optimization, the idea is to preserve the current longest increasing subsequence by not moving its elements. Consider the LIS as fixed points of you sequence. You move the other elements relatively to those fixed points.
By doing so, you know that the new sequence still includes the initial LIS. You can find ways of moving the other elements such that the LIS’s size is increased by at least one (asymptoticaly, that’s even more than ~√(n/s²), but you don’t need that)
I hope it was a bit clearer, I probably went too much into the details

3 Likes
7

My approach which unexpectedly gave me 39 pts…(attempting challenge problem first time)

what I did was First I check if n==K…then sort the array and return it
else:
first, partition the array in K+1 pieces…i.e, break it from k places such that all are in increasing order except the last one

now copy this in two array
sort the first array on the basis of the first element of these K+1 groups and find the length of Longest Increasing Subsequence in O(N log N)
now sort the second array on the basis of the
last element of these K+1 groups and find the length of Longest Increasing subsequence again in O(N log N)
compare them whose LIS is greater…print that array

This game me the gift of 39 points in the challenge problem

8
  1. Move Max element to end
  2. Move Min element to beginning
  3. Sort first K-3 elements from begining.

Guess what?
Got 26 point for this :sweat_smile:
https://www.codechef.com/viewsolution/27180296

9

I wondered how everyone is getting 20-40 points easily whereas i couldn’t get more the 3.xxx.I equally divided the subarrays in k parts and tried randomized permutation of these k subarrays for 100 iterations. Yeah, i know that’s the most bizzarre solution to get some points :stuck_out_tongue_closed_eyes:. Anyone else wanna share their weird approach ?

10
  1. Check the min element and its adjacent and push the min and minimum of adjacent
  2. Check the max element and its adjacent and push the max and maximum of adjacent
11

Split the array into k similar sized pieces.
Split the range of integers 1...n into k sections.
Then for each piece of the array, and for each section, calculate length of the longest increasing sequence in piece of array with values in the section. We now have a matrix of k^2 lengths.

Allocate the pieces of the array to the sections by solving a balanced maximum value assignment problem.

For some of the test-cases this method resulted in a longest increasing sequence less than 2k, which seemed rather small. My second approach was to search the array for up to k pairs of integers, where the integers are close together in position and value, and the intervals between the integers (in position and value) are non-overlapping. For some of the test cases this gave a better permutation.

12

How this this solution work- Print 1 and if arr[i]!=1, print arr[i].
CodeChef: Practical coding for everyone.
What is the logic? Can anyone explain?

13

It permutes the sequence so that 1 appears at the start.

For example, if the original sequence was 2,5,1,4,3, then the output sequence will be 1,2,5,4,3, which improves the maximum increasing sequence length from 2 to 3.