C was a pretty cool problem. Never seen anything like it, requires some thinking, yet not too difficult. Props!

Why not just pick n=2000 for D, so it can be solved in Python? Now I had to go back and rewrite my solution in C++ for no particular reason, just because the Python implementation barely times out. I actually thought it was a very nice problem other than that annoying detail.

Additionally, they should get posted to Kattis, although it may take a while.

Thank you so much! It's very satisfying to get an answer to this, it's very unlikely I would have figured it out myself. Indeed I just have to change a single byte to get AC.

Do you happen to know some good CF exercises to practice this?

I have now implemented this solution, in submission 87661047. It gives WA, but I cannot think of a counterexample (or my code may have a bug). I cannot get the killing test case out because the test case file gets truncated. Anyone have an idea?

I had the following solution to Div1D. Unfortunately I did not manage to implement it correctly in time, but I am still curious if this is the correct approach.

Does this work? If not, what is a counterexample?

From the examples, it seems that within { A } apply { B } means: first apply A, then apply B, then apply the inverse (adjoint) of A.

Oh, damn. I proved this too, but it was a lot of tedious calculation. I didn't think to compare columns. Obvious in retrospect.

In this particular case, you can replace R1 by Z itself. :-)

That's it? I can't believe I didn't get that. :') I spent pretty long on that question, too.

It put a real damper on the contest for me as well. It made me perversely happy to see the top 50 fill up with people with 17-18 solutions, because it meant I could just give up on the ML questions without feeling like I'd given up early. Fingers crossed that next year won't contain problems like that.

Oh! My problem was simply that I hadn't heard of custom invocation before. That's great actually -- I'll try out this workflow tomorrow before the contest, see if that works better for me. Thanks.

Custom Invocation allows you to run Q# code on Codeforces servers; make sure your code has namespace Solution and an operation with a signature operation RunQsharp () : Bool defined in it.

So does this replace the Solve from the practice problems and previous years? And what is the boolean you have to return? Or am I confusing things?

I had the same issue here, maybe that helps?

Thanks!

How do I find out what hyperparameters are available to me, and what they mean (i.e. what their definition is)? It is not meaningfully specified here or here.

In my current solutions file, these are the first three cells:

// A1
open Microsoft.Quantum.Intrinsic;

operation SolveA1 (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using(q = Qubit()) {
        unitary(q);
        mutable result = 1;
        if(M(q) == Zero) {
            set result = 0;
        }
        Reset(q);
        return result;
    }
}

open Microsoft.Quantum.Diagnostics;
open Microsoft.Quantum.Measurement;

operation SolveTestA1 () : Unit {
    let i = SolveA1(I);
    Message($$$"I={i}"); let x = SolveA1(X); Message($$$"X={x}");
}

%simulate SolveTestA1

Running all three of these cells takes about 3 seconds.

To hand in the code, I copy the content of the first cell into a text file, add the correct namespace, and change the name from SolveA1 to Solve.

I write my code in a jupyter notebook, with testing code next to it. Once I want to submit I copy the code to a new text file and submit that. This workflow is terrible and I wouldn't recommend it to anyone. :^)

Sure, but if I were programming in PyTorch and my parameters weren't updating I would know how to get the gradient I am using for the update and print some statistics (max, min, mean, variance) to see if the hyperparameters are the problem or there is just a bug in my code (or something wrong with my installation of the backend). Q# is still a little arcane to me.

Ah, thank you. That seems to have worked. That gives me some confidence in the contest next weekend.

This post contains spoilers for D1.

    function ClassifierStructure() : ControlledRotation[] {
        return [
            ControlledRotation((0, new Int[0]), PauliY, 0)
        ];
    }

    parameter_starting_points = [
        [3.1415]
     ]

Qubit => Unit means a function that takes a Qubit as argument and returns Unit (essentially a void function, if you're used to C/C++/Java). The signature suggests that it operates on qubits, and the "output" is given by the state in which it leaves the qubit. The Adj + Ctl means that the operation has an adjoint and a controlled version available, which is true of (for instance) X. So indeed Solve(X); is a correct line of code if Solve has the signature you describe.

Interesting. I hadn't considered recursion in Q#. I'll take a look at your submission to the problem when the contest ends.

Ah, thanks, this is good to know. I often run into more problems with the non-quantum part of Q# than the actual QC knowledge.

Ah, right, I failed to mention this in my post but that's another approach I had considered. Since simulating N additional qubits incurs a factor 2^N (ish) overhead to fully simulate (or does it?) I was worried that it would likely cause my code to timeout.

This post may contain some spoilers for B1 and/or B2.

I had the same question as Svlad_Cjelli. Thank you for the answer!

Is there an easily searchable repository of Q# examples yet? If I'd seen any piece of code actually using LittleEndian I think this would have been obvious, but I don't know where to look. I don't think the documentation helps.

Non-trivial quantum computing, the type where you use entanglement non-trivially, starts in 8 (real) dimensions though. A couple fewer if you only look at unit vectors and normalize the global phase in some way, but still strictly more than 3.

A Python Queue is quite slow; the correct object to use as a fast queue data structure is the deque object from collections. It is actually a double-ended queue (so you can append and pop from either side) but of course you can use this as a queue. If you use this data structure (here is your code with a deque: 83210553) it becomes fast enough.

In this particular problem, the queue never gets very long. At worst there are about 50 elements in it. As a result, the slow list operation pop(0) becomes quite fast in practice -- faster than a Queue.

This round, I did everything in Python 3 except E. Last round, Python 3 was too slow for A which really messed me up (I could have just translated it to C++, but I was too stubborn).

If you don't know C++ yet, it never hurts to learn. But use the right tool for the right job: if time limits aren't tight, a package like itertools can save you a lot of programming time.

I don't think that's true. In your example, the innermost "else" triggers on each *, at which point curr has value 1, so x is added to the total and curr is reset to 0.

Might be the width of a double that differs between the compilers? Just a guess, though.

I'm guessing the problem is that you're using an f-string: those are from the most recent versions of Python, and are not supported by older versions. Try a different way to format your output string, and it should get rid of the RTE verdict.

Edit: My bad, this is not the issue, see comments below. (I had this problem myself with GCJ and assumed too quickly that it was probably the same issue.)

A really cool problem set. Looking forward to more. Lightly upset about the contest being unrated -- I solved Div 1 ABC, think I probably would have solved D if I'd continued, and I'm only rated 19-something, so that would've been a big boost -- but it's just numbers.

Try the mirrors, they work for me more consistently.

Can we submit solutions in 1C even if we've already made the top 1500 in another round? I wanted to participate for fun.