On the circumference of a circle are two red points. One is allowed to perform the following operations:

1. Add a RED point to the circumference and change the color of its two neighboring points (red to blue, or blue to red).
2. Remove a RED point from the circumference and change the color of its two neighboring points, again from red to blue or blue to red.

If one starts with two red points, show that one cannot achieve a configuration with two blue points.

The official editorial for E given here: https://mirror.codeforces.com/blog/entry/92739 has much less detail than the Chinese editorial ( https://www.cnblogs.com/invisible-eyes/p/15003033.html ). Can anyone graciously translate the Chinese editorial E solution into english?

(Or provide an English solution?). I could not find an understandable proof for E in the comments section of the editorial's blog post.

Thanks in advance.

Quora Programming Challenge 2021

Quora, an American tech-company, is hosting an algorithm contest with cash prizes on February 6 and 7, 2021.

Some info copy-pasted from the contest webpage :

About the Challenge

At Quora, we work on difficult programming challenges on a daily basis. We wanted to share some of the interesting problems that we work on. Thus, we drew inspiration from real-world challenges in our product, systems, and machine learning applications to create an interesting set of algorithm problems that we hope you’ll enjoy.

Divisions

In order to accomodate a wide range of timezones, we will be holding the contest in two divisions. Each division will have its own unique set of problems and a separate set of winners and prizes. Participants can join one or both divisions. The divisions will be held at the following times:

• Division 1: Feb 6 2021, 14:00 to 18:00 (UTC + 00:00)
• Division 2: Feb 7 2021, 01:00 to 05:00 (UTC + 00:00)

Prizes

Top place finishers in each division will be awarded the following prizes:

• 1st place: $2000 USD
• 2nd place: $1000 USD
• 3rd place: $500 USD
• 4th to 10th place: $200 USD
• Top 50 places: Quora T-Shirt

Participants who score well may also be fast-tracked through our interview process, if they are interested in roles at Quora.

Rules

1. You may participate in one or both divisions of the contest.
2. After you register, we will send you the login information for the contest platform before the contest date.
3. Each division will feature 6 problems; each problem is scored out of 100.
4. Ties in score will be resolved by considering the timestamp of the final submission of each participant.
5. This is an individual competition. Please refrain from discussing solutions with anyone else during the contest.
6. Any case of code plagiarism will result in disqualification of all users involved from the contest.

To register, go to their webpage

It's well known that the longest palindromic subsequence (LPS) of a string s can be obtained by computing the longest common subsequence (LCS) of s and its reverse.

There may be multiple LCS's between a string and its reverse, some of which are palindromic and some of which are not.

For example the string "CABCA" and its reverse "ACBAC" have "ABC" and "ACA" as LCS's.

Here is the DP table:

    A C B A C

  0 0 0 0 0 0

C 0 0 1 1 1 1

A 0 1 1 1 2 2

B 0 1 1 2 2 2

C 0 1 2 2 2 3

A 0 1 2 2 3 3

I'm trying to understand why taking the topmost or bottommost path in the DP table will always yield a palindromic LCS. For example the topmost path here yields "CAC" and the bottommost path yields "ACA".

Can anyone explain this? Thank you in advance!

For CodeForces round #537 (Div. 2) the problem difficulty algorithm seems incorrect.

Problem B — 694 / 4752 correct submissions during contest, rated 1600

Problem C — 1272 / 2172 correct submissions during contest, rated 1700

Can anyone explain how this could happen? I don't see how any algorithm could rank the C as harder.

I was reading the tutorial of CF 763D, a problem about tree isomorphism. The solution involved computing polynomial hashes of all possible subtrees of a tree (max 10^5 vertices), and then comparing the hashes as a substitute for checking tree equality. It seems to me like the solution is vulnerable to hash collisions.

I'm relatively new to competitive programming. Is it normal for there to be problems that require solutions that are vulnerable to hash collisions? Shouldn't a good problem be one that is provably solvable for 100% of all possible inputs?

The problem is here: http://mirror.codeforces.com/problemset/problem/763/D

The tutorial is here: http://mirror.codeforces.com/blog/entry/50205

rng_58 also wrote a blog post on this: http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html. The solution given there also has a nonzero hash collision probability.