kakashi.'s blog

By kakashi., history, 5 weeks ago, In English

I don't know if I'm completely wrong, but reading the editorial for the Hacked Exam problem, maybe they overcomplicated the solutions for test sets 1 and 2. I just figured that, with T/F questions, adding a second student with a lower score doesn't change the expected value. So, the answer is to just replicate the best student (or the worst one inverted, for that matter). Does it make sense or I just got lucky to have passed with this idea? Thanks for any help! And please follow the code below.

string inv(string a) {
    string r;
    trav(x, a) {
        if(x == 'T') r += 'F';
        else r += 'T';
    }
    return r;
}

void run_test() {
    int n, q; read(n, q);
    int mx = 0;
    string ans;
    rep(k, n) {
        string a; read(a);
        int s; read(s);
        if(s <= q / 2) a = inv(a), s = q-s;
        if(s > mx) {
            mx = s;
            ans = a;
        }
    }
    cout << ans << " " << mx << "/1" << endl;
}
 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I did the same :D

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Do you have a proof , like how you would prove that answer less than maximum value doesn't matter.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't, so I would be very glad if someone could come up with that.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I did a similar thing. My reasoning is as follow:

For the first student, P(ans(i) = T | A) = A / Q if he chooses T and 1 — A / Q if he chooses F where A is his score. The same for the second student.

Then for every answer, if both students give the same answer, then choose it. If they give different answer, choose the one with highest probability. Calculating this way, the highest probability is always from one with higher total score. Hence I just copy the answer of the student with the highest score.

Even if I think this kind of answer is idiotic, not solid, and just random guess. I think it makes sense for N=2. Can anyone tell where I was wrong?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Consider the set $$$A$$$ of questions that received the same answer from both students. Suppose each of them responded correctly $$$x$$$ questions from $$$A$$$ (since they responded in the same way, they must have the same points in these questions). Then the probability of them responding correctly a question $$$q \in A$$$ is $$$p_{q} = \frac{x}{\vert A \vert}$$$ and the probability of having an incorrect answer is $$$1 - p_{q}$$$. Now, we'll choose our answer to these questions based on which probability is higher, then the expected value of correct answers is

$$$\sum\limits_{q \in A}\max(p_{q}, 1 - p_{q}) = \max(x, \vert A \vert - x)$$$

Let's do the same for the rest of the questions noticing that the $$$i$$$-th student got $$$s_{i} - x$$$ points, so the probability of student $$$i$$$ responding question $$$q \notin A$$$ correctly is $$$p_{i,\, q} = \frac{s_{i} - x}{Q - \vert A \vert}$$$. In this case the expected number of correct answers is

$$$\sum\limits_{q \notin A}\max(p_{1,\, q},\, 1 - p_{1,\, q},\, p_{2,\, q},\, 1 - p_{2,\, q}) = \max(s_{1} - x,\, s_{2} - x,\, Q - \vert A \vert - (s_{1} - x),\, Q - \vert A \vert - (s_{2} - x))$$$

We want to prove that replicating the answers of the student with best score (or responding the opposite as the student with worst score if $$$Q - \min(s_{i}) \geq \max(s_{i})$$$) yields the maximum expected value. There are four cases but they're pretty much symmetrical, we'll only do one of them.

Assume that $$$s_{1} = \max(s_{1},\, s_{2},\, Q - s_{1},\, Q - s_{2})$$$. Our goal is to prove that the sum of the previous expected values is exactly $$$s_{1}$$$, in order to do so we'll just figure out what the maximums are and check that they add up to $$$s_{1}$$$. It is obvious that $$$s_{1} - x \geq s_{2} - x$$$ and $$$Q - \vert A \vert - (s_{2} - x) \geq Q - \vert A \vert - (s_{1} - x)$$$. If we show that $$$s_{1} - x \geq Q - \vert A \vert - (s_{2} - x)$$$ then it follows that the second summation is equal to $$$s_{1} - x$$$. \begin{align} s_{1} − x &\geq Q − \vert A \vert − (s_{2} − x) \newline \iff s_{1} + s_{2} − 2x &\geq Q − \vert A \vert \end{align} Remember that $$$x$$$ is the number of points that each student got for answering questions correctly from the set $$$A$$$, therefore $$$s_{1} - s_{2} -2x$$$ represents the number of correct answers in which exactly one of them chose $$$T$$$ and the other student chose $$$F$$$, then all the remaining questions (questions $$$q$$$ where $$$q \notin A$$$) were answered correctly between the two students and the inequality follows (Actually we have an equality and something that will be useful later on is $$$Q = s_{1} + s_{2} - 2x + \vert A \vert$$$).

Finally we only need to prove that the first summation is equal to $$$x$$$. Assume that it is equal to $$$\vert A \vert - x$$$ then it must be true that $$$\vert A \vert - x > x \Rightarrow \vert A \vert > 2x$$$. The following inequality contradicts our initial assumption on the maximality of $$$s_{1}$$$ \begin{align} Q − s_{2} &= (s_{1} + s_{2} − 2x + \vert A \vert) − s_{2} = s_{1} − 2x + \vert A \vert > s_{1} \end{align} So, the expected number of correct answers is $$$s_{1}$$$.