CSES - Aalto Competitive Programming 2024 - wk5 - Mon

CSES - Aalto Competitive Programming 2024 - wk5 - Mon - Results

Submission details
Task:	Kindergarten
Sender:	aalto2024e_003
Submission time:	2024-09-30 17:06:20 +0300
Language:	Python3 (CPython3)
Status:	READY
Result:	TIME LIMIT EXCEEDED

Test results
test	verdict	time
#1	ACCEPTED	0.02 s	details
#2	ACCEPTED	0.02 s	details
#3	ACCEPTED	0.02 s	details
#4	ACCEPTED	0.02 s	details
#5	ACCEPTED	0.02 s	details
#6	ACCEPTED	0.02 s	details
#7	ACCEPTED	0.02 s	details
#8	ACCEPTED	0.03 s	details
#9	ACCEPTED	0.02 s	details
#10	ACCEPTED	0.02 s	details
#11	ACCEPTED	0.02 s	details
#12	ACCEPTED	0.02 s	details
#13	ACCEPTED	0.02 s	details
#14	ACCEPTED	0.02 s	details
#15	ACCEPTED	0.02 s	details
#16	ACCEPTED	0.02 s	details
#17	ACCEPTED	0.02 s	details
#18	ACCEPTED	0.02 s	details
#19	ACCEPTED	0.02 s	details
#20	ACCEPTED	0.02 s	details
#21	ACCEPTED	0.04 s	details
#22	ACCEPTED	0.04 s	details
#23	ACCEPTED	0.04 s	details
#24	ACCEPTED	0.04 s	details
#25	ACCEPTED	0.04 s	details
#26	ACCEPTED	0.04 s	details
#27	ACCEPTED	0.04 s	details
#28	ACCEPTED	0.04 s	details
#29	ACCEPTED	0.04 s	details
#30	ACCEPTED	0.04 s	details
#31	TIME LIMIT EXCEEDED	--	details
#32	TIME LIMIT EXCEEDED	--	details
#33	TIME LIMIT EXCEEDED	--	details
#34	TIME LIMIT EXCEEDED	--	details
#35	TIME LIMIT EXCEEDED	--	details
#36	TIME LIMIT EXCEEDED	--	details
#37	TIME LIMIT EXCEEDED	--	details
#38	TIME LIMIT EXCEEDED	--	details
#39	TIME LIMIT EXCEEDED	--	details
#40	TIME LIMIT EXCEEDED	--	details
#41	TIME LIMIT EXCEEDED	--	details
#42	TIME LIMIT EXCEEDED	--	details
#43	TIME LIMIT EXCEEDED	--	details
#44	TIME LIMIT EXCEEDED	--	details
#45	TIME LIMIT EXCEEDED	--	details
#46	TIME LIMIT EXCEEDED	--	details
#47	TIME LIMIT EXCEEDED	--	details
#48	TIME LIMIT EXCEEDED	--	details
#49	TIME LIMIT EXCEEDED	--	details
#50	TIME LIMIT EXCEEDED	--	details
#51	TIME LIMIT EXCEEDED	--	details
#52	TIME LIMIT EXCEEDED	--	details
#53	TIME LIMIT EXCEEDED	--	details
#54	TIME LIMIT EXCEEDED	--	details
#55	TIME LIMIT EXCEEDED	--	details
#56	TIME LIMIT EXCEEDED	--	details
#57	TIME LIMIT EXCEEDED	--	details
#58	TIME LIMIT EXCEEDED	--	details
#59	TIME LIMIT EXCEEDED	--	details
#60	TIME LIMIT EXCEEDED	--	details
#61	TIME LIMIT EXCEEDED	--	details
#62	TIME LIMIT EXCEEDED	--	details
#63	TIME LIMIT EXCEEDED	--	details
#64	TIME LIMIT EXCEEDED	--	details
#65	TIME LIMIT EXCEEDED	--	details
#66	TIME LIMIT EXCEEDED	--	details
#67	TIME LIMIT EXCEEDED	--	details
#68	TIME LIMIT EXCEEDED	--	details
#69	TIME LIMIT EXCEEDED	--	details
#70	TIME LIMIT EXCEEDED	--	details
#71	TIME LIMIT EXCEEDED	--	details
#72	TIME LIMIT EXCEEDED	--	details
#73	TIME LIMIT EXCEEDED	--	details
#74	TIME LIMIT EXCEEDED	--	details
#75	TIME LIMIT EXCEEDED	--	details
#76	TIME LIMIT EXCEEDED	--	details
#77	TIME LIMIT EXCEEDED	--	details
#78	TIME LIMIT EXCEEDED	--	details
#79	TIME LIMIT EXCEEDED	--	details
#80	TIME LIMIT EXCEEDED	--	details
#81	TIME LIMIT EXCEEDED	--	details
#82	TIME LIMIT EXCEEDED	--	details
#83	TIME LIMIT EXCEEDED	--	details
#84	TIME LIMIT EXCEEDED	--	details
#85	TIME LIMIT EXCEEDED	--	details
#86	TIME LIMIT EXCEEDED	--	details
#87	TIME LIMIT EXCEEDED	--	details
#88	TIME LIMIT EXCEEDED	--	details
#89	TIME LIMIT EXCEEDED	--	details
#90	TIME LIMIT EXCEEDED	--	details

Code

import sys
from functools import lru_cache

def minimal_rivalry_sum(n, rivalry):
    
    @lru_cache(None)
    def dp(mask, last):
        if mask == (1 << n) - 1:
            return 0
        min_rivalry = sys.maxsize
        for next in range(n):
            if not (mask & (1 << next)): 
                new_mask = mask | (1 << next)
                min_rivalry = min(min_rivalry, dp(new_mask, next) + rivalry[last][next])
        return min_rivalry

    min_sum = sys.maxsize
    for first in range(n):
        min_sum = min(min_sum, dp(1 << first, first))

    return min_sum

n = int(input())
rivalry = [list(map(int, input().split())) for _ in range(n)]

print(minimal_rivalry_sum(n, rivalry))

Test details

Test 1

Verdict: ACCEPTED

input
`1 6` view save

correct output
`0` view save

user output
`0` view save

Test 2

Verdict: ACCEPTED

input
`1 4` view save

correct output
`0` view save

user output
`0` view save

Test 3

Verdict: ACCEPTED

input
`2 4 0 0 10` view save

correct output
`0` view save

user output
`0` view save

Test 4

Verdict: ACCEPTED

input
`2 6 7 7 9` view save

correct output
`7` view save

user output
`7` view save

Test 5

Verdict: ACCEPTED

input
`3 10 1 7 1 10 6 7 6 7` view save

correct output
`7` view save

user output
`7` view save

Test 6

Verdict: ACCEPTED

input
`3 2 9 10 9 2 10 10 10 5` view save

correct output
`19` view save

user output
`19` view save

Test 7

Verdict: ACCEPTED

input
`3 9 2 0 2 9 4 0 4 1` view save

correct output
`2` view save

user output
`2` view save

Test 8

Verdict: ACCEPTED

input
`4 0 4 10 5 4 10 3 0 10 3 5 0 5 0 0 4` view save

correct output
`4` view save

user output
`4` view save

Test 9

Verdict: ACCEPTED

input
`4 9 9 2 4 9 4 4 8 2 4 0 4 4 8 4 4` view save

correct output
`10` view save

user output
`10` view save

Test 10

Verdict: ACCEPTED

input
`4 0 5 1 4 5 0 0 1 1 0 2 2 4 1 2 1` view save

correct output
`2` view save

user output
`2` view save

Test 11

Verdict: ACCEPTED

input
`5 7 4 3 7 1 4 1 6 6 1 3 6 10 0 5 7 6 0 4 2 ...` view save

correct output
`5` view save

user output
`5` view save

Test 12

Verdict: ACCEPTED

input
`5 3 6 1 10 0 6 10 2 0 9 1 2 9 9 4 10 0 9 5 6 ...` view save

correct output
`3` view save

user output
`3` view save

Test 13

Verdict: ACCEPTED

input
`5 9 3 8 3 1 3 10 3 6 0 8 3 1 8 3 3 6 8 6 3 ...` view save

correct output
`7` view save

user output
`7` view save

Test 14

Verdict: ACCEPTED

input
`5 2 10 2 9 10 10 2 6 7 2 2 6 0 0 4 9 7 0 5 10 ...` view save

correct output
`11` view save

user output
`11` view save

Test 15

Verdict: ACCEPTED

input
`5 0 4 10 4 0 4 6 8 2 8 10 8 4 8 7 4 2 8 4 9 ...` view save

correct output
`13` view save

user output
`13` view save

Test 16

Verdict: ACCEPTED

input
`5 5 2 1 3 8 2 3 5 7 8 1 5 6 9 0 3 7 9 7 2 ...` view save

correct output
`5` view save

user output
`5` view save

Test 17

Verdict: ACCEPTED

input
`5 8 9 3 4 10 9 1 10 6 8 3 10 2 8 9 4 6 8 0 0 ...` view save

correct output
`15` view save

user output
`15` view save

Test 18

Verdict: ACCEPTED

input
`5 10 8 7 6 8 8 6 0 3 6 7 0 1 1 6 6 3 1 8 6 ...` view save

correct output
`13` view save

user output
`13` view save

Test 19

Verdict: ACCEPTED

input
`5 4 9 6 1 3 9 7 5 2 8 6 5 2 9 4 1 2 9 0 7 ...` view save

correct output
`10` view save

user output
`10` view save

Test 20

Verdict: ACCEPTED

input
`5 6 4 5 7 8 4 1 4 6 5 5 4 5 2 10 7 6 2 10 2 ...` view save

correct output
`12` view save

user output
`12` view save

Test 21

Verdict: ACCEPTED

input
`10 549 646 792 87 979 640 264 618...` view save

correct output
`1257` view save

user output
`1257` view save

Test 22

Verdict: ACCEPTED

input
`10 417 92 419 671 801 895 98 315 ...` view save

correct output
`1093` view save

user output
`1093` view save

Test 23

Verdict: ACCEPTED

input
`10 436 330 621 786 505 597 468 38...` view save

correct output
`1912` view save

user output
`1912` view save

Test 24

Verdict: ACCEPTED

input
`10 551 897 29 591 283 781 976 92 ...` view save

correct output
`1530` view save

user output
`1530` view save

Test 25

Verdict: ACCEPTED

input
`10 967 216 780 597 436 75 528 545...` view save

correct output
`1166` view save

user output
`1166` view save

Test 26

Verdict: ACCEPTED

input
`10 222 612 80 274 600 144 24 578 ...` view save

correct output
`1310` view save

user output
`1310` view save

Test 27

Verdict: ACCEPTED

input
`10 893 595 438 991 54 541 717 718...` view save

correct output
`1942` view save

user output
`1942` view save

Test 28

Verdict: ACCEPTED

input
`10 76 539 679 910 601 133 205 838...` view save

correct output
`2202` view save

user output
`2202` view save

Test 29

Verdict: ACCEPTED

input
`10 874 11 555 426 65 224 28 320 6...` view save

correct output
`987` view save

user output
`987` view save

Test 30

Verdict: ACCEPTED

input
`10 10 218 166 573 386 804 650 874...` view save

correct output
`1545` view save

user output
`1545` view save

Test 31

Verdict: TIME LIMIT EXCEEDED

input
`16 78876117 17293464 73807511 451...` view save

correct output
`141535044` view save

user output
(empty)

Test 32

Verdict: TIME LIMIT EXCEEDED

input
`16 18434581 96310208 2094677 8835...` view save

correct output
`217719706` view save

user output
(empty)

Test 33

Verdict: TIME LIMIT EXCEEDED

input
`16 15764865 97858716 92778181 718...` view save

correct output
`167604914` view save

user output
(empty)

Test 34

Verdict: TIME LIMIT EXCEEDED

input
`16 79528724 65612103 26207475 638...` view save

correct output
`140515513` view save

user output
(empty)

Test 35

Verdict: TIME LIMIT EXCEEDED

input
`16 52556424 55139192 95364389 546...` view save

correct output
`140013397` view save

user output
(empty)

Test 36

Verdict: TIME LIMIT EXCEEDED

input
`16 86801053 11426789 72187831 966...` view save

correct output
`93732738` view save

user output
(empty)

Test 37

Verdict: TIME LIMIT EXCEEDED

input
`16 22833997 7191499 71236196 3216...` view save

correct output
`115026040` view save

user output
(empty)

Test 38

Verdict: TIME LIMIT EXCEEDED

input
`16 30132775 3994617 56422716 4279...` view save

correct output
`122521730` view save

user output
(empty)

Test 39

Verdict: TIME LIMIT EXCEEDED

input
`16 66508002 86884113 88110850 970...` view save

correct output
`206680250` view save

user output
(empty)

Test 40

Verdict: TIME LIMIT EXCEEDED

input
`16 9973896 65003382 54473078 6575...` view save

correct output
`105290977` view save

user output
(empty)

Test 41

Verdict: TIME LIMIT EXCEEDED

input
`16 60142917 67282857 11933232 463...` view save

correct output
`149892373` view save

user output
(empty)

Test 42

Verdict: TIME LIMIT EXCEEDED

input
`16 4982660 31508124 77610451 9338...` view save

correct output
`208191625` view save

user output
(empty)

Test 43

Verdict: TIME LIMIT EXCEEDED

input
`16 21317409 22538814 78950075 437...` view save

correct output
`141684927` view save

user output
(empty)

Test 44

Verdict: TIME LIMIT EXCEEDED

input
`16 52899464 63202728 6654687 1447...` view save

correct output
`162046504` view save

user output
(empty)

Test 45

Verdict: TIME LIMIT EXCEEDED

input
`16 98172450 57262621 54713540 967...` view save

correct output
`151356452` view save

user output
(empty)

Test 46

Verdict: TIME LIMIT EXCEEDED

input
`16 88979873 56880637 33342355 868...` view save

correct output
`159671124` view save

user output
(empty)

Test 47

Verdict: TIME LIMIT EXCEEDED

input
`16 31489774 75583422 98416671 495...` view save

correct output
`177673400` view save

user output
(empty)

Test 48

Verdict: TIME LIMIT EXCEEDED

input
`16 43534750 41244279 21038793 242...` view save

correct output
`174069522` view save

user output
(empty)

Test 49

Verdict: TIME LIMIT EXCEEDED

input
`16 74549766 97697405 65731362 223...` view save

correct output
`164091596` view save

user output
(empty)

Test 50

Verdict: TIME LIMIT EXCEEDED

input
`16 88329068 78556994 29213132 737...` view save

correct output
`150948961` view save

user output
(empty)

Test 51

Verdict: TIME LIMIT EXCEEDED

input
`16 11868309 52454190 2188140 3426...` view save

correct output
`145704982` view save

user output
(empty)

Test 52

Verdict: TIME LIMIT EXCEEDED

input
`16 62601211 24407904 38967625 742...` view save

correct output
`165774974` view save

user output
(empty)

Test 53

Verdict: TIME LIMIT EXCEEDED

input
`16 38353763 90537037 98227382 885...` view save

correct output
`128735723` view save

user output
(empty)

Test 54

Verdict: TIME LIMIT EXCEEDED

input
`16 87124995 71164598 85140576 178...` view save

correct output
`88146905` view save

user output
(empty)

Test 55

Verdict: TIME LIMIT EXCEEDED

input
`16 15506055 73736552 44372116 853...` view save

correct output
`139764802` view save

user output
(empty)

Test 56

Verdict: TIME LIMIT EXCEEDED

input
`16 20052620 55628826 15868440 899...` view save

correct output
`112678656` view save

user output
(empty)

Test 57

Verdict: TIME LIMIT EXCEEDED

input
`16 38365166 78120078 30444983 287...` view save

correct output
`180080436` view save

user output
(empty)

Test 58

Verdict: TIME LIMIT EXCEEDED

input
`16 46161809 99247781 74790752 906...` view save

correct output
`192231810` view save

user output
(empty)

Test 59

Verdict: TIME LIMIT EXCEEDED

input
`16 96396611 61707575 39771927 957...` view save

correct output
`157075200` view save

user output
(empty)

Test 60

Verdict: TIME LIMIT EXCEEDED

input
`16 86701456 19718778 48320555 202...` view save

correct output
`171350081` view save

user output
(empty)

Test 61

Verdict: TIME LIMIT EXCEEDED

input
`16 10218362 40742172 91128924 285...` view save

correct output
`127429234` view save

user output
(empty)

Test 62

Verdict: TIME LIMIT EXCEEDED

input
`16 79903579 1974104 24354885 4902...` view save

correct output
`119531862` view save

user output
(empty)

Test 63

Verdict: TIME LIMIT EXCEEDED

input
`16 23816783 24638719 49178170 814...` view save

correct output
`161233528` view save

user output
(empty)

Test 64

Verdict: TIME LIMIT EXCEEDED

input
`16 22336543 34284046 7826114 4407...` view save

correct output
`172344121` view save

user output
(empty)

Test 65

Verdict: TIME LIMIT EXCEEDED

input
`16 4933488 53040995 75121239 3334...` view save

correct output
`150345908` view save

user output
(empty)

Test 66

Verdict: TIME LIMIT EXCEEDED

input
`16 15740195 82161403 83343605 558...` view save

correct output
`177299100` view save

user output
(empty)

Test 67

Verdict: TIME LIMIT EXCEEDED

input
`16 3639374 43311419 10627086 4629...` view save

correct output
`181883199` view save

user output
(empty)

Test 68

Verdict: TIME LIMIT EXCEEDED

input
`16 10600561 29567300 26714920 537...` view save

correct output
`153201253` view save

user output
(empty)

Test 69

Verdict: TIME LIMIT EXCEEDED

input
`16 34181158 4262559 25064528 1281...` view save

correct output
`110754397` view save

user output
(empty)

Test 70

Verdict: TIME LIMIT EXCEEDED

input
`16 1379850 55703817 5455026 69880...` view save

correct output
`150243591` view save

user output
(empty)

Test 71

Verdict: TIME LIMIT EXCEEDED

input
`16 69328497 20779089 35701876 660...` view save

correct output
`163180293` view save

user output
(empty)

Test 72

Verdict: TIME LIMIT EXCEEDED

input
`16 11384815 61579628 8695610 1495...` view save

correct output
`161906149` view save

user output
(empty)

Test 73

Verdict: TIME LIMIT EXCEEDED

input
`16 16054161 19304150 57152778 337...` view save

correct output
`159099477` view save

user output
(empty)

Test 74

Verdict: TIME LIMIT EXCEEDED

input
`16 71221723 14311522 45021194 426...` view save

correct output
`216877591` view save

user output
(empty)

Test 75

Verdict: TIME LIMIT EXCEEDED

input
`16 10846316 79755467 74445718 590...` view save

correct output
`135548636` view save

user output
(empty)

Test 76

Verdict: TIME LIMIT EXCEEDED

input
`16 51818372 6753746 10792121 3914...` view save

correct output
`164259241` view save

user output
(empty)

Test 77

Verdict: TIME LIMIT EXCEEDED

input
`16 10755019 44179719 41876247 694...` view save

correct output
`133696572` view save

user output
(empty)

Test 78

Verdict: TIME LIMIT EXCEEDED

input
`16 53567785 71579417 82569781 317...` view save

correct output
`150763443` view save

user output
(empty)

Test 79

Verdict: TIME LIMIT EXCEEDED

input
`16 88623279 34185830 73137414 387...` view save

correct output
`198014364` view save

user output
(empty)

Test 80

Verdict: TIME LIMIT EXCEEDED

input
`16 58343206 9110482 88825117 5032...` view save

correct output
`131581281` view save

user output
(empty)

Test 81

Verdict: TIME LIMIT EXCEEDED

input
`16 36829570 59249556 69795996 491...` view save

correct output
`149993947` view save

user output
(empty)

Test 82

Verdict: TIME LIMIT EXCEEDED

input
`16 55892938 61714751 75014144 212...` view save

correct output
`171851792` view save

user output
(empty)

Test 83

Verdict: TIME LIMIT EXCEEDED

input
`16 53792259 75175740 86691312 687...` view save

correct output
`261201544` view save

user output
(empty)

Test 84

Verdict: TIME LIMIT EXCEEDED

input
`16 83382234 98447679 33400623 580...` view save

correct output
`174166475` view save

user output
(empty)

Test 85

Verdict: TIME LIMIT EXCEEDED

input
`16 49232089 54075676 50668211 720...` view save

correct output
`138328462` view save

user output
(empty)

Test 86

Verdict: TIME LIMIT EXCEEDED

input
`16 29877190 8099586 92371257 8541...` view save

correct output
`103011096` view save

user output
(empty)

Test 87

Verdict: TIME LIMIT EXCEEDED

input
`16 91519337 33138162 11320405 226...` view save

correct output
`148911385` view save

user output
(empty)

Test 88

Verdict: TIME LIMIT EXCEEDED

input
`16 13035374 24654480 36933166 555...` view save

correct output
`141610494` view save

user output
(empty)

Test 89

Verdict: TIME LIMIT EXCEEDED

input
`16 43339370 14613386 9518839 2982...` view save

correct output
`126679049` view save

user output
(empty)

Test 90

Verdict: TIME LIMIT EXCEEDED

input
`16 9921885 71587757 22396864 1673...` view save

correct output
`139350643` view save

user output
(empty)

Aalto Competitive Programming 2024 - wk5 - Mon

Kindergarten

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Test 68

Test 69

Test 70

Test 71

Test 72

Test 73

Test 74

Test 75

Test 76