ZeyadKhattab's blog

By ZeyadKhattab, history, 4 years ago, In English

I would like to share with you my best Codeforces moments and my reactions to them.

Moment 1

Yesterday, I had my best performance in a codeforces contest, I reached my max rating of 2236 (120+ my 2nd best rating) and my best rank in a round (20th). I was really happy, and I checked how did I compare (historically) against my friends and people I know, and I realized that there must be a mistake, there is no way I am better than these people and concluded that yesterday, I was lucky and that the problems were so easy and I had a convenient rating of 2070 which meant the contest was rated for me and I can jump high into master.

Moment 2

In a previous round (my 2nd best) which lead me to have my best rating (at the time) of 2078. I had similar thoughts, "I was lucky today, this contest was supposed to be Div3 (true story) and I just abused the fact that it is rated for me."

Moment 3

This happened when I first reached master, it was around the end of 2019 and the start of 2020, I entered multiple contests in a short period of time and my rating steadily increased until I became master only by solving by 4 problems in Div2, and I thought to myself, "Well, currently, the number of participants is much larger than usual, which means that a not so good performance will increase my rating and I was lucky to abuse this fact. "

My Thoughts

These 3 stories show a common theme, "I am not supposed to be here." This kind of behavior, when you attribute your success to external circumstances or luck rather than effort you exerted, is known as "Impostor Syndrome".

I thought about it to try to figure out which part is true and which is just an exaggeration, and here are my thoughts.

What I experienced is an example of the "Fundamental attribution error" where I explain my performances based on the particular situations I experienced, but attribute others's success on personality traits, "They are just better problem solvers."

What this means is even though luck was clearly on my side, this shouldn't decrease the value of my achievements because these situations I mentioned were experienced by everyone, so if there is an easy contest, and someone puts a good performance then he deserves what he achieved compared to someone who entered the same contest but did not do so well. You might also think, "What about the people who missed the easy contest?" and my answer to that is the idea that luck is not purely random, the more you are proactive, the more you enter contests, the more likely it is to stumble upon an easy contest; thus, rewarding the more proactive person.

I would love to hear your thoughts.

Full text and comments »

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

By ZeyadKhattab, history, 4 years ago, In English

A Segment Tree query works by breaking down a segment that is queried into several pre-computed segment tree segments and merge them together to find the answer for the queried segment.

What is a tight upper bound for the number of segment tree segments that are merged together?

I believe it's $$$2*log(n)$$$ because the following scenario is possible:

4 nodes are visited in the majority of the segment tree levels, 2 of them make recursive calls, (visiting 4 more in the next level), and 2 segments are returned.

Is this analysis correct?

Is there a tighter upper bound?

Full text and comments »

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

By ZeyadKhattab, history, 4 years ago, In English

I would appreciate it if someone explains the solution for 102055K - Mr. Panda and Kakin

I tried reading AC solutions, but I could not understand them.

Full text and comments »

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

By ZeyadKhattab, history, 5 years ago, In English

Can anyone explain the solution for this problem 102014F - Directional Resemblance ?

The problem basically says:

We are given N vectors in 3D and we want to find 2 vectors such that the angle between them is minimum.

Full text and comments »

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

By ZeyadKhattab, history, 5 years ago, In English

It is commonly known that we can use Fenwick Tree to perform 2 tasks :

1) calculate the prefix sum (a[1]+a[2]+...+a[idx-1]+a[idx]) up to some index

2) increment a certain index by a certain value

but, my question is how can we modify the fenwick tree implementation so that instead of calculating prefix sums, we are calculating suffix sums so the sum we are now querying is (a[idx]+a[idx+1]+...+a[n-1]+a[n]), so I tried to change the implementation by basically swapping the indices that are accessed in the update and the query functions and I tried submitting in different problems and the submissions are accepted and I wanted to know if someone had a proof of why does it work ?

Full text and comments »

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

By ZeyadKhattab, history, 5 years ago, In English

How can we solve the following problem efficiently (I am mainly looking for a Segment Tree solution) ? Given an array of integers A of size N , and Q queries of the form L,R,X we need to find the minimum index i such that L<=i<=R and A[i]>=X 1<=L<=R<=N and |X|<=10^9 1<=N<=10^5 1<=Q<=10^5 |A[i]|<=10^9 for 1<=i<=N

Full text and comments »

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

By ZeyadKhattab, history, 5 years ago, In English

Can someone help me solve this problem ? 101755D - Transfer Window My approach was to build a graph with the players as the nodes and there is an edge between player a and player b if I can exchange a with b then I created 2 nodes; Source and Sink. Then I added edges from from the Source to players I have and edges from players I want to the Sink, and applied max flow on this graph. All edges have capacity one. But then, I cannot construct the solution. My code (which gets WA at test 8) https://ideone.com/U4EjyO

Full text and comments »

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