CIRMERGE - Subtask 2 runs but 1 and 3 fails, can someone plz help me understand this?

#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;
}

1 Like

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. https://www.youtube.com/watch?v=jxVzUg7oSP8

1 Like

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.

2 Likes

Thank you, sir! That was a pretty clear explanation :smile:

Even Subtask 1 could be solved by greedy. I did that. Probably, it was a weak test case.