Code Jam APAC 2017 - Problem B. Robot Rock Band

Robot_Rock_Band.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Google Code Jam\n",
    "\n",
    "## Practice Round APAC test 2017\n",
    "\n",
    "### Problem B. Robot Rock Band"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def line(f):\n",
    "    return f.readline().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solve_input(f_in, f_out, std_out=True):\n",
    "    fin = open(f_in, 'r')\n",
    "    fout = open(f_out, 'w')\n",
    "    \n",
    "    T = int(line(fin))\n",
    "    for t in range(T):\n",
    "        n, k = map(int, line(fin).split())\n",
    "        ls = [[int(x) for x in line(fin).split()] for i in range(4)]\n",
    "        ans = solve(n, k, ls)\n",
    "        res_str = 'Case #%s: %s' % (t + 1, ans)\n",
    "        fout.write(res_str + '\\n')\n",
    "        if std_out:\n",
    "            print(res_str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Meet in the middle strategy\n",
    "\n",
    "Going through all the combinations takes too much time. For the large test case: `1000^4 = 10^12.`\n",
    "\n",
    "Instead, we can divide the \"4 nested loops\" into 2 \"2 nested loops\". Which would bring the worst case down to `1000^2 + 1000^2 ~= 10^6` (completely ok).\n",
    "\n",
    "Given the 4 lists A, B, C and D, the idea is to find the number of sets $\\{a, b, c, d \\mid a \\in A, b \\in B, c \\in C, d \\in D \\}$ such that $a \\oplus b \\oplus c \\oplus d = k$, which is the same as $a \\oplus b \\oplus c \\oplus d \\oplus k = 0$.\n",
    "\n",
    "We can divide this equation into finding 2 numbers: $a \\oplus b$ and $c \\oplus d \\oplus k$, that are easily found with 2 nested loops for each ($k$ constant).\n",
    "\n",
    "The only thing left is to remember all the numbers generated by the XOR of a and b, as there might be many of them. We store them in the dictionary $cnt$ to be able to count how many times they are reached. Whenever we compute a number $x = c \\oplus d \\oplus k$, we check whether it exists in the dictionary $cnt$. If it does, we know that taking the XOR of $x$ and $a \\oplus b$ will be zero since they are equal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solve(n, k, ls):\n",
    "    A, B, C, D = ls\n",
    "    cnt = defaultdict(int)\n",
    "    for a in A:\n",
    "        for b in B:\n",
    "            xor = a ^ b\n",
    "            cnt[xor] += 1\n",
    "            \n",
    "    ans = 0\n",
    "    for c in C:\n",
    "        for d in D:\n",
    "            xor = c ^ d ^ k\n",
    "            # cnt[xor] = 0 if xor not in cnt (defaultdict)\n",
    "            ans += cnt[xor]\n",
    "            \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Case #1: 4\n",
      "Case #2: 8\n"
     ]
    }
   ],
   "source": [
    "solve_input('1.in', '1.out')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Case #1: 2882388\n",
      "Case #2: 83297\n",
      "Case #3: 0\n",
      "Case #4: 4080\n",
      "Case #5: 5308416\n",
      "Case #6: 2439795\n",
      "Case #7: 76081\n",
      "Case #8: 0\n",
      "Case #9: 4711\n",
      "Case #10: 5308416\n",
      "CPU times: user 30 ms, sys: 0 ns, total: 30 ms\n",
      "Wall time: 34.6 ms\n"
     ]
    }
   ],
   "source": [
    "%time solve_input('B-small-practice.in', 'B-small-practice.out')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Case #1: 492047993088\n",
      "Case #2: 15009248196\n",
      "Case #3: 972\n",
      "Case #4: 796277175\n",
      "Case #5: 933714431521\n",
      "Case #6: 490074779765\n",
      "Case #7: 13326445069\n",
      "Case #8: 883\n",
      "Case #9: 940929712\n",
      "Case #10: 968381956096\n",
      "CPU times: user 5.74 s, sys: 150 ms, total: 5.89 s\n",
      "Wall time: 5.94 s\n"
     ]
    }
   ],
   "source": [
    "%time solve_input('B-large-practice.in', 'B-large-practice.out')"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}