Note 8: Codeforces MemSQL start[c]up Round 1 E

Revision en11, by NeoYL, 2024-03-09 17:08:03

Hi Codeforces, it has been a long time since I wrote a note blog.

This is the 8th episode of this "note" series. I will write notes on problems (normally around 2500-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

Difficulty rating
Tags

Problem link

Problem paraphrased:

You are given an integer $$$N$$$.

You would need to start from node $$$0$$$ and visit every other node once and end at node $$$0$$$ again.

When we reach node $$$i$$$, we can only go to $$$(2*i)$$$ $$$mod$$$ $$$N$$$ or $$$(2*i + 1)$$$ $$$mod$$$ $$$N$$$.

Print a cycle that contains all $$$N$$$ nodes and starts and ends at node $$$0$$$.

Hint 1
Hint 2
Solution

AC code link

Here is the proof for Hint 1.

proof of Hint 1
Tags dsu, constructive, brain

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English NeoYL 2024-03-14 09:19:42 1
en17 English NeoYL 2024-03-10 05:52:15 15
en16 English NeoYL 2024-03-09 17:14:22 5 Tiny change: 'm node $0$ and visit eve' -> 'm node $0$, visit eve'
en15 English NeoYL 2024-03-09 17:10:33 1 Tiny change: 'ch problem so can I ' -> 'ch problem, so can I '
en14 English NeoYL 2024-03-09 17:10:12 4 Tiny change: 'e have an upvote plssss.\n' -> 'e have an **upvote** plssss.\n'
en13 English NeoYL 2024-03-09 17:09:49 112
en12 English NeoYL 2024-03-09 17:08:27 3 Tiny change: 'oes to $(2i + 1)$ $m' -> 'oes to $(2 * i + 1)$ $m'
en11 English NeoYL 2024-03-09 17:08:03 9
en10 English NeoYL 2024-03-09 17:07:08 8
en9 English NeoYL 2024-03-09 17:06:18 8
en8 English NeoYL 2024-03-09 17:05:36 1 Tiny change: 'ating">\n$*2800$\n</s' -> 'ating">\n$2800$\n</s'
en7 English NeoYL 2024-03-09 17:05:00 33
en6 English NeoYL 2024-03-09 17:03:43 14
en5 English NeoYL 2024-03-09 17:03:10 5 Tiny change: 'lem/E)\n\nProblem pa' -> 'lem/E)\n\n### Problem pa'
en4 English NeoYL 2024-03-09 17:02:34 1220
en3 English NeoYL 2024-03-08 03:28:48 0 (published)
en2 English NeoYL 2024-03-08 03:26:59 1 Tiny change: '(2i) mod N or $(2i +' -> '(2i) mod N$ or $(2i +'
en1 English NeoYL 2024-03-08 03:26:32 1615 Initial revision (saved to drafts)