MuhammadSawalhy's blog

By MuhammadSawalhy, 5 weeks ago, In English

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.

Full text and comments »

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

By MuhammadSawalhy, 6 months ago, In English

Problem: 1868B2 - Candy Party (Hard Version)

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?!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MuhammadSawalhy, 10 months ago, In English

If you have more channels please leave a comment and I will update it. I hope it is helpful for you!

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)

Let's welcome the Codeforcers YouTubers:

Author handle Link Vote
tourist https://youtube.com/channel/UCkySD00cmDWYHXA31hqRYRw
Um_nik https://youtube.com/@umnik_team
Petr https://youtube.com/user/petrmitrichev
ecnerwala https://youtube.com/channel/UCn9ng6ZUnh5weU1BsIQoZ5w
jqdai0815 https://youtube.com/@yuhaodu3382
Golovanov399 https://youtube.com/@Golovanov399
Errichto https://youtube.com/@Errichto
SecondThread https://youtube.com/c/SecondThread
neal https://youtube.com/c/NealWuProgramming
Geothermal https://youtube.com/@jayleedsgeothermal5200
tmwilliamlin168 https://youtube.com/c/WilliamLin168
galen_colin https://youtube.com/c/ColinGalen
BucketPotato https://youtube.com/@BucketPotato
pashka https://youtube.com/pavelmavrin
Shayan, Algorithms_with_Shayan https://youtube.com/@AlgorithmswithShayan
orz https://youtube.com/channel/UCXh5Qf6QYt0C_H_M-Uqkc8w
rembocoder https://youtube.com/@rembocoder
Maksim1744 https://youtube.com/@maksim1744
Egor https://youtube.com/@TCScreencasts
errorgorn, kshitij_sodani, sidhant https://youtube.com/@algoplanet
peltorator https://youtube.com/@peltorator
demoralizer https://youtube.com/@utkarshgupta9858
AaronHe https://youtube.com/@AaronHe
Joshc https://youtube.com/@numb3r5
Priyansh31dec https://youtube.com/@PriyanshAgarwal
KDVinit https://youtube.com/@programmingclub_iitm
acraider https://youtube.com/@vivekgupta3484
tyr0Whiz https://youtube.com/@tyroWhiz
cuiaoxiang https://youtube.com/@aoxiangcui7566
Beacon https://youtube.com/@beaconcodes
stefdasca https://youtube.com/@stefdasca
sharmaharisam https://youtube.com/@Harisamsharma
snowysecret https://youtube.com/@dbsic211
i_pranavmehta https://youtube.com/@GrindCoding
kartik8800 https://youtube.com/@AlgosWithKartik
micho https://youtube.com/@MitkoNikov
kazama460 https://youtube.com/@codencode
Shaun0510 https://youtube.com/@programmingclub_iitm
importlogic https://youtube.com/@cpwithcpp
ak2006 https://youtube.com/@adhishkancharla

Non-English Channels

Author handle Language Link Vote
kotatsugame Japanese https://youtube.com/@kotatsugame
andrewzta Russian https://youtube.com/@andrewzta
dmkz Russian https://youtube.com/@cp_mirea
AST_TheCoder Bengali https://youtube.com/@md.allshahoriartonmoy9874
mostafa.saad.fci Arabic https://youtube.com/@ArabicCompetitiveProgramming
_Mahmoud_Ayman Arabic https://youtube.com/@mahmoudayman8873
Sadiq_23 Bengali https://youtube.com/@wrongsubmission4700

Unkown handles

Channel name Link Vote
Algorithms Live! https://youtube.com/@AlgorithmsLive
William Fiset https://youtube.com/c/WilliamFiset-videos
code_report https://youtube.com/c/codereport
Inside Code https://youtube.com/@insidecode

Full text and comments »

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

By MuhammadSawalhy, 12 months ago, In English

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:

Solution verdict: Wrong answer

Congratulations Yousef-Elwan!

But why my solution didn't get RTE?

Full text and comments »

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

By MuhammadSawalhy, history, 16 months ago, In English

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.

Full text and comments »

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

By MuhammadSawalhy, history, 20 months ago, In English

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.

Full text and comments »

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

By MuhammadSawalhy, history, 22 months ago, In English

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:

  1. https://mirror.codeforces.com/contest/1690/submission/160147330
  2. https://mirror.codeforces.com/contest/1690/submission/160147403

Can anyone help?!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it