#include <stdio.h>
#include <stdlib.h>
typedef struct
{
unsigned long long int val;
struct node *next;
}node;
node *head=NULL,*tail=NULL;
void delet(unsigned long long int l)
{
node *q=head,*q2=NULL;
unsigned long long int copy=l;
while(l>1)
{
q=q->next;
l–;
}
l=copy;
if(!l)
{
tail->next=head->next;
q=q->next;
head=q;
}
else if(q->next==tail)
{
q->next=head;
tail=q;
}
else
{
q2=q;
q=q->next;
q2->next=q->next;
}
}
unsigned long long int *min(unsigned long long int a[],int l,unsigned long long int mm[])
{
unsigned long long int b[l];
mm[0]=a[0]+a[1];
mm[1]=0;
for(int i=0;i<l;i++)
{
b[i]=a[i]+a[(i+1)%l];
if(mm[0]>b[i])
{
mm[0]=b[i];
mm[1]=i;
}
}
return mm;
}
void replace(unsigned long long int x,unsigned long long int y)
{
node *q=head;
while(y>0)
{
q=q->next;
y–;
}
q->val=x;
}
void copy(unsigned long long int a[])
{
node *q=head;
int i=0;
while(q->next!=head)
{
a[i++]=q->val;
q=q->next;
}
a[i]=q->val;
}
void create(unsigned long long int x,int l)
{
node p=(node)malloc(sizeof(node));
p->val=x;
if(!l)
{
head=p;
tail=p;
}
else
{
tail->next=p;
tail=p;
}
p->next=head;
}
int main()
{
int c;
scanf("%d",&c);
while(c>0)
{
int l;
unsigned long long int x,pen=0;
scanf("%d",&l);
for(int i=0;i<l;i++)
{
scanf("%llu",&x);
create(x,i);
}
while(l>1)
{
unsigned long long int arr[l],m[2];
copy(arr);
min(arr,l,m);
pen+=m[0];
replace(m[0],m[1]);
delet((m[1]+1)%l);
l–;
}
printf("%llu\n",pen);
c–;
}
return 0;
}
I haven’t studied your code yet, but Sub-task 2 in this problem can be solved using Greedy approach. So I assume that you have applied greedy approach,instead of Dynamic programming. So use DP instead of Greedy.
To understand the DP implementation, the video tutorial for this problem might help you. Circular Merging Codechef Long using Matrix Chain Multiplication Dynamic Programming - YouTube
because sub task 2 having distinct power of 2, so we just need to pick position which having minimum adjacent sum and due to distinct power of 2 at each step there is only one such index will exist.
One important observation for subtask 2 ( which makes greedy works ) is it has all elements distict powers of two. How does that help ? well, if you group any of them and sum up, they would result in distinct numbers always, i.e. there won’t ever be two numbers that are equal, even not in the middle of the process. This makes greedy work here, and not in other subtasks.
Thank you, sir! That was a pretty clear explanation
Even Subtask 1 could be solved by greedy. I did that. Probably, it was a weak test case.