Can someone help me with ANSLEAK question of April Long Challenge 2020

I tried understanding the submissions of ANSLEAK as there is no editorial on this question but I could not understand the logic behind the question. Could someone help me?

int main(void) {
int t,n,m,k;
scanf("%d",&t);
while(t-- >0)
{
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
int arr[n][k];
int c[m];
for(int i=0;i<n;i++)
{
for(int v=0;v<m;v++)
{
c[v]=0;
}
for(int j=0;j<k;j++)
{
scanf("%d",&arr[i][j]);
c[arr[i][j]-1]++;
}
int big=c[0];
int p=0;
for(int u=1;u<m;u++)
{
if(c[u]>big)
{
big=c[u];
p=u;
}
}
printf("%d ",p+1);
}
}
return 0;
}

hope this helps

you don’t understand the logic behind the question or you don’t understand the logic behind the submissions you checked?
I can explain my approach, but I need to know what you don’t understand

I don’t understand the logic behind the question

Let’s try a small example. It has K (K = 2) forms, each with N (N = 4) numbers, for example:

Form 1 = 1,3,2,4
Form 2 = 1,1,3,4

You must choose N numbers so that the form with a minimum number of matches has as many matches as possible. Let’s check different choices of such N numbers and analyze the value they give us:

Test #1: 1,1,1,1. This attempt gives us 1 match on form 1 and 1 match on form 2, so the value obtained is only 1.
Test #2: 1,3,2,1. This attempt gives us 3 matches on Form 1 and 1 match on Form 2, so the value obtained is 1 (remember the value is the minimum obtained in all forms)
Try #3: 1,1,2,4 you can verify that this attempt gives us 3 matches in both forms, so the value is 3.

The last attempt allows you to get the maximum possible value for this little example, so 1,1,2,4 is a good answer. The difficult thing about this problem is that K and N are not so small, so the number of combinations is large and it is not so easy to find a method to get a good answer, and certanly, given the limitation in time, it’s impossible to be sure you found the optimal answer.

4 Likes

Thanks @carre. Could you share your solution?

Thanks @punpun

My approach was:

unanswered questions=N
while there's unanswered questions:
    for each possible answer value (up to M) and for each of the N-i rest questions:
        evaluate it "goodness"
    pick the answer/question with best goodness value
    unanswered questions -= 1

To quantify the “goodness” of a choise I keep track of the number of correct answers in each form, let’s call that the score of a form. The “goodness” of an answer/question pair is the number of forms, among those that have k’th lowest scores, that increse their score with that election. The value of k is decreasing while the number of unanswered questions get lower. The approach is pretty simple but good enough to get the 5’th place in div1.

2 Likes

the longest common subsequence of all the forms will be the best answer right?

nop, if you see the small example I used the longest common subsequence is only 2 but the best answer is 3

hmm u are correct.

Hey, what do you mean by ‘k’th lowest scores’. Does it mean the lowest score amongst all the forms at that point of time? Please explain .

Yes, consider the case where you have 10 forms with scores: 3,3,3,4,4,5,7,7,10,10. A k value of 3 means that your goodness will take into account the number of forms with scores 3, 4 or 5 (the three lowest scores) that increase their scores

That’s a wonderful explanation. Thanks @carre

1 Like