{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:50.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/7e42421cd3b2517f11732e7e5295ba1d?v\u003d1715309735\" alt\u003d\"/problems/cuckoo/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eOne of the most fundamental data structure problems is\n the dictionary problem: given a set \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e of words you want to be able to\n quickly determine if any given query string \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e is present in the dictionary\n \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e or not. Hashing is a\n well-known solution for the problem. The idea is to create a\n function \u003cspan class\u003d\"tex2jax_process\"\u003e$h:\\Sigma ^*\\rightarrow\n [0..n-1]$\u003c/span\u003e from all strings to the integer range\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0,1,..,n-1$\u003c/span\u003e, i.e. you\n describe a fast deterministic program which takes a string as\n input and outputs an integer between \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e. Next you allocate an empty hash\n table \u003cspan class\u003d\"tex2jax_process\"\u003e$T$\u003c/span\u003e of size\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and for each word\n \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e in \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e, you set \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h(w)]\u003dw$\u003c/span\u003e. Thus, given a query\n string \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e, you only need\n to calculate \u003cspan class\u003d\"tex2jax_process\"\u003e$h(q)$\u003c/span\u003e and\n see if \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h(q)]$\u003c/span\u003e equals\n \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e, to determine if\n \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e is in the dictionary.\n Seems simple enough, but aren’t we forgetting something? Of\n course, what if two words in \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e map to the same location in the\n table? This phenomenon, called collision, happens fairly often\n (remember the Birthday paradox: in a class of 24 pupils there\n is more than \u003cspan class\u003d\"tex2jax_process\"\u003e$50$\u003c/span\u003e% chance\n that two of them share birthday). On average you will only be\n able to put roughly \u003cspan class\u003d\"tex2jax_process\"\u003e$\\sqrt\n {n}$\u003c/span\u003e-sized dictionaries into the table without getting\n collisions, quite poor space usage!\n\n \u003cp\u003eA stronger variant is Cuckoo Hashing\u003ca href\u003d\"https://open.kattis.com/problems/cuckoo#a0000000440\" class\u003d\"footnote\"\u003e\u003csup class\u003d\"footnotemark\"\u003e1\u003c/sup\u003e\u003c/a\u003e. The\n idea is to use two hash functions \u003cspan class\u003d\"tex2jax_process\"\u003e$h_1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$h_2$\u003c/span\u003e. Thus each string maps to two\n positions in the table. A query string \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e is now handled as follows: you\n compute both \u003cspan class\u003d\"tex2jax_process\"\u003e$h_1(q)$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$h_2(q)$\u003c/span\u003e, and if\n \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_1(q)]\u003dq$\u003c/span\u003e, \u003cem\u003eor\u003c/em\u003e\n \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_2(q)]\u003dq$\u003c/span\u003e, you\n conclude that \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e is in\n \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e. The name “Cuckoo\n Hashing” stems from the process of creating the table.\n Initially you have an empty table. You iterate over the words\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e in \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e, and insert them one by one. If\n \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_1(d)]$\u003c/span\u003e is free, you\n set \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_1(d)]\u003dd$\u003c/span\u003e.\n Otherwise if \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_2(d)]$\u003c/span\u003e\n is free, you set \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_2(d)]\u003dd$\u003c/span\u003e. If both are occupied\n however, just like the cuckoo with other birds’ eggs, you evict\n the word \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e in\n \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_1(d)]$\u003c/span\u003e and set\n \u003cspan class\u003d\"tex2jax_process\"\u003e$T[h_1(d)]\u003dd$\u003c/span\u003e. Next you\n put \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e back into the\n table in its alternative place (and if that entry was already\n occupied you evict that word and move it to its alternative\n place, and so on). Of course, we may end up in an infinite loop\n here, in which case we need to rebuild the table with other\n choices of hash functions. The good news is that this will not\n happen with great probability even if \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e contains up to \u003cspan class\u003d\"tex2jax_process\"\u003e$n/2$\u003c/span\u003e words!\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eOn the first line of input is a single positive integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq t \\leq 50$\u003c/span\u003e\n specifying the number of test cases to follow. Each test case\n begins with two positive integers \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq m \\leq n \\leq 10000$\u003c/span\u003e on a line\n of itself, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e telling the\n number of words in the dictionary and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e the size of the hash table in the\n test case. Next follow \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines of which the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e:th\n describes the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e:th word\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ i$\u003c/span\u003e in the dictionary\n \u003cspan class\u003d\"tex2jax_process\"\u003e${D}$\u003c/span\u003e by two non-negative\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$h_1(d_ i)$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$h_2(d_ i)$\u003c/span\u003e less than\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e giving the two hash\n function values of the word \u003cspan class\u003d\"tex2jax_process\"\u003e$d_\n i$\u003c/span\u003e. The two values may be identical.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eFor each test case there should be exactly one line of\n output either containing the string “\u003ctt class\u003d\"ttfamily\"\u003esuccessful hashing\u003c/tt\u003e” if it is possible to insert\n all words in the given order into the table, or the string\n “\u003ctt class\u003d\"ttfamily\"\u003erehash necessary\u003c/tt\u003e” if it is\n impossible.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 3\n0 1\n1 2\n2 0\n5 6\n2 3\n3 1\n1 2\n5 1\n2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003esuccessful hashing\nrehash necessary\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}