Fork me on GitHub
Picture by Fernando Frazão/Agência Brasil, (CC BY 3.0 BR)

Status

Submission accepted on Kattis Problem Archive

Files

mon@razerRamon:~/tmp/ncpc17$ ll
total 109M
drwxrwxr-x 3 mon mon 4.0K Oct 14 16:42 assets/
drwxrwxr-x 13 mon mon 4.0K Oct 14 12:34 ncpc2017-testdata/
-rwxrwxr-x 1 mon mon 257 Oct 14 16:19 BestRelayTeam.bash*
-rwxrwxr-x 1 mon mon 4.0K Oct 14 16:23 BestRelayTeam.hs*
-rw-rw-r-- 1 mon mon 699 Oct 14 16:24 BestRelayTeam.sample.output
-rw-rw-r-- 1 mon mon 138K Oct 14 16:24 BestRelayTeam.secret.output
-rw-rw-r-- 1 mon mon 59K Oct 7 12:19 Language Haskell - Kattis, The 2017 Nordic Collegiate Programming Contest.pdf
-rw-rw-r-- 1 mon mon 4.7M Oct 7 12:29 ncpc2017problems.pdf
-rw-rw-r-- 1 mon mon 104M Oct 11 09:00 ncpc2017-testdata.tar.bz2
-rwxrwxr-x 1 mon mon 1.2K Oct 14 14:00 ScriptTemplate.hs*
-rw-rw-r-- 1 mon mon 8 Oct 7 12:42 ScriptTemplate.input
mon@razerRamon:~/tmp/ncpc17$

Haskell Code Snippet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#!/usr/bin/env stack
{- stack
--resolver ghc-7.10.3
--install-ghc
runghc
--
-rtsopts -ferror-spans
+RTS -M1024m -K8m -RTS
-}


{-
* GHC used by NCPC:
The Glorious Glasgow Haskell Compilation System version 7.10.3

* Flags required by NCPC:
-O2 -threaded -rtsopts -ferror-spans
+RTS -M{memlim}m -K8m -RTS

... but, due to warnings (ignored), some are removed:
when making flags consistent: Warning:
-O conflicts with --interactive; -O ignored.
Warning: -debug, -threaded and -ticky are ignored by GHCi

* Flags in order to make optimal code (exhaustive):
-Wall -Werror

... but if used, it would require way more code (time is mana)
-}


module Main (main) where

data Runner = Runner
{ surname :: String
, fstleg :: Double
, sndleg :: Double
}

data Runners = Runners
{ number :: Int
, athletes :: [Runner]
}

data RelayTeam = RelayTeam
{ time :: Double
, first :: Runner
, second :: Runner
, third :: Runner
, fourth :: Runner
}

instance Eq Runner where
Runner name1 fstleg1 sndleg1 == Runner name2 fstleg2 sndleg2 =
name1 == name2 && fstleg1 == fstleg2 && sndleg1 == sndleg2
Runner name1 fstleg1 sndleg1 /= Runner name2 fstleg2 sndleg2 =
name1 /= name2 || fstleg1 /= fstleg2 || sndleg1 /= sndleg2

instance Read Runner where
readsPrec _ input =
let
aux [ ] = []
aux (name:fstleg:sndleg:[]) =
[(Runner name (read fstleg) (read sndleg), "")]
aux [ _ ] = []
in
aux $ words input

instance Read Runners where
readsPrec _ input =
let
aux [ ] = []
aux (x:xs) =
let
nr = read x
in
[(Runners nr (aux' nr xs), "")]
aux' 0 [ ] = [ ]
aux' n (x:xs) = (read x) : aux' (n-1) xs
in
aux $ lines input

instance Show Runner where
show (Runner surname _ _) = surname

instance Show RelayTeam where
show (RelayTeam time first second third fourth) =
show time ++ "\n" ++
show first ++ "\n" ++
show second ++ "\n" ++
show third ++ "\n" ++
show fourth ++ "\n"

nrdec :: Double -> Int -> Double
nrdec x n =
fromIntegral (round $ x * z) / z
where z = 10 ^ n

solve :: Runners -> RelayTeam
solve (Runners _ xs) =
let
dummy = Runner "DUMMY" 9999.99 9999.99
init = (dummy,dummy,dummy,dummy)

ftime (Runner _ t _) = t
stime (Runner _ _ t) = t
bstime (a,b,c,d) (w,x,y,z) =
stime a + stime b + stime c + stime d <
stime w + stime x + stime y + stime z
bctime (a,b,c,d) (w,x,y,z) =
ftime a + stime b + stime c + stime d <
ftime w + stime x + stime y + stime z

aux (a,b,c,d) _ [ ] =
RelayTeam (nrdec (ftime a + stime b + stime c + stime d) 2) a b c d
aux acc (a,b,c,d) (y:ys) =
{- Linear time with only 8 extra memory usage -}
let
abcd =
if a == y then
(y,b,c,d)
else
if b == y then
(y,a,c,d)
else
if c == y then
(y,a,b,d)
else
(y,a,b,c)
in
if bctime abcd acc then
aux abcd (a,b,c,d) ys
else
aux acc (a,b,c,d) ys

aux' (a,b,c,d) [ ] = (a,b,c,d)
aux' (a,b,c,d) (y:ys) =
{- Linear time with only 4 extra memory usage -}
if bstime (y,b,c,d) (a,b,c,d) then
aux' (y,b,c,d) (a:ys)
else
if bstime (a,y,c,d) (a,b,c,d) then
aux' (a,y,c,d) (b:ys)
else
if bstime (a,b,y,d) (a,b,c,d) then
aux' (a,b,y,d) (c:ys)
else
if bstime (a,b,c,y) (a,b,c,d) then
aux' (a,b,c,y) (d:ys)
else
aux' (a,b,c,d) ys
in
aux init (aux' init xs) xs

readInput :: String -> Runners
readInput =
read

writeOutput :: RelayTeam -> String
writeOutput =
show

main :: IO ()
main =
interact $ writeOutput . solve . readInput

Haskell Code output:

BestRelayTeam.bash

#!/bin/bash

for f in $1*.in; do
echo " "
echo "- "$f
cat $f
echo "- "${f%.*}.ans
cat ${f%.*}.ans
echo "- result:"
cat $f | ./BestRelayTeam.hs
echo "- diff:"
cat $f | ./BestRelayTeam.hs | diff - ${f%.*}.ans
done

BestRelayTeam (sample)

./BestRelayTeam.bash ncpc2017-testdata/bestrelayteam/sample/

BestRelayTeam (sample output)

 
- ncpc2017-testdata/bestrelayteam/sample/1.in
6
ASHMEADE 9.90 8.85
BLAKE 9.69 8.72
BOLT 9.58 8.43
CARTER 9.78 8.93
FRATER 9.88 8.92
POWELL 9.72 8.61
- ncpc2017-testdata/bestrelayteam/sample/1.ans
35.54
CARTER
BOLT
POWELL
BLAKE
- result:
35.54
CARTER
BOLT
POWELL
BLAKE
- diff:

- ncpc2017-testdata/bestrelayteam/sample/2.in
9
AUSTRIN 15.60 14.92
DRANGE 15.14 14.19
DREGI 15.00 14.99
LAAKSONEN 16.39 14.97
LUNDSTROM 15.83 15.35
MARDELL 13.36 13.20
POLACEK 13.05 12.55
SANNEMO 15.23 14.74
SODERMAN 13.99 12.57
- ncpc2017-testdata/bestrelayteam/sample/2.ans
52.670000
MARDELL
POLACEK
SODERMAN
DRANGE
- result:
52.67
MARDELL
POLACEK
SODERMAN
DRANGE
- diff:
1c1
< 52.67
---
> 52.670000

BestRelayTeam (secret)

./BestRelayTeam.bash ncpc2017-testdata/bestrelayteam/secret/

BestRelayTeam (secret output, only diff)

- ncpc2017-testdata/bestrelayteam/secret/01-crazy.in
10
QXBINSJS 10.91 8.16
WKN 18.65 15.09
CPP 16.38 9.38
KDNLKJMYIWFSGYWY 12.53 11.18
KXS 19.64 13.63
OYCJANFTSGQTZMIJD 16.16 8.32
ZKGNNS 17.32 16.16
LDOYLWRXVXAJEVDOWXNF 13.02 12.58
IVONUZJE 11.52 10.37
KMEVNRHQSQPUYEYBP 18.71 9.63
- ncpc2017-testdata/bestrelayteam/secret/01-crazy.ans
37.38
IVONUZJE
QXBINSJS
OYCJANFTSGQTZMIJD
CPP
- result:
37.38
IVONUZJE
QXBINSJS
OYCJANFTSGQTZMIJD
CPP
- diff:

- ncpc2017-testdata/bestrelayteam/secret/02-crazy.in
50

...

- ncpc2017-testdata/bestrelayteam/secret/15-sequential.ans
60.06
GGURGO
NXZUEOA
BOHPBXMYSTFJUPUA
IOYBAEDMKSKO
- result:
60.06
IOYBAEDMKSKO
GGURGO
NXZUEOA
BOHPBXMYSTFJUPUA
- diff:
2d1
< IOYBAEDMKSKO
5a5
> IOYBAEDMKSKO

...

- ncpc2017-testdata/bestrelayteam/secret/30-sequential-secondbest-firstpart.ans
51.99
SECONDBEST
BEST
JMBCIRVTIHVRKRZZTXSD
RJZMGLUWHOJBLQGIUWZD
- result:
51.99
SECONDBEST
BEST
JMBCIRVTIHVRKRZZTXSD
QQYBKUPSWYKJCUODUSMA
- diff:
5c5
< QQYBKUPSWYKJCUODUSMA
---
> RJZMGLUWHOJBLQGIUWZD

References:

comments powered by Disqus