Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

ScarletS's blog

By ScarletS, 5 months ago, In English

Hi everyone!

A week ago, the 2nd edition of the Western European Olympiad in Informatics was held in London, UK, and now we've brought the problems for everyone to solve on Codeforces! The mirror contest will be held on the Codeforces Gym on Sunday $$$14^{\text{th}}$$$ July 2024 at 10am UTC+1 (check your timezone here!).

Please don't participate in the mirror contest if you have participated or seen the problems!

The Western European Olympiad in Informatics is an individual contest for top secondary school students from Belgium, France, Ireland, Italy, Luxembourg, Netherlands, Portugal, Spain, Switzerland and United Kingdom.

The contest consists of a single day; contestants are given 5 hours to solve 4 problems of various difficulty. Each problem is worth 100 points, distributed into multiple subtasks with different constraints that allow the participant to earn partial scores. For testing, the IOI grading format is used, where the participant receives full feedback about the execution of the solution on all tests during the contest. C++ is the only allowed language in this contest.

We hope you enjoy the contest!

  • WEOI 2024 Committee & Contributors

FelixMP hugopm I_love_MikhailRubinchik ScarletS veluca93, Ahmadsm2005 Bakry erekle

Full text and comments »

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

By ScarletS, 2 years ago, In English

Thank you for participating in our contest! We hope you enjoyed it. Implementations will be added soon (when Codeforces lets authors submit solutions!).

Please let us know what you thought of the problems by voting!

1758A - SSeeeeiinngg DDoouubbllee

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Feedback

1758B - XOR = Average

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial
Feedback

1758C - Almost All Multiples

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial
Feedback

1758D - Range = √Sum

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial
Feedback

1758E - Tick, Tock

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Feedback

1758F - Decent Division

Hint
Solution
Implementation (C++)
Implementation (Python)
Feedback

Full text and comments »

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

By ScarletS, 2 years ago, In English

omg hi Codeforces!

I've been meaning to write a blog about this interesting, but not (as far as I know) documented trick for a while. I've decided to call it the Amogus trick after the first problem where I encountered and used it.

Prerequisites

  • DSU
  • Basic knowledge of 2-SAT (definitely not required, but it may make the blog easier to understand)

Focus Problem: 1594D - Количество предателей

First, let's solve an easier version of this problem, where we just need to find whether there exists a configuration of player roles (i.e. Crewmate or Imposter) such that all the statements made by players so far are true.

Let's look at the two different types of statements made by players separately.

  • Case 1: Player $$$i$$$ claims Player $$$j$$$ is a crewmate. Now, if Player $$$i$$$ is a crewmate, Player $$$j$$$ will also be a crewmate. Similarly, if Player $$$i$$$ is an imposter, Player $$$j$$$ will also be an imposter. The reversed versions of these statements are also true. Using this, we can create a virtual "edge" between Players $$$i$$$ and $$$j$$$, as their roles in the game will always be the same. More formally, for those familiar with 2-SAT or otherwise, we create the equivalency $$$v_i = v_j$$$.

  • Case 2: Player $$$i$$$ claims Player $$$j$$$ is an imposter. Now, if Player $$$i$$$ is a crewmate, Player $$$j$$$ will be an imposter. Similarly, if Player $$$i$$$ is an imposter, Player $$$j$$$ will be a crewmate. We can create a virtual "anti-edge" between Players $$$i$$$ and $$$j$$$, as their roles in the game will always be the different. More formally, we create the equivalency $$$v_i = !v_j$$$.

Adding edges is easy, we can just use normal DSU. But how do we deal with anti-edges? This is where the Amogus Trick comes in!

We can deal with these anti-edges by creating a DSU with $$$2n$$$ nodes, where nodes $$$1$$$ to $$$n$$$ represent player $$$i$$$ being a crewmate, and nodes $$$n + 1$$$ to $$$2n$$$ represent player $$$i - n$$$ being an imposter. Now, let's look at those cases again.

  • Case 1 results in both players having the same role in the game. Therefore, when such a statement is said, we can unite nodes $$$i$$$ and $$$j$$$, and similarly, unite nodes $$$i + n$$$ and $$$j + n$$$.

  • Case 2 results in both players having differing roles in the game. Therefore, when such a statement is said, we can unite nodes $$$i$$$ and $$$j + n$$$, and similarly, unite nodes $$$i + n$$$ and $$$j$$$.

Testcases 2 & 3 of the sample input in the problem, respectively, visualised with the Amogus trick:

So, how can we solve our reduced problem with this? Note that a player can be exactly one of $$$\{ \text{Crewmate, Imposter} \}$$$, so a configuration is invalid iff for some $$$1 \le i \le n$$$, nodes $$$i$$$ and $$$i + n$$$ are in the same component in our DSU. This is the only condition we need to check, as since the edges we add to our DSU are symmetric, there will always be a valid assignment of roles.

It's not too difficult to extend this idea to solve our original problem.

Full Solution

Using this trick, we can solve a variety of other problems, such as dynamic bipartiteness checking, and it can often be paired with other modifications of DSU such as with support for rollbacks.

Other Problems:

Problems are ordered (roughly) in ascending order of difficulty.

1702E - Раздели на два набора

tourist's AC Code

1290C - Освещение префиксов

My AC Code

1713E - Обмен крестом

My AC Code

1444C - Тимбилдинг

My AC Code

A special thank you to kostia244, BucketPotato, fishy15 and AlperenT for providing lots of feedback and/or sample problems!

Full text and comments »

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

By ScarletS, history, 3 years ago, In English
Tragic Backstory

As the title suggests, I would like to propose that Codeforces keep its extra (late) registration open throughout the contest. Unlike AtCoder, where such a system is problematic due to its penalty system, Codeforces' penalty for submissions increases every minute, and it is no different to registering 2 days before the contest, so it isn't exploitable.

I don't see any reason not to have this, unless it is too much of a technical difficulty due to room allocation?

E: Pinging MikeMirzayanov as this seems popular, also bump for exposure.

Full text and comments »

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

By ScarletS, 3 years ago, In English

Hey there Codeforces!

flamestorm and I are glad to invite you to our first-ever Codeforces round, Codeforces Round 742 (Div. 2), which will be held on 05.09.2021 17:35 (Московское время). This round will be rated for participants with rating lower than 2100.

Special shoutouts to:

You will have 2 hours to work on (and solve!) 6 problems. At most one of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round! You are highly encouraged to read all the problems ;).

UPD: The score distribution is 500 — 1000 — 1500 — 1750 — 2250 — 2750.

Good luck, and see you on the scoreboard!

UPD: Editorial is out!

UPD: Congrats to the winners!

Div. 2 (the only 5 contestants to solve the whole set!):

  1. shengtongtong

  2. zihouzhong

  3. NOOB228

  4. definition_win

  5. TearsFreeze

Div. 1 + 2:

  1. SSRS_

  2. dlalswp25

  3. LayCurse

  4. neal

  5. Vercingetorix

We hope you enjoyed the round. See you soon!

Full text and comments »

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

By ScarletS, history, 3 years ago, In English

I'd like to preface this by saying I know that the world doesn't revolve around IOI participants or whatever, this is just a suggestion. There is an upcoming Div. 1 and Div. 2 round (#728) scheduled for the 25th of June 15:35 UTC. I think Div. 1 rounds are pretty rare as it is at the moment, and that most serious IOI competitors practice on Codeforces anyways, so it would be nice if it could be rescheduled to some day that doesn't clash with one of the competition days. That way, it can also serve as a nice practice contest for the IOI :)

E: This topic seems to be supported by many in the Codeforces community (judging from the upvotes), I think it's fair to tag MikeMirzayanov now.

E2: adedalic too!

Full text and comments »

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

By ScarletS, history, 4 years ago, In English

A — Star

Solution

B — uNrEaDaBlE sTrInG

Solution

C — Kaprekar Number

Solution

D — Base n

Solution

E — Train

Solution

F — Potion

Solution

Full text and comments »

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

By ScarletS, history, 4 years ago, In English

A — Very Very Primitive Game

Solution

B — Magic 3

Solution

C — Bowls and Dishes

Solution

D — Staircase Sequences

Solution

E — Magical Ornament

Solution

F — Shift and Inversions

Solution

Full text and comments »

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

By ScarletS, history, 4 years ago, In English

A — Large Digits

Solution

B — Gentle Pairs

Solution

C — 1-SAT

Solution

D — Choose Me

Solution

E — Through Path

Solution

F — Close Group

Solution

Full text and comments »

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

By ScarletS, history, 4 years ago, In English

A — ABC Preparation

Solution

B — Smartphone Addiction

Solution

C — Duodecim Ferra

Solution 1

D — Stamp

Solution

E — Sequence Matching

Solution

F — Range Xor Query

Solution

Full text and comments »

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