CIRMERGE - Editorial

editorial
, , ,
7

Many N^3 solutions were giving TLE. Setters should have been careful. If we use modulo operator, we get tle , if we don’t …it runs!

3 Likes
8

Yes but it’s not a new thing, everyone should know modulus is time consuming operation and it’s always better to avoid it.

3 Likes
9

Testers might didn’t used it, so they might didn’t figured it out…

10

clever move by settler, see how he used mod, It seems this time limit was put intentionally.

11

Its basically Matrix chain multiplication over a circular array. Nice editorial though😊

8 Likes
12

In fact, this problem is solved by O (n ^ 2) method of quadrilateral inequality and O (nlogn) method of Garsia Wachs algorithm plus BST.

10 Likes
13

This is the Garsia Wachs algorithm, which can solve linear version of this problem by O (T*n^2).

#include <iostream>
#include <string.h>
#include <stdio.h>
 
using namespace std;
const int N = 50005;
 
int stone[N];
int n,t,ans;
 
void combine(int k)
{
    int tmp = stone[k] + stone[k-1];
    ans += tmp;
    for(int i=k;i<t-1;i++)
        stone[i] = stone[i+1];
    t--;
    int j = 0;
    for(j=k-1;j>0 && stone[j-1] < tmp;j--)
        stone[j] = stone[j-1];
    stone[j] = tmp;
    while(j >= 2 && stone[j] >= stone[j-2])
    {
        int d = t - j;
        combine(j-1);
        j = t - d;
    }
}
 
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n == 0) break;
        for(int i=0;i<n;i++)
            scanf("%d",stone+i);
        t = 1;
        ans = 0;
        for(int i=1;i<n;i++)
        {
            stone[t++] = stone[i];
            while(t >= 3 && stone[t-3] <= stone[t-1])
                combine(t-2);
        }
        while(t > 1) combine(t-1);
        printf("%d\n",ans);
    }
    return 0;
}

If BST optimization is used again, O (T*nlogn) can be achieved.

37 Likes
14

How do you know so much ?! Show us the way…!

5 Likes
15

My college teacher talked about these things.

In fact, this problem is not a simple one in the eyes of some people, but the data range of the problem is too small，I guess the author probably didn’t learn this algorithm either.

Tidy up:
the normal DP: O(T*n^3)
Quadrilateral inequality optimization DP: O(T*n^2)
Linear case:
Garsia Wachs algorithm: O(T*n^2)
BST optimization Garsia Wachs algorithm: O(T*nlogn)

28 Likes
16

I used a different approach .

  1. search for the adjacent pair with smallest sum.
  2. add their sum to score
  3. make one element element equal to the sum and remove the other
  4. if there are more than one elements go to 1
  5. print score.
    But it could only pass one sub task. Can you tell me what i did wrong?
    my solution :CodeChef: Practical coding for everyone
    edit: editorialist has also mentioned but I don’t understand why it doesn’t work with other subtasks.
4 Likes
17

The input is quite small in all testcases, so io is fast no matter how you do it.

18

i am completely not able to understand CIRMERGE PROBLEM
why it can’t the sum of array
IT IS A SILLY QUESTION BUT I WANT TO LEARN PLS HELP ME

20

hello… i tested all possible test cases and got correct answer every time… can you tell what is the problem here??
i used python 3.6

y=[]
x=int(input())
for z in range(0,x):
    pentt=[]
    pent=0
    n= int(input())
    a=list(map(int, input("").split()))
    for ww in range(0,n-1):
        aaa=0
        bbb=0
        minn=a.index(min(a))
        lenn=len(a)-1
        if minn==lenn:
            aaa=minn
            bbb=0
            if a[bbb]<a[minn-1]:
                pent=a.pop(aaa)+a.pop(bbb)
            else:
                pent=a.pop(aaa)+a.pop(aaa-1)
            a.insert(aaa,pent)
            pentt.append(pent)
        elif minn==0:
            aaa=minn
            bbb=minn+1
            ccc=lenn
            if lenn==1:
                pent=a.pop()+a.pop()
                a.insert(aaa,pent)
            else:
                if a[bbb]<a[ccc]:
                    pent=a.pop(bbb)+a.pop(aaa)
                    a.insert(aaa,pent)
                else:
                    pent=a.pop(ccc)+a.pop(aaa)
                    a.insert(aaa,pent) 
            pentt.append(pent)
        else:
            aaa=minn
            bbb=minn+1
            ccc=minn-1
            if lenn==1:
                pent=a.pop()+a.pop()
                a.insert(aaa,pent)
            else:
                if a[bbb]<a[ccc]:
                    pent=a.pop(bbb)+a.pop(aaa)
                    a.insert(aaa,pent)
                else:
                    pent=a.pop(aaa)+a.pop(ccc)
                    a.insert(ccc,pent) 
            pentt.append(pent)
    print(sum(pentt))
21

can you give some test cases and their answer

22

For e.g. in this case : 4 3 2 3 2 3 5 6 .
By your logic it would find the adjacent pair with smallest sum = 5 and it would
first merge the first occuring 3 and 2 , which would not turn into minimum score.
Look in this example …

4 Likes
23

Can anyone give me any case were the brute force solution of subtask 2 will not work for other subtasks…

24

Bruteforce will excede the time limit as there is n factorial ways to merge the array

25

But i did not recieve a tle for rest of subtasks and instead I got WA.
Here is the link of my solution CodeChef: Practical coding for everyone

1 Like
26

O(N^3) solution working fine…
this is my code
https://www.codechef.com/viewsolution/25117564

2 Likes
27

Can anyone use different approach other than DP???
Thanks