How was ZIO?

How did ZIO go for you guys? I felt like it was easier than last year, I attempted 65 marks, but I don’t know about silly mistakes :weary: :pensive:

“ZIO 2023, more like ZMO 2023” - Me during the test

I am getting following answers (I smuggled out answers on my hall ticket :smirk:)

  1. (a) 30
    (b) 136
    (c) 441

  2. (a) 53
    (b) 33750
    (c) 5751022 (probably wrong oops)

  3. (a) 3
    (b) 112
    (c) 344960

  4. (a) 181
    (b) BLANK
    (c) BLANK

I’m getting same answers as the user above except I didn’t attempt 2(c) and I’m getting 70 as the answer for 3(b).

How did you get 70 for 3(b)?

How did u get the answers for 2c and 3c?

I remember getting 2*(7C4) at the end

For 2c, I just did bruteforce along with casework, and for 3c, basically do this algorithm:

  • For a range [l \cdots r], find the minimum index. Say it is m.
  • Then, split at m into [l \cdots m - 1] and [m + 1 \cdots r].
  • Then, since we can get no new information by including m in any of our queries, we will now calculate the number of ways of assigning all the numbers in [l \cdots r] (except m of course, since that is fixed) to the right half. That is \dbinom{r - l}{r - m}.
  • Then multiply that by the number of solutions you get for [l \cdots m - 1] and again, multiply that by the number of solutions you get for [m + 1 \cdots r].
  • Base case is: For r - l = 1, there will always be exactly one solution. (Of course, you can break early even if r - l = 2, and there is some special case, but I’m talking about a formal definition of the recursive function)
  • Thus, we are done by calling the number of solutions of [1 \cdots n].

It’s actually 2 \cdot \dbinom{8}{3}. (according to me, maybe it is wrong.)

Was the value of N 8 or 9 if you’d remember?

Can someone explain the logic for the 1st question? I’m getting the B part correct but my answer for A is 36 and my answer for B is 496

You are not subtracting the common parts…Think about it, maybe do some writing.

Howsopro sir. And why did you leave UFDS?? :wew:

what was the test case for 2(a)?

What is the algorithm for problem 4, parts (b) and (c) specifically?

There is an algorithm based on maintaining components in small-to-large fashion, along with offset values which can solve those subtasks in reasonable time.