CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:1
Submission time:2018-10-12 16:30:55 +0300
Language:Python3
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.04 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.07 s1details
#6ACCEPTED0.70 s1details
#7ACCEPTED0.09 s1details
#8ACCEPTED0.05 s1details
#9ACCEPTED0.06 s1details
#10ACCEPTED0.06 s1details
#11ACCEPTED0.04 s2details
#12ACCEPTED0.06 s2details
#13ACCEPTED0.05 s2details
#14ACCEPTED0.07 s2details
#15ACCEPTED0.10 s2details
#16ACCEPTED0.11 s2details
#17ACCEPTED0.12 s2details
#18ACCEPTED0.12 s2details
#19ACCEPTED0.12 s2details
#20ACCEPTED0.15 s2details
#210.13 s3details
#220.13 s3details
#230.13 s3details
#240.13 s3details
#250.14 s3details
#260.13 s3details
#270.13 s3details
#280.13 s3details
#290.13 s3details
#300.11 s3details

Code

import copy

n = int(input())
board = []
for i in range(0, n):
    board.append(list(input()))

def fill(l, symbol):
    for i in range(0, len(l)):
        l[i] = symbol
    return l

# set all rows and columns for both symbols as not forbidden (value of 0)
forbiddenZones = {"A": [fill(list(range(n)), 0), fill(list(range(n)), 0)], "B": [fill(list(range(n)), 0), fill(list(range(n)), 0)]}

for x in range(0, n): # update forbidden zones based on initial board arrangement
    for y in range(0, n):
        if board[x][y] == "A":
            forbiddenZones["A"][0][x] = 1
            forbiddenZones["A"][1][y] = 1
        elif board[x][y] == "B":
            forbiddenZones["B"][0][x] = 1
            forbiddenZones["B"][1][y] = 1

def possibleRowCompletions(symbols, restrictedsA, restrictedsB):
    # find all ways to complete a row such that it contains certain symbols that cannot be placed in certain places
    completedTrails = []
    def searcher(remainingSymbols, rstrA, rstrB, length, trail):
        if len(trail) == n:
            completedTrails.append(trail)
        choices = []
        if "A" in remainingSymbols and rstrA[0] != 1:
            choices.append("A")
        if "B" in remainingSymbols and rstrB[0] != 1:
            choices.append("B")
        if len(remainingSymbols) != length:
            choices.append(".")
        for choice in choices:
            searcher([x for x in remainingSymbols if x != choice], rstrA[1:], rstrB[1:], length - 1, trail + [choice])
    searcher(symbols, restrictedsA, restrictedsB, n, [])
    return completedTrails

def arrangementFinder(b, forbidden, rowNum):
    if 0 not in forbidden["A"][0] and 0 not in forbidden["A"][1] and 0 not in forbidden["B"][0] and 0 not in forbidden["B"][1]:
        return 1
    sum = 0
    symbols = []
    restrictedsA = []
    restrictedsB = []
    if forbidden["A"][0][rowNum] == 0:
        symbols.append("A")
        for x in range(0, n):
            if forbidden["A"][1][x] == 1 or b[rowNum][x] != ".":
                restrictedsA.append(1)
            else:
                restrictedsA.append(0)
    else:
        restrictedsA = [0] * n
    if forbidden["B"][0][rowNum] == 0:
        symbols.append("B")
        for x in range(0, n):
            if forbidden["B"][1][x] == 1 or b[rowNum][x] != ".":
                restrictedsB.append(1)
            else:
                restrictedsB.append(0)
    else:
        restrictedsB = [0] * n
    rowCompletions = possibleRowCompletions(symbols, restrictedsA, restrictedsB)
    if len(rowCompletions) == 0:
        return 0
    else:
        for row in rowCompletions:
            newForbidden = copy.deepcopy(forbidden)
            if "A" in row:
                newForbidden["A"][0][rowNum] = 1
                newForbidden["A"][1][row.index("A")] = 1
            if "B" in row:
                newForbidden["B"][0][rowNum] = 1
                newForbidden["B"][1][row.index("B")] = 1
            sum += arrangementFinder(b[0:rowNum] + [row] + b[rowNum+1:], newForbidden, rowNum + 1)
        return sum

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

derangementsTable = [-1]*501

def derangements(n):
    if n == 0:
        return 1
    elif n == 1:
        return 0
    else:
        if derangementsTable[n] != -1:
            return derangementsTable[n]
        else:
            ans = (n - 1) * (derangements(n - 1) + derangements(n - 2))
            derangementsTable[n] = ans
            return ans

if n > 5:
    print((factorial(n) * derangements(n)) % (10**9 + 7))
else:
    answer = arrangementFinder(board, forbiddenZones, 0)
    print(str(answer))

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..

correct output
2

user output
2

Test 2

Group: 1

Verdict: ACCEPTED

input
2
..
A.

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A

correct output
0

user output
0

Test 4

Group: 1

Verdict: ACCEPTED

input
3
...
...
...

correct output
12

user output
12

Test 5

Group: 1

Verdict: ACCEPTED

input
4
....
....
....
....

correct output
216

user output
216

Test 6

Group: 1

Verdict: ACCEPTED

input
5
.....
.....
.....
.....
...

correct output
5280

user output
5280

Test 7

Group: 1

Verdict: ACCEPTED

input
5
....A
.....
.....
.....
...

correct output
264

user output
264

Test 8

Group: 1

Verdict: ACCEPTED

input
5
B....
.....
.....
.A.B.
...

correct output
22

user output
22

Test 9

Group: 1

Verdict: ACCEPTED

input
5
B.A..
....A
.....
A.B..
...

correct output
2

user output
2

Test 10

Group: 1

Verdict: ACCEPTED

input
5
A.B..
BA...
.B.A.
...BA
...

correct output
1

user output
1

Test 11

Group: 2

Verdict: ACCEPTED

input
10
..........
..........
..........
..........
...

correct output
306442892

user output
306442892

Test 12

Group: 2

Verdict: ACCEPTED

input
50
.................................

correct output
694861480

user output
694861480

Test 13

Group: 2

Verdict: ACCEPTED

input
111
.................................

correct output
555319110

user output
555319110

Test 14

Group: 2

Verdict: ACCEPTED

input
222
.................................

correct output
108372237

user output
108372237

Test 15

Group: 2

Verdict: ACCEPTED

input
333
.................................

correct output
259107857

user output
259107857

Test 16

Group: 2

Verdict: ACCEPTED

input
444
.................................

correct output
19906314

user output
19906314

Test 17

Group: 2

Verdict: ACCEPTED

input
497
.................................

correct output
224313667

user output
224313667

Test 18

Group: 2

Verdict: ACCEPTED

input
498
.................................

correct output
929574601

user output
929574601

Test 19

Group: 2

Verdict: ACCEPTED

input
499
.................................

correct output
600226043

user output
600226043

Test 20

Group: 2

Verdict: ACCEPTED

input
500
.................................

correct output
198353194

user output
198353194

Test 21

Group: 3

Verdict:

input
499
.................................

correct output
840243733

user output
600226043

Test 22

Group: 3

Verdict:

input
499
........................A........

correct output
4146290

user output
600226043

Test 23

Group: 3

Verdict:

input
499
B.........A......................

correct output
173518884

user output
600226043

Test 24

Group: 3

Verdict:

input
499
...A....B........................

correct output
20044800

user output
600226043

Test 25

Group: 3

Verdict:

input
499
AB...............................

correct output
2

user output
600226043

Test 26

Group: 3

Verdict:

input
500
.................................

correct output
121064146

user output
198353194

Test 27

Group: 3

Verdict:

input
500
.................................

correct output
848435259

user output
198353194

Test 28

Group: 3

Verdict:

input
500
.....B........A..................

correct output
296240911

user output
198353194

Test 29

Group: 3

Verdict:

input
500
.A......B........................

correct output
2196

user output
198353194

Test 30

Group: 3

Verdict:

input
500
...AB............................

correct output
1

user output
198353194