{"problem":{"name":"B. Bored Dreamoon","description":{"content":"Dreamoon serves in the military this year. Everything in the military is boring. In order to make military life more interesting, Dreamoon decided to transform some of his military experiences into pr","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10123B"},"statements":[{"statement_type":"Markdown","content":"Dreamoon serves in the military this year. Everything in the military is boring. In order to make military life more interesting, Dreamoon decided to transform some of his military experiences into programming competition problems.\n\nThe leaders usually order soldiers to stand in several rows ordered by their heights. The rules of arrangement of soldiers are as follows:\n\nAfter Dreamoon noticed these properties, the following problem came to his mind:\n\nFor two different soldiers A and B, we say B is _right front_ of A if A's row is *NOT* in front of the B's row, and the number of soldiers to the right of B in B's row is not larger than the number of soldiers to the right of A in A's row.\n\nYou don't know how many soldiers there are in total, and you don't know how many rows these soldiers are arranged into. But you have some information about certain N soldiers, numbered from 1 through N. You are given the heights of these soldiers. And for any two distinct numbers i and j, you know whether soldier j is right front of i. Please inspect whether there exists at least one possible configuration satisfying the given information. If possible, you should calculate the minimum number of soldiers in the first row (the row in front of every other row).\n\nThe first line of input contains one integer N indicating that you have information of N soldiers. The second line of input consists of N integers h1, h2, ..., hN. Here, hi indicates the height of i-th soldier. Note that the unknown heights of the soldiers are allowed to be non-integers.\n\nEach of the following N lines contains N characters. The j-th character in the i-th of these lines is '_1_' if soldier j is right front of soldier i; otherwise, it is '_0_'.\n\nOutput one number indicating the minimum possible number of soldiers in the first row (the row in front of every other row). If there is no possible configuration satisfying the given information, output  - 1 instead.\n\n## Input\n\nThe first line of input contains one integer N indicating that you have information of N soldiers. The second line of input consists of N integers h1, h2, ..., hN. Here, hi indicates the height of i-th soldier. Note that the unknown heights of the soldiers are allowed to be non-integers.Each of the following N lines contains N characters. The j-th character in the i-th of these lines is '_1_' if soldier j is right front of soldier i; otherwise, it is '_0_'.  2 ≤ N ≤ 103  1 ≤ hi ≤ 109  all hi are distinct     for all i in 1, 2, ..., N \n\n## Output\n\nOutput one number indicating the minimum possible number of soldiers in the first row (the row in front of every other row). If there is no possible configuration satisfying the given information, output  - 1 instead.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of known soldiers.  \nLet $ h = (h_1, h_2, \\dots, h_N) \\in \\mathbb{R}^N $ be the vector of their heights.  \nLet $ R \\in \\{0,1\\}^{N \\times N} $ be the adjacency matrix where $ R[i][j] = 1 $ iff soldier $ j $ is *right front* of soldier $ i $.\n\n**Constraints**  \n1. For all $ i, j \\in \\{1, \\dots, N\\} $, if $ R[i][j] = 1 $, then:  \n   - $ h_j \\leq h_i $ (soldier $ j $ is not taller than soldier $ i $),  \n   - The row of $ j $ is not in front of the row of $ i $,  \n   - The number of soldiers to the right of $ j $ in its row $ \\leq $ the number of soldiers to the right of $ i $ in its row.  \n2. The arrangement of all soldiers (known and unknown) must satisfy:  \n   - Soldiers are arranged in rows ordered by increasing row index (row 1 is frontmost),  \n   - Within each row, soldiers are ordered left to right by increasing index (arbitrary assignment),  \n   - Heights are non-decreasing from front to back rows and non-decreasing left to right within a row.  \n3. The *right front* relation must be consistent with the global row and position assignment.\n\n**Objective**  \nDetermine the minimum possible number of soldiers in row 1 (front row) over all valid configurations satisfying the above constraints. If no such configuration exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10123B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}