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
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