[Gym] SMU ICPC Selection Contest 2026

#	User	Rating
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
5	Um_nik	141
6	Errichto	139
7	adamant	137
8	maroonrk	133
9	BledDest	132
10	qwexd	129

Hello Codeforces!

This weekend we held the SMU ICPC Selection Contest 2026, used to select Singapore Management University's team for the upcoming ICPC season.

The contest was designed as a five-hour individual contest with estimated difficulties ranging from CF900 to CF2500. The problems are partially ordered by difficulty: they are divided into broad difficulty groups, while problems within each group are unordered.

Update: The editorial has been uploaded to the Gym! Feedback is welcome. Sorry for the delay — I started full-time work recently.

Thanks as well to everyone who attempted the problems on the Gym post-contest and provided valuable feedback.

All problems in the set were authored by me. To the best of my knowledge, they are based on original ideas.

I would like to thank:

teekaytai for testing a superset of the final problemset, giving feedback that helped shape the final set, and creating the Gym
Floating_Duck for testing the first version of the problemset and telling me which problems he did not like
feeder1 for reviewing several of the hardest problems and helping to verify their intended solutions
tiongg for testing an alternative problem order and helping me realise that the original difficulty curve was too steep

I would also like to thank all the invited participants from Singapore's competitive programming community who joined us for the online selection contest:

Participants from other universities: swehoneycodes, Valenz, hiroc and Shoryu386
Participants from Singapore's NOI community: mcncheesee, FIips, Lypho, hexahydride, stag3 and abcd271828

Special thanks to mcncheesee for reaching out to the NOI participants on my behalf.

Thank you for spending your Saturday with us and contributing to the live scoreboard :)

Comments (12)

Write comment?

jonteo_2001

3 months ago, hide # |

Auto comment: topic has been updated by jonteo_2001 (previous revision, new revision, compare).

→ Reply

hexahydride

orz

mcncheesee

orz jonteo_2001 for setting all the problems!

Valenz

As a participant, the problems buffed my Maimai skill and made me S QZKago Requiem master difficulty.

stag3

swehoneycodes

+19

Hey Jonathan, thanks for inviting me over as a guest participant! The problems were fun and interesting!

I have an observation for Problem H that I would like to point out. I think we can solve the problem in $$$5$$$ queries instead, rather than using the full $$$7$$$ queries allowed by the problem.

Let $$$N\le 10^8$$$. We can prime factorise $$$N$$$ as

$$$ N=\prod_i p_i^{e_i}, $$$

and the number of positive divisors of $$$N$$$ is

$$$ \tau(N)=\prod_i(e_i+1). $$$

If $$$\tau(N) \gt 8$$$, then every non-sacred number $$$N$$$ must be divisible by at least one of the following forms:

$$$ p^8,\qquad p^4q,\qquad p^2q^2,\qquad p^2qr,\qquad pqrs, $$$

where $$$p,q,r,s$$$ are distinct primes.

This is fairly easy to prove by considering the number of distinct prime factors and the smallest possible exponents that make the divisor count exceed $$$8$$$.

Let $$$M$$$ be the number remaining after our division using the gcd queries.

We want to choose the divisors such that none of these five forms can remain in $$$M$$$. For each prime $$$p$$$, let $$$a_p$$$ be the number of copies of $$$p$$$ that we try to remove from the initial number $$$N$$$.

We construct a number

$$$ D=\prod_p p^{a_p}, $$$

and divide $$$N$$$ by $$$\gcd(N,D)$$$.

If $$$p^e\mid M$$$, then after removing at most $$$a_p$$$ copies of $$$p$$$, at least $$$e$$$ copies are still left. Therefore, the original number $$$N$$$ must have contained at least $$$a_p+e$$$ copies of $$$p$$$. Hence,

$$$ p^e\mid M \quad\Longrightarrow\quad p^{a_p+e}\mid N. $$$

We choose $$$a_p$$$ such that

$$$ p^{a_p+1} \gt 10^2,\qquad p^{a_p+2} \gt 10^4,\qquad p^{a_p+4} \gt 10^6,\qquad p^{a_p+8} \gt 10^8. $$$

These conditions eliminate all five possible non-sacred forms.

If $$$p^8\mid M$$$, then

$$$ N\ge p^{a_p+8} \gt 10^8. $$$

If $$$p^4q\mid M$$$, then

$$$ N\ge p^{a_p+4}q^{a_q+1} \gt 10^6\cdot10^2 =10^8. $$$

If $$$p^2q^2\mid M$$$, then

$$$ N\ge p^{a_p+2}q^{a_q+2} \gt 10^4\cdot10^4 =10^8. $$$

If $$$p^2qr\mid M$$$, then

$$$ N\ge p^{a_p+2}q^{a_q+1}r^{a_r+1} \gt 10^4\cdot10^2\cdot10^2 =10^8. $$$

If $$$pqrs\mid M$$$, then

$$$ N\ge p^{a_p+1}q^{a_q+1}r^{a_r+1}s^{a_s+1} \gt (10^2)^4 =10^8. $$$

Every case contradicts $$$N\le10^8$$$. Therefore, none of the five non-sacred forms can remain in $$$M$$$.

The smallest suitable values of $$$a_p$$$ are

$$$ a_p= \begin{cases} 19, & p=2,\\ 9, & p=3,\\ 5, & p=5,\\ 4, & p=7,\\ 2, & p\in\{11,13,17,19\},\\ 1, & 23\le p\le97,\\ 0, & p\ge101. \end{cases} $$$

Now let us perhaps define

$$$ D=\prod_p p^{a_p}. $$$

The value of $$$D$$$ is larger than $$$10^{18}$$$, so we cannot use it in one gcd query. However, we can split its prime factors into four pairwise coprime query values, each at most $$$10^{18}$$$.

For gcd query $$$1$$$, use

$$$ d_1=2^{19}\cdot11^2\cdot43\cdot61\cdot79 =13145607766016. $$$

For gcd query $$$2$$$, use

$$$ d_2=3^9\cdot13^2\cdot31\cdot47\cdot67\cdot83 =26951965616979. $$$

For gcd query $$$3$$$, use

$$$ d_3=5^5\cdot17^2\cdot29\cdot37\cdot59\cdot73\cdot89 =371460351034375. $$$

For gcd query $$$4$$$, use

$$$ d_4=7^4\cdot19^2\cdot23\cdot41\cdot53\cdot71\cdot97 =298343793306853. $$$

Let the returned values be

$$$ g_i=\gcd(N,d_i). $$$

Since the four $$$d_i$$$ are pairwise coprime and $$$D=d_1d_2d_3d_4$$$, we have

$$$ g_1g_2g_3g_4 =\gcd(N,d_1d_2d_3d_4) =\gcd(N,D). $$$

Let

$$$ G=g_1g_2g_3g_4. $$$

Since $$$G=\gcd(N,D)$$$, we know that $$$G\mid N$$$. Therefore, the fifth query, div G, is guaranteed to succeed.

After this division, the remaining number is

$$$ M=\frac{N}{\gcd(N,D)}. $$$

From the argument above, $$$M$$$ cannot contain any of the five non-sacred forms. Therefore,

$$$ \tau(M)\le8, $$$

so $$$M$$$ is sacred.

Hence, I think the problem can always be solved using

$$$ 4\text{ gcd queries}+1\text{ division query}=5\text{ queries}. $$$

3 months ago, hide # ^ |

Wow! This is really cool, thank you for sharing this!!

jeroenodb

← Rev. 2 →

The sample outputs of problem I in the statement and the "answer" tab when looking at test $$$1$$$ when submitted are different. Which one is the correct one?

Specifically, the answer: $$$0.946667668049$$$ seems too high. (because point $$$(0,0)$$$ is closer than that)

I looked at the accepted judge submissions, and I believe just the wrong submission was chosen as the "main correct one".

Btw, comparing calc(mid,p) with calc(mid+1,p) can lead to precision errors, because the positions of the segments for mid and mid+1 are so close together (can be less than $$$10^{-12}$$$ difference), and if the segment distance functions happens to round the wrong way, then the binary search goes the wrong way (the segment distance is written well, but that doesn't exclude some error). Not sure on the impact on the testcases currently, but it is something to think about.

I feel like my submissions should get an answer always $$$\geq$$$ to the actual answer, because I am leaving out some points, but I get a smaller answer than the judge solution, which does not depend on if I use doubles or long doubles).

Hi! Thank you for pointing this out. I checked the Polygon invocation logs and found that your submission fails on query 64 of test 5, which is the point:

1 101746 1 2824

The correct distance is approximately 0.000243465604, while your submission outputs about 0.0002445804, which exceeds the threshold.

That said, you raised a valid concern about the numerical stability of the official solution. Before the contest, I noticed that this model solution produced slightly different answers but appeared to be more forgiving in our tests, while the more precise solutions still passed against it. I had not identified the cause of the discrepancy at that time, and used it to reduce the likelihood of contestants receiving WA from minor floating-point differences. In hindsight, the jury answers should have been made as accurate as possible. My mistake.

I have now improved the implementation and teekaytai has updated the Gym's jury answers.

Sorry for the confusion, and thank you again for highlighting this.

6 weeks ago, hide # |

jonteo_2001's blog