fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef double ld;
  6. typedef unsigned int uint;
  7. const uint ST = 100;
  8. const uint QT = 10000;
  9. const uint iterations = 10;
  10. const ld  learing_rate_S = 10.;
  11. const ld  learing_rate_Q = 10.;
  12.  
  13. inline ld sigmoid(ld x) {
  14.   return 1./(1.+exp(-x));
  15. }
  16.  
  17. inline ld rsigmoid(ld x) {
  18.   return 1./(1.+exp(x));
  19. }
  20.  
  21. inline ld min(ld a, ld b) {
  22.   return (a<=b? a:b);
  23. }
  24.  
  25. inline ld max(ld a, ld b) {
  26.   return (a>=b? a:b);
  27. }
  28.  
  29. ld mean(vector<ld> &v) {
  30.   ld mean = 0.;
  31.   for (auto &i: v) mean+=i;
  32.   mean /= ld(v.size());
  33.   return mean;
  34. }
  35.  
  36. ld stdev(vector<ld> &v) {
  37.   ld std = 0.;
  38.   for (auto &i: v) std+=i*i;
  39.   std = sqrt(std/ld(v.size()));
  40.   return std;
  41. }
  42.  
  43. void solve() {
  44.   string str;
  45.   vector<vector<bool>> A(ST,vector<bool>(QT));
  46.   for (auto &s: A) {
  47.     cin >> str;
  48.     for (uint i = 0; i < QT; i++) {
  49.       s[i] = (str[i]=='1');
  50.     }
  51.   }
  52.  
  53.   vector<ld> S(ST,0.), Q(QT,0.);
  54.  
  55.   //Initial guess for students
  56.   for (uint i = 0; i < ST; i++) {
  57.     uint cnt = 0;
  58.     for (uint j = 0; j < QT; j++) {
  59.       if (A[i][j])  {
  60.         cnt++;
  61.       }
  62.     }
  63.     ld rateo = ld(cnt)/ld(QT);
  64.     S[i] = max(-3.,min(3., log(rateo/(1-rateo))));
  65.   }
  66.   //Initial guess for question
  67.   for (uint j = 0; j < QT; j++) {
  68.     uint cnt = 0;
  69.     for (uint i = 0; i < ST; i++) {
  70.       if (A[i][j])  {
  71.         cnt++;
  72.       }
  73.     }
  74.     ld rateo = ld(cnt)/ld(ST);
  75.     Q[j] = max(-3.,min(3., log(rateo/(1-rateo))));
  76.   }
  77.  
  78.   for(uint k=0; k<iterations;k++) {
  79.     // Update questions
  80.     for (uint j = 0; j < QT; j++) {
  81.       ld loglike = 0.;
  82.       for (uint i = 0; i < ST; i++) {
  83.         if  (A[i][j]) {
  84.           loglike -= rsigmoid(S[i]-Q[j]);
  85.         } else {
  86.           loglike += sigmoid(S[i]-Q[j]);
  87.         }
  88.       }
  89.       loglike /= ld(ST);
  90.       Q[j] = max(-3.,min(3., Q[j] + (learing_rate_Q)*loglike));
  91.     }
  92.     // Update students
  93.     for (uint i = 0; i < ST; i++) {
  94.       ld loglike = 0.;
  95.       for (uint j = 0; j < QT; j++) {
  96.         if  (A[i][j]) {
  97.           loglike += rsigmoid(S[i]-Q[j]);
  98.         } else {
  99.           loglike -= sigmoid(S[i]-Q[j]);
  100.         }
  101.       }
  102.       loglike /= ld(QT);
  103.       S[i] = max(-3.,min(3., S[i] + (learing_rate_S)*loglike));
  104.     }
  105.   }
  106.  
  107.   ld best_likelihood = -1e10;
  108.   uint cheater = 0;
  109.   uint cnt;
  110.   ld rateo, Sact, likelihood;
  111.   for(uint i = 0; i < ST; i++) {
  112.     cnt = 0;
  113.     for (uint j = 0; j < QT; j++) {
  114.       if (A[i][j]) {
  115.         cnt++;
  116.       }
  117.     }
  118.     rateo = max(ld(cnt)-ld(QT)/2.,0)/(ld(QT)/2.);
  119.     Sact = max(-3.,min(3., log(rateo/(1-rateo))));
  120.     likelihood = 0.;
  121.     for (uint j = 0; j < QT; j++) {
  122.       if (A[i][j]) {
  123.         likelihood -= -log(1+exp(Q[j]-S[i]));
  124.         likelihood += log((2+exp(Q[j]-Sact))/(1+exp(Q[j]-Sact)));
  125.       } else {
  126.         likelihood -= -log(1+exp(S[i]-Q[j]));
  127.         likelihood += -log(1+exp(Sact-Q[j]));
  128.       }
  129.     }
  130.     //likelihood -= ld(QT)*log(0.5);
  131.     if (likelihood > best_likelihood) {
  132.       best_likelihood = likelihood;
  133.       cheater = i;
  134.     }
  135.   }
  136.   cout << cheater + 1;
  137. }
  138.  
  139. int main() {
  140.   // IO optimizer. Comment if interactive problem
  141.   ios_base::sync_with_stdio(false);
  142.   cin.tie(nullptr); cout.tie(nullptr);
  143.  
  144.   uint t;
  145.   ld p;
  146.   cin >> t >> p;
  147.   for (uint i = 0; i < t; i++) {
  148.     cout << "Case #" << i+1 << ": ";
  149.     solve();
  150.     cout<< endl;
  151.   }
  152.  
  153.   return 0;
  154. }
  155.  
Success #stdin #stdout 0s 4848KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7vH4bV
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!