What was your approach for the challenge question ANSLEAK?
My approach was to check the max of each row and that gave just 75 points.
Others with higher points, please share your approach.
3 Likes
I stored the number of wrong answers for each k , I tried to give correct answer to the page which had maximum number of wrong answers till then.
3 Likes
My approach was to print i and increase i by 1 ,while i<=m. Then if i>m I replace i=1. That gave me 78 points.
I almost applied same approach but only when rows are less than columns (n<k).
Else when (n>=k) I just traversed matrix from (0,0) in a line having negative 45 degree slope, as it reaches the last column, again I start it from 0th column from the next row. Like zig-zag manner.
I stored all the options in a matrix and created a frequency matrix[i][j] to store the frequency of j th option for i th question based on a flag[k] array which contains the mark in kth set.When flag[k]==min then I will update the frequency matrix and I will take the max in this frequency matrix and place it in result array at the respective question and go on update and insert the elements.
This approach gave me 93.4 score.
Here is my code:https://www.codechef.com/viewsolution/31771310
5 Likes
i tried adding weight to all the question forms which were not selected. More like the ageing concept in round robin algo. A bit of hit and trial for the factor to increase weight gave me 95
I created another array of size k , which stores the number of wrong answer for each question form. So for each question , first I check which question form has the highest number of wrong answers till that question (let it be i), then the answer for current question would be answer of the question form i , and then I update the wrong answer array . My code
If you read out the test generation section in the ANSLEAK problem they are testing the solutions based on a random value so i just cout random values in range 1 to m and that gave me 75 points!..I did it using rand function rand() %m + 1 for every i in range 0 to n.
here is my solution CodeChef: Practical coding for everyone
1 Like
i printed the maximum in first row and then second maximum in second row and then so on.
42k (~94 points in final scoring): shuffle the questions randomly, and fix a cap on the answer. Keep a count array of how many answers are correct for each possible test (initially all 0). Then, for each question in the shuffled order, greedily select the answer that is correct for the most sheets with count < cap, with more weight given to sheets farther from the cap. Run this process until time runs out, increasing the cap gradually (or binary searching). O(nk) per iteration.
Submission
42.5k (~95 points in final scoring): each step, brute-force not only the best next answer to take, but also the best next question to answer. O(n^2k) per iteration, so I only used this strategy for n = 100, k = 1000.
Submission
2 Likes
@koulick424
hey, my approach was the same but it gave me only 37 points.
Can you tell me the exact difference between your approach and my approach.
Here is my code: CodeChef: Practical coding for everyone
The approach that I used was to keep track of the exams with the lower score, and for those choose the answer that appeared the more. I then updated the exams with lower score and repeated for every question. This approach got me about 90 points.
I also use the gready approach of choosing the “best” option possible for exams with low scores, but not for the lowest one, but for the k-th lowest, where k is a variable number from some initial value at the beginning to 1 near the end. That showed to be a decent approach until ACRush came into scene.
But I think this would give non AC verdict after rejudging
You don’t reset mval between each question.
Can you please explain why does it work ?
Well I printed answer randomly for each row using rand() function in c++. Got 81 XD .
2 Likes
Some users ansleak submission have been evaluated and this approach has yeild only 25 pts though.
1 Like
I had used random function which give me 75 points
1 Like