During Codeforces Round 934 (Div. 2) I submitted problem D hoping to get the green AC but unfortunately got the red WA (submission 251770538). I spent the rest of the time in the contest trying to figure out the problem in vain. After the contest, I checked the accepted solutions and found that they were exactly like mine which made me more confused.

I stress-tested my solution using a brute-force approach during the contest and using AC solutions after the contest time but couldn't find a single test case. Even after a million random test cases, my solution is still steadfast. I know that a few hundred test cases are enough.

My implementation of string hashing is inspired by Usaco.guide, which uses random bases and a fixed modulus (1LL << 61) -1). I used multiple bases to make sure no collisions happen, but this also didn't help.

Usaco.guide string hashing implementation

Unfortunately, I couldn't get AC during the contest but now I'm curious about this weird behavior of string hashing. Why using many random bases doesn't help and the solution is to use a prime modulus (i.e. $10^9 + 7$)?

Now the situation is more complex, I tried to submit a solution (submission 252010026) with only one base and $10^9 + 7$ as a modulus and got AC. Isn't the collision probability high for such a case?

Another thing to note is the inability to use GNU C++20 compiler caused all of this chaos because I couldn't use __int128 and (1LL << 61) - 1 as a modulus which I think will get AC.

• +43

The easy version wants every person to send and receive, we can model the problem to be a graph problem where powers of $2$ are the nodes, and persons are the directed edges between the required power of $2$ to send and the required power of $2$ to receive. So, we can always have the cycles of persons by the fact that Eulerian circuits exit.

Here is a comment on the editorial that explains it more precisely.

But in the hard version, what is the proof that we can always have cycles or paths of persons when some will only send or receive?!

• 0

I'm trying to list all the YT channels of the Codeforces competitors, not necessarily mean that the channel is active or has many videos. The channel should be mainly for competitive stuff. (sorted by title as appeared in July 2023)

Non-English Channels

Unkown handles

• +174

In the recent Div 3, I was rushing to submit fast to reduce the penalty so I miss-typed this part of the code:

            if (j + tochange[i])
dp[i + 1][j + tochange[i]] = dp[i + 1][j + tochange[i]] | dp[i][j];


It should be:

            if (j + tochange[i] <= n)
dp[i + 1][j + tochange[i]] = dp[i + 1][j + tochange[i]] | dp[i][j];


Can you hack my submission, please?: 203309510

Update:

Congratulations Yousef-Elwan!

But why my solution didn't get RTE?

• +33

By MuhammadSawalhy, history, 16 months ago,

In the last round Codeforces Round 838 (Div. 2) I managed to solve A, B, and C in about 45 minutes even faster than a friend of mine who is a master and faster than lots of experts. I was left with about 1:45:00 to solve D but in vain. This happens many times in recent rounds, solving the first 3 problems so quickly and D is the big obstacle that seems impossible to approach.

If anyone can give me some advice to attack D more efficiently I'll be thankful.

• +12

By MuhammadSawalhy, history, 20 months ago,

What can really cause such a runtime error with this version of the GNU C++ compiler? The only thing I thought about was a bug in this version, which was fixed later in GNU C++17.

• -20

By MuhammadSawalhy, history, 22 months ago,

This is my first time submitting an answer with python. I tried PyPy 3-64 but got runtime error, I thought it was my fault to submit with PyPy as the language which I don't know anything about it. Then I tried to submit again with Python 3 in no vain.

These are my submissions:

Can anyone help?!

• 0