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;
while(t-- >0)
int arr[n][k];
int c[m];
for(int i=0;i<n;i++)
for(int v=0;v<m;v++)
for(int j=0;j<k;j++)
int big=c[0];
int p=0;
for(int u=1;u<m;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.


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.


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