Hello guys can anyone help me with the compress the list problem, i can only figure out multiple if else solution.
Please check my code here: Coding Blocks IDE
Thanks in advance.
stacks was just to simplify my strategy yeah but the idea was to devise a strategy in my case i observed the first number which is less that its previous. As you can only reduce the number and not increase it so if the arr[0] was less than any arr[i] i>0 then we had to reduce arr[0] to that arr[i] finally,so we consider all number greater than arr[0] and keep putting them on the stack when we get an i such that arr[i] < stacktop we know that the previous value which is greater than this have to be reduced to this so for all j<i j in stack where arr[i]<j we change those value to arr[i] val and increase count now and remove these from stack as they have been processed and made into arr[i]. Go on this way .
try to iterate the logic for 1 2 4 5 3 12 you will get it,
like 1 2 4 5 3 12
applying the strategy here 3<5 && 3<4 so you need to change both 4&5 to 3 intially but 3>2 so once you changed 4 5 to 3 it becomes
1 2 4 5 3 12 → 1 2 4 3 3 12 → 1 2 3 3 3 12
now we see 2<3 so we need to get the 3s down to 2s we can do that in one step(this was the reason to convert 4 and 5 to 3 intially and not to 1 so as to do group them together and convert them to 2 this in 1 step)
1 2 3 3 3 12 → 1 2 2 2 2 12
carry on the same process for 1 and thats how the logic builds.
Here is the code to help you out its very straightforward and easy to understand. Important part was to proof that the strategy was right.
can anyone help me with compress the list (cmprss) question, sample test output is the same but on submitting it is wrong, I tried with StringBuilder also.
link: CodeChef: Practical coding for everyone
In one operation, you may choose any contiguous subsequence Al,Al+1,…,Ar such that for each i (l+1≤ i ≤r), Ai=Al, i.e. a sequence of identical elements, then choose any integer x<Al, and for each i (l≤ i ≤r), replace Ai by x. The integers x chosen in different operations may be different.
Hi doesn’t this explanation mean that we can only take a subarray of identical elements and the min. size of the sub-array is 2?
Can please someone dry-run it for this test case?
5 9 8 3 12
Hi @maghav12,
You are wrong, we can take a sub-array of length 1 too. It is not written that l < r, in the question.
No idea how many of you are still waiting for answers, but:
1
4
9 15 16 23
@ganesh_6 (CMPRSS)
1
11
6 8 9 10 11 13 15 16 17 20 23
@darklooter and @abhishk1
1
12
2 3 4 6 7 8 9 10 11 12 13 14
2 Likes