codelegend's blog

By codelegend, 3 years ago, In English

I am attempting to solve 1520F1 - Guess the K-th Zero (Easy version) in Haskell.

import Control.Arrow ((>>>))

main = interact $
         lines >>> (\(nt:ls) -> head (words nt) : ls) >>> map read >>> solve >>> map show >>> unlines

data Query = Ask Int Int | Answer Int

instance Show Query where
  show (Ask l r) = "? " ++ show l ++ " " ++ show r
  show (Answer x) = "! " ++ show x

solve :: [Int] -> [Query]
solve (n:k:rs) = go 1 n rs
  where
    go lo hi xs
      | lo == hi = [Answer lo]
      | otherwise =
        let mid = (lo + hi) `div` 2
         in Ask 1 mid :
            (let (lo', hi') = (if head xs + k > mid then (mid + 1, hi) else (lo, mid))
              in go lo' hi' (tail xs))

I believe I have ensured maximum laziness while checking the query responses — I only force xs in the tail of the returned query list.
The code runs fine locally. But I keep getting Idleness limit exceeded on the sample case: 117826356

Am I missing some important detail here? Or perhaps it has something to do with the exact compilation options CF uses? (I am just using ghc -O2)

Edit: Resolved, had to disable stdout buffering, with hSetBuffering stdout NoBuffering.

  • Vote: I like it
  • +46
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What flushes the output here?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    IIUC the interact function is fully lazy, it forces and prints one character at a time. And this force usually forces the computation to happen.

    So here, tracing back, it forces unlines which forces map show which forces solve. And solve consumes input, but only from the second query onwards. And I think all the functions I used are fully lazy.

    (I might be wrong about my assumptions of which functions are lazy though.)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ah okay, turns out I also need to disable buffering for stdout, by hSetBuffering stdout NoBuffering. It works now! submission — 117843764.

    I guess without this, the flushing is environment dependent? Not sure.