Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×
Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

wilcot's blog

By wilcot, 4 months ago, translation, In English

Just recently I had a need to solve the following problem:

Given $$$a$$$ and $$$m$$$, find all $$$x$$$ such that: $$$x^2 \equiv a \pmod{m}$$$.

After some time searching the Internet and carefully analyzing each case, I got a solution that works for any $$$a$$$ and $$$m > 0$$$ in $$$O(\sqrt{m})$$$ time, or in $$$O(\log^2(m))$$$ time if $$$a$$$ and $$$m$$$ are coprime.

Below are the cases I considered and links to articles (or discussions) for algorithms:

  1. $$$x^2 \equiv a \pmod{p}$$$, $$$a \ne 0$$$, $$$p$$$ — odd prime (link).
  2. $$$x^2 \equiv a \pmod{p^k}$$$, $$$a \ne 0$$$, $$$k > 0$$$, $$$\gcd(a, p) = 1$$$, $$$p$$$ — odd prime (link).
  3. $$$x^2 \equiv a \pmod{2^k}$$$, $$$a \ne 0$$$, $$$k > 0$$$, $$$\gcd(a, 2) = 1$$$ (link).
  4. $$$x^2 \equiv 0 \pmod{p^k}$$$, $$$k > 0$$$, $$$p$$$ — prime. Note that in this case $$$x^2$$$ must be divisible by $$$p^k$$$. Then $$$x$$$ must be divisible by $$$p^{\lceil\frac{k}{2}\rceil}$$$. From this we obtain that $$$x = i \cdot p^{\lceil\frac{k}{2}\rceil}$$$, $$$0 \le i < p^{\lfloor\frac{k}{2}\rfloor}$$$ .
  5. $$$x^2 \equiv p^s \pmod{p^k}$$$, $$$k > 0$$$, $$$0 < s < k$$$, $$$p$$$ — prime. Solutions exist only for $$$s = 2 \cdot t$$$. Proved by contradiction. Then it is obvious that $$$p^t$$$ is one of the solutions ($$$(p^t)^2 = p^s$$$). Let's find the remaining solutions. Let $$$x = p^t + y$$$, then $$$x^2 = p^s + 2 \cdot p^t \cdot y + y^2$$$. Note that $$$2 \cdot p^t \cdot y + y^2$$$ must be divisible by $$$p^k$$$. In this case, $$$x = p^t + i \cdot p^{\max(\lceil\frac{k}{2}\rceil, k - t - (p = 2))}$$$.
  6. $$$x^2 \equiv q \cdot p^s \pmod{p^k}$$$, $$$k > 0$$$, $$$0 < s < k$$$, $$$\gcd(q, p) = 1$$$, $$$p$$$ — prime. Let $$$x_1$$$ be the solution for $$$x^2 \equiv q \pmod{p^k}$$$, and let $$$x_2$$$ be the solution for $$$x^2 \equiv p^s \pmod{p^k}$$$. Then $$$x = x_1 \cdot x_2$$$ will be a solution to the original problem.

The last three cases had to be deduced independently, so there are no links. I was too lazy to document the proofs in this post, although in general they are not very complicated.

The general solution is found by using the Chinese Remainder Theorem and reducing to one of the above cases.

I will also give a complete implementation in Python (a function that solves the general case — discrete_sqrt):

Implementation

Full text and comments »

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

By wilcot, history, 14 months ago, In English

The XI BSUIR Open Programming Championship will be held from March 15 till April 29, 2023 (Minsk, Belarus).

Undergraduates and postgraduates of BSUIR, scholars, students from other universities and countries are invited to participate in the Championship.

The competition will take place in several rounds:

  • Quarterfinals (distance, problems in Russian and English) — March 15 — March 20 (both included);
  • Semifinals (distance/onsite semi-final, russian and english problems) — April 6;
  • Students Final — April 22 (Belarusian State University of Informatics and Radioelectronics, Minsk);
  • Schools Final — April 29 (Belarusian State University of Informatics and Radioelectronics, Minsk).

Quarterfinals are required only for BSUIR and school teams but other registered teams can also take part in it. Semifinals are required for all teams. BSUIR and school teams from Belarus take part onsite, other teams — online. Semifinals and Finals will be in ICPC format (5h contest).

To participate in the Championship teams need to be registered prior to April 3, 2023. Participation is free of charge — have fun.

The finalists are 30 (or more by jury decision) students teams, showed the best results in the qualifying rounds, but no more than:

  • 7 teams of undergraduates and postgraduates of BSUIR;
  • 2 teams from each of the universities of Belarus and abroad.

And 25 school teams showed the best results in the qualifying rounds.

University teams, which include at least two ICPC finalists 2022-2023, as well as high school teams, which include at least two winners of the final stage of the National Belarusian Olympiad in Informatics 2023, are allowed to participate in the finals of the Championship without passing the qualifying rounds.

Open BSUIR Programming Championship is held by the ICPC rules. During the Championship, the teams will be given 5 hours to solve 8 to 12 programming problems.

More information about the championship, as well as the problems and results of previous years, you may find at acm.bsuir.by.

here's a link there to a telegram channel and discussion, where you can talk to other participants and team up.

A little bit of last year video:
https://www.youtube.com/watch?v=nFZpkUFAO6Q
https://www.youtube.com/watch?v=07E0APqaB20

Full text and comments »

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

By wilcot, history, 7 years ago, In English

Very interesting contest.

But, how to solve task L, G and J?

Thanks in advance.

Full text and comments »

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

By wilcot, history, 7 years ago, In English

Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

Full text and comments »

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

By wilcot, history, 8 years ago, translation, In English

Hello, Codeforces!

My name is Ivan Udovin, and I would like to say, that the Codeforces Round #344 will be held on Thursday (March 3, 2016 at 19:35). This is our first round, but it doesn’t mean that problems will be boring and not interesting. The problemsetters of this round are me (wilcot) and Ilya Kheifets (xfce8888). Thanks a lot to Alex Vistyazh (netman) and unknown person (he don’t want to be added in the announcement) for testing our round. Also I’d like to thank Fedor Korobeynikov (Mediocrity) for his awesome idea for task E.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into English, and, of course, Codeforces team and Mike Mirzayanov for unique Codeforces and Polygon platforms.

This round consists of five problems. Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others.

Scoring distribution: 500, 1000, 1500, 2000, 2500.

Good luck, have fun.

PS. Editorial is ready.

PPS. Congratulations to the winners:

Div. 2:

  1. lovelive

  2. Murtazo.Ali

  3. chychmek

  4. chrome

  5. Batman

Div. 1:

  1. Um_nik

  2. chffy

  3. natsugiri

  4. ershov.stanislav

  5. AndreiNet

Full text and comments »

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