{"id":594,"date":"2021-09-08T21:17:38","date_gmt":"2021-09-09T04:17:38","guid":{"rendered":"https:\/\/blog.400pixels.net\/?p=594"},"modified":"2022-06-05T12:51:26","modified_gmt":"2022-06-05T19:51:26","slug":"video-explaining-the-solution-of-google-code-jam-2021-cheating-detection-problem","status":"publish","type":"post","link":"https:\/\/blog.400pixels.net\/?p=594","title":{"rendered":"Presentation: Explaining the solution of Google Code Jam 2021 \"Cheating Detection\" problem"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">In Google Code Jam this year, there was a problem called \"Cheating Detection\" that was very different from the usual algorithm-based problems. It was more data-driven: it involved finding the cheater among a set of students, given only the scores of all students in each of the questions in an exam, and the mechanism of cheating that the cheater used (cheating only 50% of the time).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">After the round was over, I went to see the solutions of the top contestants, to see what sorts of methods they used to obtain a solution. The solution had to detect the cheater with very high probability, and also needed to be a fast enough program to type that it would be among the first submitted. I found the top solution to be surprisingly simple in its code, so I tried to figure out a mathematical explanation for why it worked. I ended up making a video with this explanation.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">You can watch the video here:<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"&quot;Cheating Detection&quot; Solution Mathy Explanation - Code Jam 2021\" width=\"625\" height=\"469\" src=\"https:\/\/www.youtube.com\/embed\/7RM9GNOsjJY?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In Google Code Jam this year, there was a problem called \"Cheating Detection\" that was very different from the usual algorithm-based problems. It was more data-driven: it involved finding the cheater among a set of students, given only the scores of all students in each of the questions in an exam, and the mechanism of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"class_list":["post-594","post","type-post","status-publish","format-standard","hentry","category-presentations"],"_links":{"self":[{"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=\/wp\/v2\/posts\/594","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=594"}],"version-history":[{"count":2,"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=\/wp\/v2\/posts\/594\/revisions"}],"predecessor-version":[{"id":606,"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=\/wp\/v2\/posts\/594\/revisions\/606"}],"wp:attachment":[{"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=594"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=594"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.400pixels.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=594"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}