codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2060B.md (2960B)


      1 Source: https://codeforces.com/problemset/problem/2060/B
      2 
      3 B. Farmer John's Card Game
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Farmer John's $n$ cows are playing a card game! Farmer John has a deck of $n \cdot m$ cards numbered from $0$ to $n \cdot m-1$. He distributes $m$ cards to each of his $n$ cows.
     22 
     23 Farmer John wants the game to be fair, so each cow should only be able to play $1$ card per round. He decides to determine a turn order, determined by a permutation$^{\text{∗}}$ $p$ of length $n$, such that the $p_i$'th cow will be the $i$'th cow to place a card on top of the center pile in a round.
     24 
     25 In other words, the following events happen in order in each round:
     26 
     27 * The $p_1$'th cow places any card from their deck on top of the center pile.
     28 * The $p_2$'th cow places any card from their deck on top of the center pile.
     29 * ...
     30 * The $p_n$'th cow places any card from their deck on top of the center pile.
     31 
     32 There is a catch. Initially, the center pile contains a card numbered $-1$. In order to place a card, the number of the card must be greater than the number of the card on top of the center pile. Then, the newly placed card becomes the top card of the center pile. If a cow cannot place any card in their deck, the game is considered to be lost.
     33 
     34 Farmer John wonders: does there exist $p$ such that it is possible for all of his cows to empty their deck after playing all $m$ rounds of the game? If so, output any valid $p$. Otherwise, output $-1$.
     35 
     36 $^{\text{∗}}$A permutation of length $n$ contains each integer from $1$ to $n$ exactly once
     37 
     38 Input
     39 
     40 The first line contains an integer $t$ ($1 \leq t \leq 400$) — the number of test cases.
     41 
     42 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 2\,000$) — the number of cows and the number of cards each cow receives.
     43 
     44 The following $n$ lines contain $m$ integers each – the cards received by each cow. It is guaranteed all given numbers (across all $n$ lines) are distinct and in the range from $0$ to $n \cdot m - 1$, inclusive.
     45 
     46 It is guaranteed the sum of $n \cdot m$ over all test cases does not exceed $2\,000$.
     47 
     48 Output
     49 
     50 For each test case, output the following on a new line:
     51 
     52 * If $p$ exists, output $n$ space-separated integers $p_1, p_2, \ldots, p_n$.
     53 * Otherwise, output $-1$.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 4
     61 
     62 2 3
     63 
     64 0 4 2
     65 
     66 1 5 3
     67 
     68 1 1
     69 
     70 0
     71 
     72 2 2
     73 
     74 1 2
     75 
     76 0 3
     77 
     78 4 1
     79 
     80 1
     81 
     82 2
     83 
     84 0
     85 
     86 3
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 1 2
     93 1
     94 -1
     95 3 1 2 4
     96 ```
     97 
     98 Note
     99 
    100 In the first test case, one turn order that allows all cards to be played is by having the first cow go before the second cow. The cards played will be $0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow5$.
    101 
    102 In the second test case, there is only one cow, so having the cow play all of her cards in increasing order will empty the deck.
    103 
    104 In the third test case, it can be shown there is no valid turn order that allows all cards to be played.