{"problem":{"name":"J. Majestic Warriors of China","description":{"content":"_The Terracotta Army is a collection of terracotta sculptures depicting the armies of Qin Shi Huang, the first Emperor of China. It is a form of funerary art buried with the emperor in 210–209 BCE wit","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10275J"},"statements":[{"statement_type":"Markdown","content":"_The Terracotta Army is a collection of terracotta sculptures depicting the armies of Qin Shi Huang, the first Emperor of China. It is a form of funerary art buried with the emperor in 210–209 BCE with the purpose of protecting the emperor in his afterlife._\n\nAang has been commissioned to create these fearsome warriors, and observes that the requested designs share many similarities. In fact, Aang has been able to narrow down the list of features shared by the statues to a list of only $K$ different features. For example, statues with feature #$1$ might hold a sword, statues with feature #$2$ might have a unique insignia, and so on.\n\nAang has even devised a concise way to describe each statue in terms of its \"feature ID\", a single $K$-bit integer whose binary representation tells us the set of features exhibited by the statue. As an example, suppose a statue has feature ID $13$. Since $13$ written in binary is $1101$, this means our statue exhibits features $1$, $3$, and $4$ (reading right to left), but not feature $2$. As a more general rule of thumb, we find a $1$ in the $2^(i -1)$ place if a statue exhibits feature $i$.\n\nAlways the curious fellow, Aang lined up statues $1 \\\\dots N$ in a long row and noticed that certain ranges of statues are somewhat \"majestic\" in terms of the features they exhibit. A contiguous range of statues $i \\\\dots j$ is majestic if each of the $K$ possible features is exhibited by the same number of statues in the range. Aang would like to find the largest majestic range of statues, but it is quite difficult for him to keep track of an entire army. Can you give our protagonist a hand?\n\nThe first line of input for each test case contains two integers $N$ ($1 <= N <= 100000$) and $K$ ($1 <= K <= 30$) representing the number of terracotta sculptures Aang has lined up and the number of features Aang has found, respectively. The next $N$ lines of input each contain a single integer $f_i$ ($0 <= f_i <= 2^K -1$) specifying the features present in statue $i$ using the encoding format described above. \n\nOutput a single integer representing the longest majestic range within the $N$ selected sculptures.\n\nIn the sample input, statues 3 through 6 (inclusive) form a majestic sequence of length 4.\n\n## Input\n\nThe first line of input for each test case contains two integers $N$ ($1 <= N <= 100000$) and $K$ ($1 <= K <= 30$) representing the number of terracotta sculptures Aang has lined up and the number of features Aang has found, respectively. The next $N$ lines of input each contain a single integer $f_i$ ($0 <= f_i <= 2^K -1$) specifying the features present in statue $i$ using the encoding format described above. \n\n## Output\n\nOutput a single integer representing the longest majestic range within the $N$ selected sculptures.\n\n[samples]\n\n## Note\n\nIn the sample input, statues 3 through 6 (inclusive) form a majestic sequence of length 4.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, K \\in \\mathbb{Z}^+ $ with $ 1 \\leq N \\leq 100000 $, $ 1 \\leq K \\leq 30 $.  \nLet $ F = (f_1, f_2, \\dots, f_N) $ be a sequence of integers, where each $ f_i \\in [0, 2^K - 1] $ represents the feature mask of statue $ i $.  \nFor each feature $ j \\in \\{1, \\dots, K\\} $, define the indicator function:  \n$$\nb_{i,j} = \\begin{cases}\n1 & \\text{if the } j\\text{-th bit of } f_i \\text{ is } 1 \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\nFor a contiguous subarray (range) $ [i, j] $, define the feature count vector:  \n$$\nC_{i,j} = (c_1, c_2, \\dots, c_K), \\quad \\text{where } c_j = \\sum_{\\ell=i}^{j} b_{\\ell,j}\n$$\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 100000 $  \n2. $ 1 \\leq K \\leq 30 $  \n3. $ 0 \\leq f_i < 2^K $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nFind the maximum length $ j - i + 1 $ of a contiguous subarray $ [i, j] $ such that:  \n$$\nc_1 = c_2 = \\dots = c_K\n$$  \ni.e., all $ K $ features appear the same number of times in the range.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10275J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}