steinum's blog

By steinum, 3 weeks ago, In English

Hello, Codeforces Community!

We are thrilled to invite you to participate in the Metropolitan University Inter University Programming Contest — Sylhet Division 2024 (Online Mirror) on Codeforces! The main contest will take place on Saturday, November 16, 2024 at 10:00UTC+6 for 4 hours 30 minutes and will be held on toph.co. The mirror contest will follow shortly after the main event, the tentative time is Nov/16/2024 08:00 (Moscow time).

This contest follows ICPC-style rules and is unrated. Individual participation is recommended for div2 contestants, but team participation is also allowed.

Acknowledgments:

We kindly ask participants who are already familiar with the problems to refrain from participating or discussing them before the contest ends.

Note: This contest is unrated.

We hope you enjoy the problem set, and best of luck to all participants!

UPD: Editorial has been published.

Full text and comments »

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

By steinum, 4 weeks ago, In English

Hello, Codeforces Community!

We are thrilled to invite you to participate in the Khulna Regional Inter University Programming Contest (KRIUPC) (Online Mirror) on Codeforces! The main contest will take place on Nov/10/2024 12:00 (Moscow time) for a duration of 4 hours, and will be held on toph.co. The mirror contest will follow shortly after the main event.

This contest follows ICPC-style rules and is unrated. Team participation is recommended, but individual participation is also allowed.

As the coordinator, I’ve had the privilege of working alongside an amazing team to bring this contest to life, and we’re excited to see your skills in action!

Acknowledgments:

We kindly ask participants who are already familiar with the problems to refrain from participating or discussing them before the contest ends.

Note: This contest is unrated.

We hope you enjoy the problem set, and best of luck to all participants!

UPD: Editorial has been published

Full text and comments »

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

By steinum, 20 months ago, In English

Hello, Codeforces!

The flagship contest of SUST is here everyone! There will be 12 problems and the problemset is based on Brain Craft Intra SUST Programming Contest 2023. We cordially invite you to participate in this contest. Also, we encourage you to participate as teams. Please make sure that you read ALL the problems!

The contest will be held on Apr/07/2023 11:05 (Moscow time) and will run for 5 hours.

The setters of this contest are: Alfeh, Kawchar85, Mac_prime, magic_kiri, nh_nayeem, Raiden, ShikariSohan, ShinnirKolaChori, susmoydhar7, Tahseen

Contest link: Contest Based on Brain Craft Intra SUST Programming Contest 2023

UPD: Congratulations to the winners of the round!

Top 5 of all participants:

PlaceParticipantProblem solved=
1satyam343101274
2lukameladze1, keta_tsimakuridze, Phantom_Performer101341
3Adam_GS102116
4Coder_Nayak, sloppy_coder, Krypto_Ray7588
5MinhazIbnMizan, BrehamPie, Arnob7652

Participants who sent the first correct solution to the problems:

TaskParticipantPenalty
AthisIsMorningstar01:07
Bshort-circuit00:05
Clukameladze1, keta_tsimakuridze, Phantom_Performer00:34
DMinhazIbnMizan, BrehamPie, Arnob01:42
Esatyam34301:12
FCoronaVirus21675300:04
GCoder_Nayak, sloppy_coder, Krypto_Ray00:06
Hmerlin_00:28
iCoronaVirus21675300:24
Jsatyam34300:54
KJanekKwadrat, _supernalu_02:25
L--

UPD2:

Solutions

104283A - Yet Another Short Statement
ideas: Kawchar85
prepared: steinum

Solution (steinum)

104283B - Johny English and Group Formation
ideas: Raiden
prepared: Raiden

Solution (Raiden)

104283C - Johnny English Strikes Again
ideas: Raiden
prepared: Raiden

Solution (Raiden)

104283D - Search For Beauty
ideas: Kawchar85
prepared: Kawchar85

Solution (Kawchar85)

104283E - Tree query with update
ideas: Alfeh
prepared: Alfeh

Solution (Alfeh)

104283F - Find GCD
ideas: Kawchar85
prepared: Kawchar85

Solution (Kawchar85)

104283G - Another Tree Query
ideas: Alfeh
prepared: Alfeh

Solution (Alfeh)

104283H - Sequential Nim
ideas: Kawchar85
prepared: Kawchar85

Solution (Raiden)

104283I - The Secret Key
ideas: Kawchar85
prepared: Kawchar85

Solution (steinum)

104283J - Magic Balls
ideas: Raiden
prepared: Raiden

Solution (nh_nayeem)

104283K - Special Lattice Path
ideas: magic_kiri
prepared: steinum

Solution (steinum)

104283L - Ultimate Game
ideas: ShinnirKolaChori
prepared: Raiden

Solution (steinum)

Full text and comments »

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

By steinum, 4 years ago, In English

I was trying to solve this problem : cf-497D

My solution idea : let $$$R_d(p) = p'$$$ where $$$p'$$$ is the new location of point $$$p$$$ if we rotate it $$$d$$$ degree counter-clockwise with respect to $$$(0,0)$$$. That mean $$$R_d(p) = pe^{id}$$$

Hence, for some point $$$a \in A$$$ and $$$b \in B$$$ we can write $$$R_d(a-p)+p = R_d(b-q)+q$$$.

$$$R_d(a-p)+p = R_d(b-q)+q$$$

$$$\Longrightarrow R_d(a)-R_d(p)+p = R_d(b)-R_d(q)+q$$$

$$$\Longrightarrow p-q - R_d(p) + R_d(q)= R_d(b)-R_d(a)$$$

$$$\Longrightarrow (p-q) \frac{R_d - 1}{R_d}= a-b$$$

Here , $$$(p-q) \frac{R_d - 1}{R_d}$$$ actually represent a circle($$$C$$$) centered $$$p-q$$$ and radius = $$$|p-q|$$$.

And $$$a-b$$$ = Minkowski sum of A and (-B) [if we consider all $$$a$$$ and all $$$b$$$ ].

Hence, the problem turns into, checking if circle $$$C$$$ intersects polygon A-B or not.

My first idea was to triangulate $$$A$$$ and $$$-B$$$ then calculate the Minkowski sum of each pair, then check if the polygon(sum) intersects with circle $$$C$$$ or not.

I've written this code. I used the triangulation method mentioned in Computational geometry algorithms and applications-Springer-Verlag Berlin Heidelberg (2008) [page: 49]. But got WA on test 7.

Then I change my triangulation algorithm and use the Ear clipping method mentioned here. Here is my implementation($$$O(n^3)$$$). But again got WA on case 31.

I've read the editorial, and without triangulation, just take each pair of edges (one from $$$A$$$ and another one from $$$B$$$) and Minkowski sum them and got AC. My code.

Do we only need the borderline of the polygon here in this problem? or my triangulation code is wrong. Can you help me figure out, what have I done wrong, in the code? And please share your triangulation code(both $$$n^2$$$ and $$$nlogn$$$ [with line sweep]).

UPDATE: The main problem that was in my solution was a typo:

current submission: 178730641 — AC previous submission: 116207161 — WA

Full text and comments »

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