2025-12-02 beginners | Clojure Slack Archive

beginners

2025-12-02T20:05:19.528769Z

I'm still experimenting with Clojure in competitive programming. I think I've found a case where Clojure (Babashka) doesn't meet the execution time limit (3000 ms). My solution exceeds the limit in 17 out of 18 tests. Here's the problem:

A string T is called a good bracket sequence if and only if it satisfies the following condition:
- T can be made into an empty string by repeating the following operation zero or more times:
  - Choose () contained in T as a (contiguous) substring and remove it.
For example, (), (()()), and the empty string are good bracket sequences, but )()( and ))) are not good bracket sequences.

There is a string S. Initially, S is an empty string.
Process Q queries in the order they are given. After each query, determine whether S is a good bracket sequence.
There are two types of queries:
1 c: A character c is given. c is either ( or ). Append c to the end of S.
2: Remove the last character of S. It is guaranteed that S is not an empty string at this time.

1 <= Q <= 800000

And my solution:

(import java.util.Scanner)

(let [scanner (Scanner. System/in)
      q (.nextLong scanner)]
  (loop [i 0
         n 0
         sum [0]
         cnt 0]
    (when (< i q)
      (let [op (.nextLong scanner)]
        (if (= op 1)
          (let [c (.next scanner)
                next-sum (+ (get sum n) (if (= c "(") 1 -1))
                sum (assoc sum (inc n) next-sum)]
            (if (not (zero? next-sum))
              (print "No\n")
              (print (if (pos? cnt) "No\n" "Yes\n")))
            (recur (inc i)
                   (inc n)
                   sum
                   (if (neg? next-sum) (inc cnt) cnt)))
          (do
            (print (if (and
                        (zero? (get sum (dec n)))
                        (zero? cnt))
                     "Yes\n"
                     "No\n"))
            (recur (inc i)
                   (dec n)
                   sum
                   (if (neg? (get sum n)) (dec cnt) cnt))))))))

Sample input:

8
1 (
2
1 (
1 )
2
1 (
1 )
1 )

Sample output:

No
Yes
No
Yes
No
No
No
Yes

Is there a way to speed up the code?

2025-12-03T19:00:37.561809Z

Finally, after several different solutions, the (read-line) solution passed the tests without breaking time limit

borkdude 2025-12-03T19:02:28.811389Z

borkdude 2025-12-02T20:07:03.047989Z

You can speed up the code by avoiding Java interop which is quite slow (compared to JVM Clojure) in bb

2025-12-02T20:09:56.234519Z

Got it. I'll try.

borkdude 2025-12-02T20:11:36.646559Z

Is there a way for me to run those tests locally?

borkdude 2025-12-02T20:12:21.306509Z

instead of (print "...\n") you can use (println "...")

👍 1

borkdude 2025-12-02T20:12:32.157909Z

not that this matters for performance

2025-12-02T20:17:43.361689Z

> Is there a way for me to run those tests locally? Unfortunately, there's only one case, which I described above. AtCoder doesn't disclose the other tests

borkdude 2025-12-02T20:22:57.924819Z

here is a hint without interop:

(def input "8
1 (
2
1 (
1 )
2
1 (
1 )
1 )")
#_(def input (slurp *in*))



(require '[clojure.string :as str])
(def lines (str/split-lines input))
(def q (parse-long (first lines)))
(def ops (mapv (fn [line]
                (let [[n c]
                      (str/split % #" ")]
                  [(parse-long n) c])) (rest lines)))

(reduce (fn [sum [op c]]
          (if (= 1 op)
            (let [next-sum (+ (get sum n) (if (= c "(") 1 -1))
                  sum (assoc sum (inc n) next-sum)]))
          )
        [0]
        ops)

borkdude 2025-12-02T20:23:10.024049Z

I didn't complete the whole program, but this should get you going hopefully

borkdude 2025-12-02T20:23:56.437059Z

I don't know why sum is a vector and why you use assoc on it, you might have to change this

Clojurians Log v2

beginners