Help regarding Shift and push problem of ESYA PROCON 2016 contest

Well this contest was pretty tough(at-least for me), as no one was able to do the last question and only one guy did the second last one. But, sadly I was able to do only the first problem. I need help regarding the second problem Shift and push, how will it be solved?.
My approach was that the number of copy operations will be n,
and number of shifting operations will be minimum of the set of maximum distance between two equal numbers. It gave correct answers in the cases I can think of. e.g.
7
1 1 2 4 5 2 1
should give the answer = 7 + 3
since n = 7, and set of max distance between two equal numbers is
max distance between 1s = 4, (here, 1 1 2 4 5 2 1)
max distance between 2s = 3, (as, 1 1 2 4 5 2 1)
max distance between 4s = 6, (everything except itsef, 1 1 2 4 5 2 1)
max distance between 5s = 6, (similar to 4)
So the set is = {4, 3, 6}, and the minimum is = 3;
so, ans = 7 + 3 = 10
Here is my solution : solution
It was giving TLE, help needed. :slight_smile:

hey, are u sure ur ans will be 10 (given example by u)as according to me ans should be 11.
as the idea behind my logic is ::
first sort the array nd the count the most ocuring element
suppose example is:: 1 1 1 2 3 3…
the most ocuring element is 1 nd count is 3
the formula generated by me is::
count+(n-count)*2
as same elements will be copied(1 is copied 3 times) and rest left will be shifted nd copied…
Correct me if i m wrong!!

I did it in the following way.
For each element store the indices in which it has appeared.
Also store the number of indices between 2 same elements. Then for each distinct element, find the max time it would take to reach the indices just before the indices of the element i have chosen ( if the element is present in 1, then i see n). find there maximum. and then for all these maximums , find their minimum.

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

my code

1 Like

according to me ans should be 12…
this is because
u have to copy the same element right.so copy 1/
after 5 shift
situation would be
2452111
no of steps will be now 10
and the u need nt shift just copy the rest 1 to A array ie 2 remaining steps
total 12
my submission result in exceed in time… but i think logic is correct
https://www.codechef.com/viewsolution/11059233

Hey,I think the anupam_datta approach is right . It is clear that the number which repeats maximum reduce our cost of copying the element at particular index.And to further fill the remaining places we have to use shifting operation which is equal to maximum distance between the indices of the element with which repeats maximum times . As in your given example-
7
1 1 2 4 5 2 1
Maximum occuring is 1.
max distance between 1s = 4, (here, 1 1 2 4 5 2 1)
Earlier [1 1 2 4 5 2 1]
At first shift [1 1 1 2 4 5 2]
At second shift [2 1 1 1 2 4 5]
At third shift [5 2 1 1 1 2 4]
At fourth shift [4 5 2 1 1 1 2]
Now,you can see that we have 1 achieved at all positions.
hence,Our answer = 4(for shifting and filling the remaining places)+7(for copying the element at indices) = 11

1 Like

I don’t know whether my approach is right or wrong. But we have to find the minimum no. of operations, so it should be 10(as, 10 < 11). I used your approach previously of copying the max appeared number, but it was giving WA, as you can see in my example also. Copying 2 will give the minimum operations and not 1(max appeared number).

did it work?

yeah, it did

But, we have to tell the minimum possible operations required. So, instead if we copy 2, then
[- - 2 - - 2 -], shift, [- - 2 2 - 2 2], shift, [2 - 2 2 2 2 2], shift, [2 2 2 2 2 2 2]. So, you see only 3 shifting operations are required. And the answer is, therefore, 7 + 3 = 10.

We have to tell the minimum operations required. see my comment below.

Yeah!,you are right that means we have to execute the same method for all distinct elements.But there will be some trick cases.For Example - Consider the array=(1,2,2,3,4,5) . In this,the maximum distance will be 4 not 0.
Hope,it helps.

true. My program considers this also, but it was exceeding the time limit.

Hey,Did you use Fast I/O?

I used scanf and printf.

As you solution is not visible,I cannot find the fault.You can go through this submission . It has the same implementation . Try verifying your code with this.
https://www.codechef.com/viewsolution/11059566