ANSLEAK approach

editorial
21

Has your submission be rejudged??

22

Are bhai bhai bhai ā€¦ humbhi :sweat_smile:

23

I wasnā€™t able to implement my approach during the contest, but my approach was to find out the most frequent element in the array of answers for each question. If there were multiple most frequent elements in the array, then, if the array is a[n][k], then I would first make an array b[n] and for every i, b[i]=a[i][i%k], and then iā€™ll push back this b[i], for the iā€™th element in my answer vector, else I will push back the most frequent element from the array. Here is my code. Could someone please help me with what is actually wrong in it ?

#include <iomanip>
#include <algorithm>
#include <vector>
#include <iostream>
#include <bits/stdc++.h>
#include <chrono>
#include <cstdlib>
#include <cstdio>
#include <cstring>

typedef long long int ll;
#define test ll t; cin >> t; while(t--)
#define MOD pow(10,9)+7
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define print(x) cout << x << endl;
#define take(x) cin >> x;
#define forn(i,n) for(ll i=0;i<n;i++)


int main (){
  test {
    ll n,m,k;
    cin >> n >> m >> k;
    ll a[n][k];
    vector<ll>v1[n];
    forn(i,n){
      forn(j,k){
        cin >> a[i][j];
        v1[i].push_back(a[i][j]);
      }
    }
    vector<ll>v2;
    unordered_map<ll, ll> mp; 
    forn(i,n){ 
      forn(j,v1[i].size()){
        mp[v1[i][j]]++;  
      }
    }
    ll max=0;
    ll ans[n]={0};
    forn(i,n){
      forn(j,v1[i].size()){ 
        if(mp[v1[i][j]] != -1){ 
          if(mp[v1[i][j]]>max){
             max=mp[v1[i][j]];
             ans[i]=j;
          }
        } 
      }
    }
    forn(i,n){
      ll count=0;
      forn(j,v1[i].size()){
        if(mp[v1[i][j]]==max){
          count ++;
        }
      }
      if(count>=2){
        v2.push_back(v1[i][i%k]);
      }
      else {
        v2.push_back(v1[i][ans[i]]);
      }
    }
    forn(i,n){
      cout << v2[i] << " ";
    }
    cout << endl;
  }
}
25

@galencolin i am doing mval[i]=0 after processing it.

26

:grinning:

27

ha ab 74 hogaya

28

Below is the among the only solutions that got 100 points in the contest for ANSLEAK and it is 255 lines long!!

https://www.codechef.com/viewsolution/31839489

29

didnā€™t it throw NZEC error cause you did not use try-catch block even though the main function has throw Exception keyword??

1 Like
30

@adityxraj My code works.As Iā€™m not accessing any negative indexes or any out of array memory,I donā€™t actually need try catch blocks.So my code doesnā€™t require them.But if you want to be on safer side you can use them.

1 Like
31

I did the same but think about a test case which has 4 answer sheets as follows:-
3 3 3 1
3 3 3 1
3 3 3 1
3 3 3 1
your program will give a output :- 3 3 3 3 (max possible worst score will be 0)
but the more appropriate answer for this will be :- 3 1 3 1(max possible worst score will be 2)

so the approach i followed is :-
step1: for the row which are having same element put it as it is in the answer
step2:for the remaining find the column which has min score and add its element in the ans
eg:-
4 4 4 4
1 2 3 4
2 2 3 4
1 2 1 2
After step 1:-
ans[]={4,0,0,0}
score={1,1,1,1}
Step2:-1:
1)
ans[]={4,1,0,0}
score={2,1,1,1}
2)
ans[]={4,1,2,0}
score[]={3,2,1,1}
3)
ans[]={4,1,2,1}
score[]={3,2,2,1}

32

I scored decent points using a fairly simple algorithm. Assume you have chosen answers for first x questions. Then we greedily find the best answer to the (x+1)th question by increasing the minimum over all forms and if the minimum was same for 2 or more answers then we take the choice where there were least number of minimums.
I would love to explain more if anyone is interested.

1 Like
33

I think you ask about the k value consideration, right? The idea is that if S is the lowest score you expect to have at the end, that means that all exams should have scores up to that value, therefore, in the first steps where you have several exams with scores s1, s2, s3, ā€¦ sk <S, you need to increase the scores of all of them, not just the lowest. Of course, you donā€™t know the value of S, so the value of k as a function of iteration is a parameter you need to find

34

Whoops, sorry, youā€™re right. Maybe the issue is setting max to 1 instead of mval[1].

35

@hala_tea Can you please explain with example ?

36

I applied the exactly same approach but got only 65 points

37

Try to generate the test cases themselves using your own code using the given frequencies as weights and formulae provided in the question, use randomized algorithms instead of normal ones. ACRush did something similar and was able to score perfect 100. (He/She is Rank #1 of April Div 1 Long Challenge).

1 Like
38

for
1 2
2 1
1 1
2 2

how is 2 1 1 1 better than 2 1 1 2 ? In the latter the worst case score is 2 compared to 1 in the former.

39

Yeah you are write the given sample test case output is itself not an efficient one.Then you can have many solutions,so it depends on your approach and efficient answer.
Other possible answers
1 2 1 2
1 1 1 2
2 2 1 2
2 1 1 2

40

Sorry, I seem pretty late. I donā€™t remember the question quite clealy though I will try my best to explain myself.
Ok so e.g. :
lets say 3 options / question and 3 questions for simplicity :
form 1 -: 1 2 3
form 2 -: 2 2 3
form 3 -: 3 2 1
basically the example says that if our choice of answers was lets say 1 2 3 then according to form 1 we have a perfect score. According to 2 we have score 2 while for 3 we have 0. So the mimimum being 0 we will get 0.
Ok as for the algorithm now.
lets choose best for question 1 :: if we choose 1 then acc to form 1 we score 1 while acc to 2 we get 0 while acc to 3 we also get 0. Similarly if we choose 2 or 3. So if we choose any the mimimum would still be 0 so choose any. lets say we chose 1 then we find the best answer greedily for question two by trying to maximize the minimum and so on.

1 Like