Nickolas's blog

By Nickolas, 3 months ago, translation, In English,

This turned out to be the hardest April Fools Day Contest to date — the winner solved only 5 problems out of 7!

1145A - Thanos Sort

The easiest problem of the contest, with a statement and without any caveats — I just likes the idea of sorting the array by destroying elements you dislike :-)

Read more »

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

By Nickolas, 4 months ago, translation, In English,

The contest is over; I hope at least some of you enjoyed it :-) The editorial is published here.


The 7th April Fools Day Contest will take place on Monday April 1st. This is a joke competition in which solving the problem is often easier than figuring out what the actual task is.

In this round you'll be given several weird problems and 2 hours to solve them. The contest will use ACM ICPC rules (no hacks, the standings are decided by the number of solved problems and penalty time earned on them), and it will be unrated. You can submit solutions in any language allowed by Codeforces. To get an idea of what the contest will look like, you can check out the contests of the past years: 2012, 2013, 2014, 2016, 2017, 2018.

As usual, to enjoy competing in this round you'll need a sense of humor compatible with mine. Good luck, and have fun!

Read more »

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

By Nickolas, 4 months ago, In English,

Here is the editorial for the round: https://assets.codeforces.com/rounds/1116/contest-editorial.pdf. The comments for this post also have lots of great explanations of alternative solutions, make sure to check them out!

I hope you've enjoyed the contest!

Read more »

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

By Nickolas, 5 months ago, In English,

Microsoft's Quantum Team and Codeforces are excited to invite you to Microsoft Q# Coding Contest — Winter 2019!

The contest will run from March 1 to March 4 and will offer increasingly challenging tasks on superposition, measurement, quantum oracles and unitary transformations.

As a reminder, last weekend we held a warmup round with easier tasks on quantum oracles and unitary transformations; the tasks are available for practice here, and the solutions are explained here. You can brush up on the topics of superposition and measurement in the first Q# contest and its warmup round.

Several useful reminders:

  • The contest is unrated :-)
  • Solutions are accepted only in Q#.
  • Participants are ranked according to the number of correctly solved tasks, with the last correct submission time as a tiebreaker.
  • The tasks are grouped by topic, and the tasks within one topic are ordered in approximate order of increasing difficulty. If you find a problem too hard, don't forget to check the next problems in this topic and problems from different topics, they might turn out to be easier.
  • Submission verdicts work as follows:
    Wrong Answer means that the solution fails any problem-specific checks (such as leaving the qubits in a state other than expected, using measurements in a task which prohibits them or returning incorrect classical value in measurement tasks) or prints anything to the standard output (using Message or DumpMachine functions);
    Runtime Error means that the solution throws a more general exception (for example, caused by releasing allocated qubits in non-zero state or trying to access array elements outside of array bounds);
    Memory Limit Exceeded means that the solution together with the checker allocated more qubits than it is allowed (the limit is ~15 qubits for problems related to quantum oracles with memory limit 1024MB, and ~25 qubits for other types of problems);
    Time Limit Exceeded works the same way as in classical competitions (your program is too slow), but I have to mention it for the sake of completeness :-)
  • 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.
  • And finally, the really important stuff: the top 50 ranked participants will receive a Microsoft Quantum T-shirt! Here is a preview:

Read more »

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

By Nickolas, 5 months ago, In English,

Microsoft’s Quantum team is excited to announce the Q# Coding Contest – Winter 2019! In this contest you can put your quantum programming skills to the test, solving quantum computing tasks in Q#. Winners will receive a Microsoft Quantum T-shirt!

Quantum computing is a radically different computing paradigm compared to classical computing. Indeed, it is so different that some tasks that are believed to be classically intractable (such as factoring integers or simulating physical systems) can be performed efficiently on a quantum computer. In 2017 Microsoft introduced the Quantum Development Kit which includes the Q# programming language. Q# can be used with Visual Studio, Visual Studio Code or the command line, on Windows, macOS, and Linux.

In summer of 2018 we hosted the first quantum programming contest, which included problems on introductory topics in quantum computing: superposition, measurement, quantum oracles and simple algorithms. This contest will offer harder problems on some of these topics as well as introduce some new topics.

The contest will run from March 1 to March 4.

Read more »

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

By Nickolas, 6 months ago, In English,

Marathon Match 106 StainedGlass started on January 4th and will run for 10 days, including two weekends. You can find it in the list of active contests. I am the writer :-)

Read more »

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

By Nickolas, 9 months ago, In English,

Marathon Match 103 ProductInventory started on October 19th and will run for 9 days, including two weekends. You can find it in the list of active contests.

Read more »

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

By Nickolas, 10 months ago, In English,

Marathon Match 102 TrucksAndCouriers started on September 13th and will run for a week. You can find it in the list of active contests.

Read more »

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

By Nickolas, 12 months ago, translation, In English,

The last round of TCO18, Marathon Round 4 CakeSharing started on August 1st and will run for a week. You can find it in the list of active contests.

I am the writer :-)

Upd. Due to the technical issues the round is extended by 24 hours, till August 9th.

Read more »

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

By Nickolas, 12 months ago, translation, In English,

TCO18 Argentina Lightning Marathon Round KnightsAndPawns started on July 27th and will run for three days. You can find it in the list of active contests. I am the writer :-)

This round is part of regional event at Buenos Aires, Argentina, so it has not only TCO points for Marathon track but also prizes for top 3 online participants and top 3 participants who will be present at the regional event.

Read more »

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

By Nickolas, 12 months ago, In English,

Microsoft's Quantum Team and Codeforces are excited to invite you to Microsoft Q# Coding Contest — Summer 2018!

The contest will run from July 6 — 9 and will consist of increasingly challenging tasks on introductory topics in quantum computing: superposition, measurement, oracles and simple algorithms. The top 50 ranked participants will receive a Microsoft Quantum T-shirt!

As a reminder, last weekend we help a warmup round with easier tasks which covered the same topics. The results were quite impressive: 167 participants solved all tasks! You can see the tasks here, and the solutions with explanations here.

Several useful reminders:

  • The contest is unrated.
  • Solutions are accepted in Q# only.
  • Participants are ranked according to the number of correctly solved tasks, with penalty time as a tiebreaker.
  • The tasks are grouped by topic, and the tasks within one topic are ordered in approximate order of increasing difficulty. If you find a problem too hard, don't forget to check the next problems in this topic and problems from different topics, they might turn out to be easier.
  • Unlike the warmup round, you're not allowed to discuss the tasks during the contest.
  • By popular demand, we have added Custom Invocation to allow you to run Q# code on Codeforces servers. Here is the signature of the code you should use to run it (note that the namespace and operation name have to match this code exactly):
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    // ------------- Operation which is called from C# -------------------
    operation RunQsharp () : Bool
    {
        body
        {
            Message("Hi");
            return true;
        }
    }
}
  • For tasks which require you to create a certain quantum state or to implement a unitary transformation, any kind of error gives verdict "Wrong Answer". For tasks which have classical return, I tried to differentiate verdicts "Wrong Answer" (your return value was incorrect) and "Runtime Error" (array index out of bounds, qubits released are not in zero state, oracle called too many times etc.).
  • NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 7/9/18. For details, see Official Rules.

You can find the discussion of the warmup round and pointers to Q#/quantum computing materials here.

For first time Codeforces users:

  1. Create user account here.
  2. Register for the contest here.
  3. Once the contest starts on July 6, access the problems here.

Good luck! We hope you enjoy the contest!

Update. The contest is over. Editorials are published.

Read more »

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

By Nickolas, 12 months ago, translation, In English,

TCO18 Marathon Round 3 InvestmentAdvice started on July 11th and will run for a week. You can find it in the list of active contests.

Read more »

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

By Nickolas, 13 months ago, In English,

(text courtesy of my colleague Chris Granade)

A quantum oracle O is a "black box" operation that is used as input to another algorithm. Often, such operations are defined using a classical function f: {0, 1}n → {0, 1}m which takes n-bit binary input and produces an m-bit binary output. To do so, consider a particular binary input x = (x0, x1, ..., xn - 1). We can label qubit states as .

We may first attempt to define O so that , but this has a couple problems. First, f may have a different size of input and output (n ≠ m), such that applying O would change the number of qubits in the register. Second, even if n = m, the function may not be invertible: if f(x) = f(y) for some x ≠ y, then but . This means we won't be able to construct the adjoint operation , and oracles have to have an adjoint defined for them.

We can deal with both of these problems by introducing a second register of m qubits to hold our answer. Then we will define the effect of the oracle on all computational basis states: for all and , \begin{align*} O(|x \rangle \otimes |y \rangle) = |x \rangle \otimes |y \oplus f(x) \rangle. \end{align*} Now by construction, thus we have resolved both of the earlier problems.

Importantly, defining an oracle this way for each computational basis state also defines how O acts for any other state. This follows immediately from the fact that O, like all quantum operations, is linear in the state that it acts on. Consider the Hadamard operation, for instance, which is defined by and . If we wish to know how H acts on , we can use that H is linear:

\begin{align*} H |+ \rangle = \frac{1}{\sqrt{2}} H(|0 \rangle + |1 \rangle) = \frac{1}{\sqrt{2}} (H |0 \rangle + H |1 \rangle) = \frac{1}{\sqrt{2}} (|+ \rangle + |- \rangle) = |0 \rangle \end{align*}

In the case of defining our oracle O, we can similarly use that any state on n + m qubits can be written as

Thus, the effect of the oracle O on this state is

Read more »

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

By Nickolas, 13 months ago, In English,

Microsoft's Quantum Team has good news for quantum enthusiasts and coders looking for new challenges. We are excited to announce Microsoft Q# Coding Contest — Summer 2018! By entering the contest, you can hone your quantum coding skills by tackling problems of varying difficulty and implementing solutions in the quantum programming language Q#. Winners will receive a Microsoft Quantum T-shirt!

Quantum computing is a radically different computing paradigm compared to classical computing. Indeed, it is so different that some tasks that are believed to be classically intractable (such as factoring integers, computing discrete logarithms on elliptic curves, or simulating physical systems) can be performed efficiently on a quantum computer. Microsoft recently introduced the Quantum Development Kit which includes Q# — a new programming language to express quantum programs in a way that makes it easier for classical coders to enter the space. Q# integrates into Visual Studio or Visual Studio Code development environments, and is available as a command line tool. Visual Studio Code allows development under Windows, macOS, and Linux.

The contest will run from July 6 — 9 and will consist of increasingly challenging tasks on introductory topics in quantum computing: superposition, measurement, oracles and simple algorithms.

The rules of the contest are:

  • The contest will have 12 15 tasks of various complexity levels.
  • To solve each task, you will write Q# code to implement the described transformation on the given set of qubits or to analyze the state of a set of qubits. Solutions are accepted in Q# only.
  • The solution is correct if it passes all tests from a predefined test set. You will know whether the solution is correct soon after submitting it.
  • Participants are ranked according to the number of correctly solved tasks.
  • Ties are resolved based on lowest total penalty time for all tasks, which is computed as follows. For each solved task, a penalty is set to the submission time of that task (the time since the start of the contest). An extra penalty of 20 minutes is added for each failed submission on solved tasks (i.e., if you never solve the task, you will not be penalized for trying that task).
  • The top 50 ranked participants will receive a Microsoft Quantum T-shirt.
  • NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 7/9/18. For details, see Official Rules.

From June 29 to July 2, we will offer a warmup round with simpler tasks on the topics covered in the main contest. Participation in the warmup round is entirely optional. The warmup round gives you an opportunity to get familiar with the contest environment and submission system beforehand, as well as refresh or learn the basics of quantum computing and Q# programming language. During the warmup round everybody is encouraged to discuss the tasks and the solutions. 24 hours after the start of the warmup round we will publish explanations and solutions to the easiest three problems. Once the warmup round is over, we will publish the editorials on the contest page explaining both the quantum computing logic behind the solution and the Q# implementation.

To start, please refer to Q# installation instructions and language reference.

Quantum computing and Q# materials:

For first time Codeforces users:

  1. Create user account here.
  2. Register for the warmup round here.
  3. Register for the contest here.
  4. Once the warmup round starts on June 29, access the problems and see additional contest materials here.
  5. Once the contest starts on July 6, access the problems here.

Good luck! We hope you enjoy the contest!

Update. Explanations for problems A, D and G of the warmup round are published.

Update. The warmup round is over. Explanations for all problems are published.

Read more »

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

By Nickolas, 13 months ago, translation, In English,

Marathon Match 101 "Fifa World Cup Special" WorldCupLineup started on June 27th and will run for a week. You can find it in the list of active contests.

Read more »

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

By Nickolas, 14 months ago, translation, In English,

TCO18 Marathon Round 2 CrystalLighting started on June 6th and will run for a week. You can find it in the list of active contests. I am the writer :-)

Upd. TCO Marathon Leaderboard.

Upd.2. Due to the issues with the contest not showing up in some listings of active contests, the round is extended by 24 hours, till June 14th.

Read more »

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

By Nickolas, 14 months ago, translation, In English,

TCO18 Marathon Round 1 RoadsAndJunctions started on May 9th and will run for a week. You can find it in the list of active contests. I am the writer :-)

This year the online part of the Marathon competition consists of 4 main rounds, each running for a week. The winner of each main round advances to the finals, and so do 8 participants who accumulated the most points across all main and lightning rounds. 150 competitors who accumulate the most points get t-shirts; given that each round awards points to top 50 places, it's quite possible that the t-shirt condition will transform into "top 50 in each round get t-shirts".

Read more »

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

By Nickolas, 15 months ago, In English,

TCO18 Warsaw regional event will take place on May 12th. It will include an Algorithm competition round which will allow the top 10 scorers to advance to the Online Wildcard Round. You can read more about Algorithm rules here.

A lightning Marathon match MapRecoloring started on May 4th and will run for 3 days. It will be the first of TCO18 Marathon rounds, awarding TCO points for top 50 participants, as described here. It will also feature prizes for top 3 online participants and top 3 participants present at the regional event. I am the writer of the Marathon problem :-)

Read more »

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

By Nickolas, 15 months ago, translation, In English,

952A - Quirky Quantifiers

JAPE riddle generator is a program which can produce question-answer puns. This problem has been inspired by one of the witticisms produced by it:

What do you call a quirky quantifier? An odd number.

All you had to do was to check whether the given "quantifier" was "quirky".

952B - A Map of the Cat

This problem was inspired by the awesome book "Surely You're Joking, Mr. Feynman!" In one of his stories Feynman asks a librarian to fetch him a map of a cat, having a zoological chart in mind. Of course, such a serious interpretation was unsuitable for my purposes :-)

This was a perfectly straightforward problem: just pet the cat!

Read more »

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

By Nickolas, 16 months ago, translation, In English,

The contest is over; I hope you've enjoyed it :-) Editorial is here.


The 6th April Fools Day Contest will take place on Sunday April 1st. This is a joke competition in which solving the problem is often easier than figuring out what the actual task is.

This year I tried to make the problems less puzzling and more versatile. For example, almost all problems have a statement! And you won't need OEIS this time :-)

In this round you'll be given 7 weird problems and 2 hours to solve them. The contest will use ACM ICPC rules (no hacks, the standings are decided by the number of solved problems and penalty time earned on them), and it will be unrated. You can submit solutions in any language allowed by Codeforces. To get an idea of what the contest will look like, you can check out the contests of the past years: 2012, 2013, 2014, 2016, 2017.

As usual, to enjoy competing in this round you'll need a sense of humor compatible with mine! Good luck, and have fun!

Read more »

Announcement of April Fools Contest 2018
Announcement of April Fools Contest 2018
 
 
 
 
  • Vote: I like it
  • +490
  • Vote: I do not like it

By Nickolas, 16 months ago, translation, In English,

Marathon Match 100 SameColorPairs started on April 18th and will run for a week. You can find it in the list of active contests. I am the writer :-)

Upd: Topcoder has announced prizes for MM 100 participants:

  • Top 50 will get exclusive Marathon Match 100 t-shirt.
  • The "veterans" — members who registered at Topcoder in 2012 or earlier and have participated in at least one match since then — who place in top 50 will get limited-edition "vintage" t-shirts. Here "vintage" means a special design, not previously worn :-)
  • First three places with get $250, $150 and $75, respectively.
  • Top scoring "newbie" — a member who registered between January 1st and April 10th and have never participated in a Marathon before — will get $150.

Read more »

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

By Nickolas, 16 months ago, translation, In English,

Marathon Match 99 BrokenSlotMachines started on March 14th and will run for a week. The problem was written by timmac.

Read more »

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

By Nickolas, 17 months ago, translation, In English,

Marathon Match 98 PrincessesAndMonsters started on February 14th and will run for a week.

Ten participants (top 5 and 5 random) will get t-shirts! I am the writer :-)

Read more »

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

By Nickolas, 18 months ago, translation, In English,

Marathon Match 97 PointsOnTheCircle started on January 24th and will run for a week. I am the writer :-)

Read more »

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

By Nickolas, 19 months ago, translation, In English,

909A - Generate Login

The most straightforward solution is to generate all possible logins (by trying all non-empty prefixes of first and last names and combining them) and find the alphabetically earliest of them.

To get a faster solution, several observations are required. First, in the alphabetically earliest login the prefix of the last name is always one letter long; whatever login is generated using two or more letter of the last name, can be shortened further by removing extra letter to get an alphabetically earlier login.

Second, the prefix of the first name should not contain any letter greater than or equal to the first letter of the last name, other than the first letter.

Thus, a better solution is: iterate over letter of the first name, starting with the second one.

Read more »

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